使用Kruskal算法計算最小生成樹時出現錯誤的答案

Question

我正在嘗試使用kruskal算法來解決this MST question on spoj。我的程序似乎適用於所有的測試用例，但是反覆使用這個代碼會給WA帶來麻煩。

我無法在此代碼上找到任何失敗的測試用例。有人能指出我做錯了什麼嗎？

import java.io.PrintWriter; 
import java.util.Arrays; 


public class CSTREET { 

    static final int MAX = 1002; 
    static Node edgeList[]; 
    static int parent[] = new int[MAX]; 


    public static void main(String[] args) throws Exception { 
     Reader in = new Reader(); 
     PrintWriter out = new PrintWriter(System.out, true); 
     int t = in.nextInt(); 
     while (t-- != 0) { 

      int price = in.nextInt(); 
      int vertices = in.nextInt(); 
      int edge = in.nextInt(); 
      int idx = 0; 
      edgeList = new Node[edge]; 
      for (int i = 1; i <= vertices; i++) { 
       parent[i] = i; 
      } 

      while (idx < edge) { 

       int src = in.nextInt(); 
       int dest = in.nextInt(); 
       int cost = in.nextInt(); 
       Node node = new Node(src, dest, cost); 

       edgeList[idx] = node; 
       idx++; 
      } 

      Arrays.sort(edgeList); 
      int edgeCount = 0; 


      long totalCost = 0; 
      idx = 0; 

      while (edgeCount < vertices-1) { 
       Node curEdge = edgeList[idx]; 
       if (!checkCycle(curEdge.src, curEdge.dest)) { 

        edgeCount++; 
        totalCost += curEdge.cost; 

       } 
       idx++; 

      } 
      out.println(totalCost * price); 
     } 
    } 


    static boolean checkCycle(int src, int dest) { 

     if (findParent(src) == findParent(dest)) { 
      return true; 
     } 

     while (parent[dest] != parent[src]) { 
      parent[dest] = src; 
      src = parent[src]; 
     } 

     return false; 

    } 

    static int findParent(int i) { 

     while (parent[i] != i) { 
      i = parent[i]; 
     } 

     return i; 
    } 


    static class Node implements Comparable<Node> { 

     int src; 
     int dest; 
     int cost; 

     public Node(int src, int dest, int cost) { 
      this.src = src; 
      this.dest = dest; 
      this.cost = cost; 
     } 

     @Override 
     public int compareTo(Node o) { 
      return this.cost - o.cost; 
     } 
    } 
} 

Answer 1

您的union-find實現不正確。當你調用checkCycle(A, D)考慮這個例子

x -> y (y is parent of x) 

A -> B -> C 
D -> E 

發生的事情是所有的5個節點的應該去一組，例如：

A -> B -> C 
D -> E -> C 

但是發生在你的代碼是：

A -> B -> C 
D -> C 
E 

這顯然不正確。

您可以更改如下checkCycle：

static boolean checkCycle(int src, int dest) { 

    int srcRoot = findParent(src); 
    int destRoot = findParent(dest); 
    if (srcRoot == destRoot) { 
     return true; 
    } 
    parent[destRoot] = srcRoot; 
    return false; 
} 

我強烈建議你閱讀維基百科文章關於Disjoint-set和實施路徑的壓縮版本，提高了複雜性。