0

私は初心者で、Java でクルスカルのアルゴリズムを使用してグラフの最小カットを見つけようとしています。

入力を読み取って、エッジのランダムな重みで vertexCount^2 個の MST を作成できる場所に到達しました。あとは、MST から、S と VS を分離するのに必要なカット数を計算するだけです。これにより、vertexCount^2 個の選択肢から最小のものを選択できます。

S と VS を取得するには、MST の最後のエッジを無視する必要があることを正しく理解していると思います。しかし、S と VS を接続しているエッジの数を把握する方法がわかりません。

したがって、私の質問は次のとおりです。2) S と VS を接続しているエッジの数を確認するにはどうすればよいですか?

PS。これは私のコードのスニペットです： 

            // create weighted edge graph from input.txt
            int vertexCount, edgeCount;
            Edge edgeTemp;
            vertexCount = s.nextInt();
            edgeCount = s.nextInt();
            EdgeWeightedGraph G = new EdgeWeightedGraph(vertexCount, edgeCount);
            for (int j = 0; j < edgeCount; j++) {
                edgeTemp = new Edge(s.nextInt(), s.nextInt(), new Random().nextInt(edgeCount));
                G.addEdge(edgeTemp);
            }

            // create kruskal's mst from graph G
            for (int j = 0; j < vertexCount*vertexCount; j++) {
                KruskalMST mst = new KruskalMST(G);
                for (Edge e : mst.edges()) {
                    System.out.println(e);
                }
                System.out.println(NEWLINE);
                if (j != vertexCount*vertexCount - 2)
                    G.randomizeWeight(edgeCount);
            }

PSS。これが関連する場合、コードを書くときにhttp://algs4.cs.princeton.edu/43mst/のコードを見ました。

4

1 に答える 1

0

グラフから MST を取得するときは、Kruskal のアルゴリズムを使用しました。つまり、union メソッドと find メソッドを使用したに違いありません。

各頂点は、最初は独自の親です。グラフから個別のコンポーネントの和集合を取得するときは、組み合わせコンポーネント (シングルトンを含む) に単一の親を持つように割り当てます。したがって、S と VS を残す頃には、各コンポーネントのすべての頂点が同じ親を持つことになります!

したがって、EdgeWeightedGraph に戻り、グラフ内のすべてのエッジを反復処理します (MST ではありません!)。2 つの頂点が異なる親を持つエッジを見つけた場合、それはそのエッジがコンポーネント S と VS を接続していることを意味します。このようなエッジを見るたびに++を数えます。

これにより、グラフに必要なカットの総数がわかります!

于 2015-10-12T11:49:44.820 に答える