Нахождение минимального значения графа с помощью алгоритма Крускала

Question

Я новичок, и я пытаюсь найти минимальный срез графа, используя алгоритм Крускала в Java.

Я попал туда, где я могу прочитать входные данные и создать vertexCount^2 числа MST со случайными весами для ребер. Все, что мне осталось сделать, это выяснить из моего MST, сколько срезов требуется для разделения S и VS. Это позволит мне выбрать минимальное число вершин из числа ^ 2 вариантов.

Я думаю, что я правильно понимаю, что я должен игнорировать последний край MST, чтобы получить S и VS. Но я заблудился, как выяснить, сколько ребер соединяют S и VS.

Итак, мой вопрос: 1) Достаточно ли случайного MST vertexCount^2, чтобы быть уверенным, что он будет содержать минимальный срез? 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/ при написании своего кода.

Answer 1

При получении MST из графика я использовал алгоритм Крускала. Это означает, что я должен был использовать union и найти методы.

Каждая вершина является своим собственным родителем в начале. Получая объединение различных компонентов из графа, я назначаю объединяющие компоненты (включая синглтоны) одному родителю. Таким образом, ко времени, когда у меня останутся S и VS, все вершины каждого компонента будут иметь одного и того же родителя!

Поэтому я возвращаюсь к своему EdgeWeightedGraph и перебираю все ребра на графике (не MST!). Когда я нахожу ребро, две вершины которого имеют разных родителей, это означает, что ребро соединяет компоненты S и VS. Я считаю ++ каждый раз, когда вижу такой край.

Это дает мне общее количество срезов, необходимых на графике!