0

我是一名初学者，我正在尝试使用 Java 中的 Kruskal 算法找到图形的最小分割。

我已经到了可以读取输入并为边缘创建随机权重的 vertexCount^2 数量的 MST 的位置。我剩下要做的就是从我的 MST 中计算出分离 S 和 VS 需要多少次削减。这将允许我从 vertexCount^2 个选项中选择最小值。

我想我理解正确，我应该忽略 MST 的最后一条边来获得 S 和 VS。但是我不知道如何弄清楚有多少条边连接了 S 和 VS。

所以我的问题是：1）vertexCount^2 随机 MST 是否足以确信它将包含最小切割？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！）。当我发现一条边的两个顶点有不同的父节点时，这意味着该边连接了组件 S 和 VS。每次看到这样的边缘，我都会数++。

这给了我图表中所需的削减总数！

于 2015-10-12T11:49:44.820 回答