谁能向我解释此代码的这两部分,这是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;
}
现在,将有一个名为Edge的自定义类。它不在您的代码中,但它将存在。第一部分是对优先级队列进行排序,以使权重最小的边缘位于顶部。这就是我们使用自定义比较器的原因。
PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));
当我们找到最小生成树时,我们需要具有最小权重的边,因此完成了。对于Java中的最小生成树,我也有类似的代码,请告知是否需要。
向PQ的构造函数声明的比较器用于基于]比较两个边。
权重以堆积PQ并获得最小边,因此,当您调用Poll()
方法时,将>]
拾取顶点之间的最小边缘