java - 我使用 union-find 数据结构实现 Kruskal 算法有什么问题。

Question

我正在尝试实现 Kruskal 算法，并在 MST 中找到权重之和。我认为我的问题出在我设置每个节点的父节点的某个地方，但我不确定，因为在小示例中它工作正常，但是在大示例中它没有检测到循环，最终答案是错误的。所以我的发现可能是错误的，但我不确定。这是我的代码:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Scanner;

public class Graph {
    private static int parent[];
    private static int numberOfNodes, numberOfEdges, weight;
    private static Node startNode, endNode;
    private static Graph g;
    private static ArrayList<Integer> listOfWeights = new ArrayList<Integer>();
    private static ArrayList<Edge> listOfEdges = new ArrayList<Edge>();
    private static ArrayList<Node> listOfNodes = new ArrayList<Node>();
    private static HashMap<Edge, Integer> distance = new HashMap<Edge, Integer>();
    private static HashMap<Edge, Integer> sortedMap = new HashMap<Edge, Integer>();
    //values = Integer
    private Scanner sc;

    public static void main(String[] args) throws FileNotFoundException {
        // TODO Auto-generated method stub
        g = new Graph();
    }

    public Graph() throws FileNotFoundException {

        sc = new Scanner(new File("data"));
        numberOfNodes = Integer.parseInt(sc.next());
        numberOfEdges = Integer.parseInt(sc.next());

        if(numberOfEdges > 0){
            for(int i = 0; i < numberOfEdges; i++) {
                //read the start point
                startNode = new Node(Integer.parseInt(sc.next()));
                //read the end point
                endNode = new Node(Integer.parseInt(sc.next()));
                //read the price per node
                weight = Integer.parseInt(sc.next());
                Edge e = new Edge(startNode,endNode);
                //set the weight per node
                e.setWeight(weight);
                //put them in a hashmap
                distance.put(e,e.getWeight());
                if(!listOfNodes.contains(startNode)){
                    listOfNodes.add(startNode);
                }
                if(!listOfNodes.contains(endNode)){
                    listOfNodes.add(endNode);
                }
                //System.out.println(distance.get(e));
            }
            System.out.println("without sort distance: " + distance.toString());
            for (Object key : distance.keySet()) {
                listOfEdges.add((Edge) key);
            }
            for (Object value : distance.values()) {
                listOfWeights.add((Integer) value);
            }
            sortedMap = sortHashMapByValuesD(distance);
            //System.out.println("list of nodes: "+ listOfNodes);
            parent = new int[listOfNodes.size()];
            System.out.println("sorted by weights: "+sortedMap.toString());
            System.out.println(kruskalAlgo(sortedMap));
        }
        else{
            System.out.println(0);
        }
    }

    public static void makeSet(int x){
        parent[x-1] = x;
    }

    public static int find(int x){
        //System.out.println("FIND ==> x: " + x + ".parent = " + parent[x-1] );
        if(parent[x-1] == x){
            return x;
        }
        return find(parent[x-1]);
    }

    public static void union(int x, int y){
        //System.out.println("parent[0]: "+parent[0]);
        parent[x-1] = y;
        System.out.println("x: " + x + " UNION parent[x-1]: " + parent[x-1] + " y " + y );
    }

    public static int kruskalAlgo(HashMap<Edge, Integer> s){
        parent[0] = 0;
        for(int i = 0; i < parent.length; i++){
            makeSet(listOfNodes.get(i).getId());
            //System.out.println("parent is: "+parent[i] + " for node"+ listOfNodes.get(i));
        }
        // for each edge (u,v) ∈ G, taken in increasing order by weight
        int min = 0;
        int edgeNumber = 0;
        for (Edge key : s.keySet()) {
            if(edgeNumber == listOfNodes.size()-1){
                //System.out.println("edgeNumber: "+ edgeNumber);
                //System.out.println("listOfNodes.size()-1: "+ (listOfNodes.size()-1));
                return min;
            }
            Node u = key.getFromNode();
            //System.out.println(u);
            Node v = key.getToNode();
            //System.out.println(v);
            if(find(u.getId()) != find (v.getId())){
                min += key.getWeight();
                union(u.getId(),v.getId());
                System.out.println(key + " weight is: " + key.getWeight());
                edgeNumber++;
            }
        }
        return min;
    }

    public static ArrayList<Edge> findSet(Node v){
        ArrayList<Edge> nodes = new ArrayList<Edge>();
        return nodes;
    }

    //make an ordered listed by increasing weights
    public LinkedHashMap<Edge, Integer> sortHashMapByValuesD(HashMap<Edge, Integer> newMap) {
        //list of edges    
        List<Edge> mapKeys = new ArrayList<Edge>(newMap.keySet());
        //list of nodes
        List<Integer> mapValues = new ArrayList<Integer>(newMap.values());
        //sort the nodes
        Collections.sort(mapValues);
        LinkedHashMap<Edge, Integer> sortedMap = new LinkedHashMap<Edge, Integer>();
        Iterator<Integer> valueIt = mapValues.iterator();
        while (valueIt.hasNext()) {
            Object val = valueIt.next();
            Iterator<Edge> keyIt = mapKeys.iterator();
            while (keyIt.hasNext()) {
                Object key = keyIt.next();
                String comp1 = newMap.get(key).toString();
                String comp2 = val.toString();

                if (comp1.equals(comp2)){
                    newMap.remove(key);
                    mapKeys.remove(key);
                    sortedMap.put((Edge)key, (Integer)val);
                    break;
               }
           }
        }
        return sortedMap;
    }
}

Answer 1

我认为问题可能出在您的 union 实现上:

public static void union(int x, int y){
    parent[x-1] = y;
}

问题是如果 x 已经被加入到一个集合中，它就会有一个你覆盖的父级。

解决方案是连接两个候选节点的根而不是叶节点:

public static void union(int x, int y){
    x=find(x);
    y=find(y);
    parent[x-1] = y;
}

顺便说一下，关于这个不相交集算法的一个很好的描述，加上通过“按等级联合”和“路径压缩”使它更有效的提示在维基百科上 this page .