实施 Kruskal 算法时测试电路

我正在尝试编写一个程序来找到最小生成树。但我在使用该算法时遇到的一个问题是测试电路。在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"));

    }
}

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

如果你看维基页面 http://en.wikipedia.org/wiki/Kruskal%27s_algorithm算法如下：

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.

你应该使用不相交集数据结构 http://en.wikipedia.org/wiki/Disjoint-set_data_structure为了这。再次来自维基：

首先使用 O(E log E) 中的比较排序按权重对边进行排序 时间;这允许步骤“从 S 中删除具有最小权重的边” 以恒定的时间运行。接下来，我们使用不相交集数据 结构（Union&Find）来跟踪哪些顶点位于哪个顶点 成分。我们需要执行 O(E) 操作，两个“查找”操作 每条边可能有一个并集。即使是简单的不相交集数据 诸如不相交集森林之类的按等级并集的结构可以执行 O(E log V) 时间内的 O(E) 操作。因此总时间为 O(E log E) = O(E log V)。

#创建不相交的森林 现在你可以看看Boost图库-增量组件 http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/incremental_components.html部分。 你应该实现一些方法：MakeSet, Find, Union，之后就可以实现Kruskal算法了。您所做的就是使用集合，最简单的方法就是使用链表。

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

1-首先实施MakeSet通过链表：

这为增量准备了不相交集数据结构 连接组件算法通过使图中的每个顶点成为 它自己的组件（或集合）的成员。

只需将每个顶点（元素）初始化为新集合的代表元素，我们可以通过将它们设置为自己的父元素来做到这一点：

 function MakeSet(x)
   x.parent := x

2-实施Find method:

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

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

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

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

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？

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

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