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

问题描述 投票:1回答:2

谁能向我解释此代码的这两部分,这是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;
}
java data-structures minimum-spanning-tree
2个回答
1
投票
对于第一部分,它是Priority Queue或Heap的属性,可以对其进行排序根据我们的需要,max或min总是最重要的。

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

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

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

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

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

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

拾取顶点之间的最小边缘

© www.soinside.com 2019 - 2024. All rights reserved.