java - 实现 Kruskal 算法时测试电路

Question

我正在尝试编写一个程序来找到最小生成树。但是我在使用该算法时遇到的一个问题是测试电路。在 Java 中执行此操作的最佳方法是什么。

好的，这是我的代码

import java.io.*;
import java.util.*;

public class JungleRoads 
{
    public static int FindMinimumCost(ArrayList graph,int size)
    {
        int total = 0;
        int [] marked = new int[size];      //keeps track over integer in the mst

        //convert an arraylist to an array
        List<String> wrapper = graph;
        String[] arrayGraph = wrapper.toArray(new String[wrapper.size()]);
        String[] temp = new String[size];
        HashMap visited = new HashMap();


        for(int i = 0; i < size; i++)
        {
           // System.out.println(arrayGraph[i]);
            temp = arrayGraph[i].split(" ");

            //loop over connections of a current node
            for(int j =  2; j < Integer.parseInt(temp[1])*2+2; j++)
            {

                if(temp[j].matches("[0-9]+"))
                {
                    System.out.println(temp[j]);
                }
            }


        }


        graph.clear();
        return total;


    }


    public static void main(String[] args) throws IOException
    {

         FileReader fin = new FileReader("jungle.in");
        BufferedReader infile = new BufferedReader(fin);

        FileWriter fout = new FileWriter("jungle.out");
        BufferedWriter outfile = new BufferedWriter(fout);


        String line;
        line = infile.readLine();
        ArrayList graph = new ArrayList();

        do
        {

            int num = Integer.parseInt(line);
            if(num!= 0)
            {

                int size = Integer.parseInt(line)-1;

                for(int i=0; i < size; i++)
                {
                    line = infile.readLine(); 
                    graph.add(line);
                }

               outfile.write(FindMinimumCost(graph, size));
            }   


            line = infile.readLine();
        }while(!line.equals("0"));

    }
}

Answer 1

Kruskall 算法不搜索循环，因为它的性能效率不高；而是创建不相交的树，然后将它们连接起来。由于用一条边连接两个不同的子树会创建一棵新树，因此无需检查循环。

如果你看wiki page算法如下:

1. create a forest **F** (a set of trees), where each vertex in the graph is a separate tree
2. create a set S containing all the edges in the graph
3. while S is nonempty and F is not yet spanning
    a. remove an edge with minimum weight from S
    b. if that edge connects two different trees, then add it to the forest, combining 
       two trees into a single tree
    c. otherwise discard that edge.

你应该使用 Disjoint Set Data Structure为了这。再次来自维基:

first sort the edges by weight using a comparison sort in O(E log E)time; this allows the step "remove an edge with minimum weight from S"to operate in constant time. Next, we use a disjoint-set datastructure (Union&Find) to keep track of which vertices are in whichcomponents. We need to perform O(E) operations, two 'find' operationsand possibly one union for each edge. Even a simple disjoint-set datastructure such as disjoint-set forests with union by rank can performO(E) operations in O(E log V) time. Thus the total time is O(E log E)= O(E log V).

---

#创建不相交的森林现在你可以看看Boost Graph Library-Incremental Components部分。你应该实现一些方法:MakeSet，Find，Union，然后你就可以实现Kruskall的算法。您所做的只是处理集合，最简单的方法是使用链表。

每个集合都有一个名为代表元素的元素，它是集合中的第一个元素。

1-首先通过链表实现MakeSet:

This prepares the disjoint-sets data structure for the incrementalconnected components algorithm by making each vertex in the graph amember of its own component (or set).

只需将每个顶点(元素)初始化为新集合的代表元素，我们可以通过将它们设置为自己的父节点来实现:

 function MakeSet(x)
   x.parent := x

2- 实现查找方法:

查找包含顶点 x 的集合的代表性元素:

 function Find(x)
 if x.parent == x
    return x
 else
    return Find(x.parent)

if 部分检查元素是否为代表元素。我们将集合的所有代表性元素设置为它们的第一个元素，方法是将它们设置为自己的父元素。

3- 最后，当所有前面的步骤都完成后，简单的部分就是实现 Union 方法:

function Union(x, y)
 xRoot := Find(x) // find representative element of first element(set)
 yRoot := Find(y) // find representative element of second element(set)
 xRoot.parent := yRoot // set representative element of first set 
                       // as same as representative element of second set

现在您应该如何运行 Kruskall？

首先通过MakeSet 方法将所有节点放入n 个不相交的集合中。在每次迭代中找到想要的边(未标记的和最小的边)后，通过Find方法找到其端点顶点的相关集合(它们的代表元素)，如果它们相同，则丢弃这条边，因为这edge 会导致循环，但如果它们在不同的集合中，则使用 Union 方法合并这些集合。由于每个集合都是一棵树，因此它们的联合也是一棵树。

您可以通过为不相交的集合选择更好的数据结构来优化它，但现在我认为这已经足够了。如果你对更高级的数据结构感兴趣，你可以实现 rank 基本方法，在 wiki 中有一个很好的关于它的文档，很简单但我没有提到它以防止混淆。