1

我能够为某些输入运行此代码。但在某些情况下，我得到了错误的生成树。例如：如果我在执行程序时输入如下：

输入顶点数：5 输入边数：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

请帮我纠正我的错误...请告诉我我在代码中所做的更改..请

代码如下：

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);
}
}
4

2 回答 2

16

您应该参考实际算法：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 Cost:64 , Vertex1:4 Vertex2:3 Cost:80 , Vertex1:1 Vertex2:4 Cost:100]

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

-尼鲁

于 2013-02-02T10:04:25.297 回答
0

当您的图形存储为边列表时，这是 Kruskal 算法在 Java 中的正确实现。为了使 Kruskal 算法正常工作，您需要一个称为联合查找（也称为不相交集）的数据结构，它支持快速将集合统一在一起。该算法首先按权重按升序对所有边进行排序，然后将不属于同一节点组的节点连接在一起。这背后的想法是，如果两个节点属于同一个组，那么包括当前边会在我们的最小生成树中导致一个循环，这是不允许的。我希望这有助于查看下面的代码，它有据可查。

代码取自我的Github 算法仓库。

/**
 * An implementation of Kruskal's MST algorithm using an edge list.
 * @author William Fiset
 **/

// Union find data structure 
class UnionFind {

  private int[] id, sz;

  public UnionFind(int n) {
    id = new int[n];
    sz = new int[n];
    for (int i = 0; i < n; i++) {
      id[i] = i;
      sz[i] = 1;
    }
  }

  public int find(int p) {
    int root = p;
    while (root != id[root])
      root = id[root];
    while (p != root) { // Do path compression
      int next = id[p];
      id[p] = root;
      p = next;
    }
    return root;
  }

  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  public int size(int p) {
    return sz[find(p)];
  }

  public void union(int p, int q) {
    int root1 = find(p);
    int root2 = find(q);
    if (root1 == root2) return;
    if (sz[root1] < sz[root2]) {
      sz[root2] += sz[root1];
      id[root1] = root2;
    } else {
      sz[root1] += sz[root2];
      id[root2] = root1;
    }
  }

}

class Edge implements Comparable <Edge> {
  int from, to, cost;
  public Edge(int from, int to, int cost) {
    this.from = from;
    this.to = to;
    this.cost = cost;
  }
  @Override public int compareTo(Edge other) {
    return cost - other.cost;
  }
}

public class KruskalsEdgeList {

  // Given a graph represented as an edge list this method finds
  // the Minimum Spanning Tree (MST) cost if there exists 
  // a MST, otherwise it returns null.
  static Long kruskals(Edge[] edges, int n) {

    if (edges == null) return null;

    long sum = 0L;
    java.util.Arrays.sort(edges);
    UnionFind uf = new UnionFind(n);

    for (Edge edge : edges) {

      // Skip this edge to avoid creating a cycle in MST
      if (uf.connected(edge.from, edge.to))
        continue;

      // Include this edge
      uf.union(edge.from, edge.to);
      sum += edge.cost;

      // Optimization to stop early if we found
      // a MST that includes all the nodes
      if (uf.size(0) == n) break;

    }

    // Make sure we have a MST that includes all the nodes
    if (uf.size(0) != n) return null;

    return sum;

  }

}
于 2017-11-02T06:03:55.437 回答