在java中实现kruskals算法

Question

我能够运行此代码进行一些输入.但在某些情况下,我得到了错误的生成树.例如:如果我在执行程序时给出如下输入:

输入no.of vertices:5输入no.of edges:8

    Enter the vertices and the weight of edge 1:
    1
    3
    10

 Enter the vertices and the weight of edge 2:
1
4
100
 Enter the vertices and the weight of edge 3:
3
5
64
 Enter the vertices and the weight of edge 4:
1
2
13
 Enter the vertices and the weight of edge 5:
3
2
20
 Enter the vertices and the weight of edge 6:
2
5
5
 Enter the vertices and the weight of edge 7:
4
3
80
 Enter the vertices and the weight of edge 8:
4
5
40
MINIMUM SPANNING TREE :
2-5
1-3
4-5
MINIMUM COST = 55

expected o/p :

 MINIMUM SPANNING TREE :
    2-5
    1-3
    1-2
    4-5
    MINIMUM COST = 68

请帮助我纠正我的错误...请告诉我我在代码中做出的改变... plssss

代码如下:

import java.io.*;  
class Edge
{
 int v1,v2,wt;   // wt is the weight of the edge
}
class kruskalsalgo
{
public static void main(String args[])throws IOException 
{ 
int i,j,mincost=0;
BufferedReader br=new BufferedReader( new InputStreamReader(System.in));
System.out.println(" Enter no.of vertices:");
int v=Integer.parseInt(br.readLine());
System.out.println(" Enter no.of edges:");
int e=Integer.parseInt(br.readLine());
 Edge ed[]=new Edge[e+1];
for(i=1;i<=e;i++)
{
 ed[i]=new Edge();
 System.out.println(" Enter the vertices and the weight of edge "+(i)+ ":"); 
 ed[i].v1=Integer.parseInt(br.readLine());
 ed[i].v2=Integer.parseInt(br.readLine());
 ed[i].wt=Integer.parseInt(br.readLine());
}
for(i=1;i<=e;i++)      // sorting the edges in ascending order
 for(j=1;j<=e-1;j++)
{
 if(ed[j].wt>ed[j+1].wt)
 {
   Edge t=new Edge();
    t=ed[j];
    ed[j]=ed[j+1];
    ed[j+1]=t;
}
}

int visited[]=new int[v+1];       // array to check whether the vertex is visited or not
for(i=1;i<=v;i++)
 visited[i]=0;
System.out.println("MINIMUM SPANNING TREE :");


for(i=1;i<=e;i++)
{ 
 if(i>v)
  break;
else if( visited[ed[i].v1]==0 || visited[ed[i].v2]==0)
 {
    System.out.println(ed[i].v1+ "-"+ ed[i].v2);
    visited[ed[i].v1]=visited[ed[i].v2]=1;
    mincost+=ed[i].wt;
 }
}
System.out.println("MINIMUM COST = " +mincost);
}
}

Answer 1

你应该参考实际的算法:http://en.wikipedia.org/wiki/Kruskal%27s_algorithm 你在代码中犯了一些错误.为简单起见,您可能希望定义您的

Edge class something like this:

class Edge implements Comparable<Edge>
{
    int v1,v2,wt; 

    Edge(int v1, int v2, int wt)
    {
        this.v1=v1;
        this.v2=v2;
        this.wt=wt;
    }

    @Override
    public int compareTo(Edge o) {
        Edge e1 = (Edge)o;
        if(e1.wt==this.wt)
            return 0;
        return e1.wt < this.wt ? 1 : -1;
    }

    @Override
    public String toString()
    {
        return String.format("Vertex1:%d \t Vertex2:%d \t Cost:%d\n", v1,v2,wt);

    }
}

这里扩展可比较,因此您可以在边缘使用Java Collections.sort(),它将为您升序排序,并覆盖toString(),以便您可以使用它进行打印并帮助调试.

在您访问过的数组中,您只检查您是否曾在某个时间点访问过它,但这不是制作最小生成树的标准.例如,在你的输入中,我可以选择边{1,2,5},{2,5,5},{4,5,40},这将访问每个顶点一次,但不会给你最小的生成树.

该算法首先说要建造一片树林.这意味着对于每个顶点,您应该创建一个仅将自身作为成员的集合.像这样的东西:

HashMap<Integer,Set<Integer>> forest = new HashMap<Integer,Set<Integer>>();
for(Integer vertex : vertices)
{
        //Each set stores the known vertices reachable from this vertex
        //initialize with it self.
    Set<Integer> vs = new HashSet<Integer>();
    vs.add(vertex);
    forest.put(vertex, vs);
}

现在迭代你的边缘.对它们进行排序很好,因为你可以将它作为堆栈使用,所以弹出直到找到你的最小树或用完边缘.对于每个边缘,要合并由边连接的2个顶点的可到达顶点集.如果构成边的2个顶点的可到达顶点集相同,则不合并,因为它将形成循环.如果没有,请将边缘添加到最小树.找到包含所有顶点的集合后停止.在代码中它看起来像这样:

//sort your edges, you should use existing functionality where possible, saves testing needed
//here edges is your Stack, pop until minimum spanning tree is found.
Collections.sort(edges);
ArrayList<Edge> minSpanTree = new ArrayList<Edge>();
while(true) //while you haven't visited all the vertices at least once
{
    Edge check = edges.remove(0);//pop

    Set<Integer> visited1 = forest.get(check.v1);
    Set<Integer> visited2 = forest.get(check.v2);
    if(visited1.equals(visited2))
        continue;
    minSpanTree.add(check);
    visited1.addAll(visited2);
    for(Integer i : visited1)
    {
        forest.put(i, visited1);
    }
    if(visited1.size()==vertices.length)
        break;
}

所以对于以下输入:

输入:[Vertex1:2 Vertex2:5 Cost:5,Vertex1:1 Vertex2:3 Cost:10,Vertex1:1 Vertex2:2 Cost:13,Vertex1:3 Vertex2:2 Cost:20,Vertex1:4 Vertex2:5 Cost :40,Vertex1:3 Vertex2:5成本:64,Vertex1:4 Vertex2:3成本:80,Vertex1:1 Vertex2:4成本:100]

你得到最小跨度树:输出:[Vertex1:2 Vertex2:5成本:5,Vertex1:1 Vertex2:3成本:10,Vertex1:1 Vertex2:2成本:13,Vertex1:3 Vertex2:2成本:20, Vertex1:4 Vertex2:5成本:40]

-Niru