了解Java代码中最小生成树的一部分[关闭]

Question

关闭。这个问题需要details or clarity。它当前不接受答案。

---

是否要改善此问题？通过editing this post添加详细信息并澄清问题。

关闭昨天。

谁能向我解释此代码的这两部分，这是Java代码的一部分，作为Dijkstra最短路径最小生成树的数据结构的应用程序

第一个：-

PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));

第二个：-

makeSet(parent);

代码：-

 public String MST(){

    PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));

    for (int i = 0; i <allEdges.size() ; i++) {
        pq.add(allEdges.get(i));
    }

    int [] parent = new int[vertices];
    makeSet(parent);

    ArrayList<Edge> mst = new ArrayList<>();
    int index = 0;

    while(index<vertices-1){
        Edge edge = pq.remove();
        System.out.println("Source : "+edge.source+", Dest : "+edge.destination+", Weight : "+edge.weight);
        int x_set = find(parent, edge.source);
        int y_set = find(parent, edge.destination);

        if(x_set==y_set){}

        else {
            mst.add(edge);
            index++;
            union(parent,x_set,y_set);
        }
    }
    String str = "";
    str+="Minimum Spanning Tree :-\n";
    str+=printMST(mst);
    return str;
}

public void makeSet(int [] parent){
    for (int i = 0; i <vertices ; i++) {
        parent[i] = i;
    }
}

public int find(int [] parent, int vertex){
    if(parent[vertex]!=vertex)
        return find(parent, parent[vertex]);;
    return vertex;
}

public void union(int [] parent, int x, int y){
    int x_set_parent = find(parent, x);
    int y_set_parent = find(parent, y);
    parent[y_set_parent] = x_set_parent;
}

Answer 1

对于第一部分，它是Priority Queue或Heap的属性，可以对其进行排序根据我们的需要，max或min总是最重要的。

现在，将有一个名为Edge的自定义类。它不在您的代码中，但它将存在。第一部分是对优先级队列进行排序，以使权重最小的边缘位于顶部。这就是我们使用自定义比较器的原因。

PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));

当我们找到最小生成树时，我们需要具有最小权重的边，因此完成了。对于Java中的最小生成树，我也有类似的代码，请告知是否需要。

Answer 2

这是用于获得最小权重边缘的PriorityQueue

向PQ的构造函数声明的比较器用于基于]比较两个边。

权重以堆积PQ并获得最小边，因此，当您调用Poll()方法时，将>]

拾取顶点之间的最小边缘