在实施Kruskalls算法时测试电路

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的算法不会搜索周期,因为它不具有性能效率; 但是尝试创建树的组件,然后将它们相互连接.如您所知,如果使用一个新边连接两个不同的树,您将创建新树,而无需检查周期.

如果你看维基页面算法如下:

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进行此操作.再次来自维基:

首先使用O(E log E)时间中的比较排序按重量对边缘进行排序; 这允许步骤"从S移除具有最小重量的边缘"以在恒定时间内操作.接下来,我们使用一个不相交的数据结构(Union&Find)来跟踪哪些顶点在哪些组件中.我们需要执行O(E)操作,两个'find'操作以及每个边可能有一个union.即使是简单的不相交集数据结构,例如具有按行​​级联的不相交集合林,也可以在O(E log V)时间内执行O(E)运算.因此总时间为O(E log E)= O(E log V).

创造不相交的森林

现在,您可以查看Boost Graph Library-Incremental Components部分.你应该实现一些方法:MakeSet,Find,Union,之后你可以实现kruskall的算法.你所做的只是使用一些集合,最简单的方法是使用链表.

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

1-首先按链表实现MakeSet:

这通过使图中的每个顶点成为其自己的组件(或集合)的成员来为渐进连接组件算法准备不相交集数据结构.

您应该将每个顶点(元素)初始化为新集合的代表元素,您可以通过将它们设置为自己的父集合来完成此操作:

 function MakeSet(x)
   x.parent := x

2-实现查找方法:

查找包含顶点的set的代表元素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？

首先n通过MakeSet方法将所有节点放在不相交的集合中.在找到所需边缘(未检查和最小值)之后的每个步骤中,通过Find方法(它们的代表元素)找到其端点顶点的相关集合,如果它们相同,则将此边缘删除,因为此边缘会导致循环,但如果它们在不同的集合中,使用Union方法合并这些集合.因为每个集合都是树的结合.

您可以通过为不相交集选择更好的数据结构来优化这一点,但现在我认为已经足够了.如果您对更高级的数据结构感兴趣,可以实现排名基础方式,您可以在wiki中找到它,这很容易,但我没有提及它以防止困惑.