4

とboolean[][]呼ばれる 2D 配列があります。これは、 の場合、頂点jが頂点iに接続されるmatrixような有向グラフをエンコードします(逆は必ずしも真ではありません)。 互いに素な有向グラフの数を判断する Java メソッドを作成しようとしています。 matrix[i][j] == true

たとえば、頂点 0 が頂点 1 に接続され、頂点 2 が頂点 3 に接続されている場合 、2つのばらばら(<code>[{{0,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,1,0}}]</code> would be the 2D array)の有向グラフが作成されます。

接続がない場合、ばらばらの有向グラフの数は頂点の数に等しくなります。

4

3 に答える 3

1 
public int countDisjointSubgraphs() {
    int len = matrix.length;
    int[] nodes = new int[len];
    for (int i = 0 ; i < len ; i++) nodes[i] = i;
    for (int i = 0 ; i < len ; i++) {
        for (int j = 0 ; j < len ; j++) {
            if (matrix[i][j] || matrix[j][i])
                for (int k = 0 ; k < len ; k++)
                    if (nodes[k] == nodes[i]) nodes[k] = j;
        }
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i : nodes)
        if (list.indexOf(i) < 0) list.add(i);
    return list.size();
}
于 2012-06-21T18:27:02.930 に答える
1

ツリー内のすべてのノードのリストから始めます。これらを未訪問のノードと考えてください。

次に、未訪問のノードのリストがなくなるまで、次のプロセスを繰り返します。

  1. 現在のノードのグラフに存在するノードを表す空のセット、「ノード セット」を作成します。
  2. 現在のノードから開始して検索を実行します。検索で見つかったノードごとに、未訪問のノード リストから削除します。次に、(1) ノードが別のノード セットに既に存在する場合は、現在のノード セットとその別のノード セットをマージし、次の場所からの検索を停止します。そのノード、または (2) そのノードが現在のノードセットに既に存在する場合は、そのノードからの検索を停止するか、(3) そのノードを見たことがない場合は、それを現在のノードセットに追加します。

このプロセスが完了すると、ノードセットは、それぞれのばらばらのグラフに一意に存在するノードに対応するため、ノードセットの数が求める値になります。

于 2012-05-22T02:35:27.280 に答える
1

強力な接続は必要ないように思われるので、互いに素な集合のフォレストに対して非常に効果的なアルゴリズムが機能します。結合フェーズの後、parent = self でノードをカウントするだけで済みます

それについてのPS Sedgewick lection

于 2012-05-22T02:59:26.690 に答える