public static int findOptimalRoot(int[] msg){
  final int size=(msg.length >> 1) + 1;
  int[] depth=new int[size];
  int[] missing=new int[size];
  int root=-1;
  for (int i=1; i < size; i++) {
    boolean active=false;
    for (int e=0; e < msg.length; e+=2) {
      if (depth[msg[e]] == 0) {
        missing[msg[e + 1]]++;
      }
      if (depth[msg[e + 1]] == 0) {
        missing[msg[e]]++;
      }
    }
    for (int n=0; n < size; n++) {
      if (depth[n] == 0 && missing[n] <= 1) {
        depth[n]=i;
        root=n;
        active=true;
      }
    }
    if (!active) {
      break;
    }
    Arrays.fill(missing,0);
  }
  return root;
}

public static int findOptimalRoot ( int [ ] msg ) { final int size = ( msg . length > > 1 ) + 1 ; int [ ] depth = new int [ size ] ; int [ ] missing = new int [ size ] ; int root = - 1 ; for ( int i = 1 ; i < size ; i ++ ) { boolean active = false ; for ( int e = 0 ; e < msg . length ; e += 2 ) { if ( depth [ msg [ e ] ] == 0 ) { missing [ msg [ e + 1 ] ] ++ ; } if ( depth [ msg [ e + 1 ] ] == 0 ) { missing [ msg [ e ] ] ++ ; } } for ( int n = 0 ; n < size ; n ++ ) { if ( depth [ n ] == 0 && missing [ n ] <= 1 ) { depth [ n ] = i ; root = n ; active = true ; } } if ( ! active ) { break ; } Arrays . fill ( missing , 0 ) ; } return root ; }
find the " optimal " root of a spanning tree . optimal in the sense of : one of the most central nodes . this uses a simple message passing approach . every node that has only one unset neighbor will emit a message to this neighbor . the node last to emit wins .
