java Krushkal算法。我的代码有什么问题?
我尝试创建一个比较器,并重写了基于权重的比较排序方法。在unionFind()函数中,我检查源和目标的最顶层父级是否相同(我这样做是为了检查是否存在循环)。如果最顶端的父级相同,则函数unionFind()将返回true,否则将返回false。我的代码有什么问题?我不明白
import java.util.*;
import java.io.*;
// comparator to sort on the basis of weights
class minCom implements Comparator<Edge>
{
@Override
public int compare(Edge o1, Edge o2)
{
if(o1.weight < o2.weight)
return -1;
else if(o1.weight > o2.weight)
return 1;
else
return 0;
}
}
class Edge
{
int src;
int dest;
int weight;
public Edge(int src,int dest,int weight)
{
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
public class Solution {
public static boolean unionFind(int parent[],int src,int dest)
{
int currentSrc = src;
while(parent[currentSrc]!=currentSrc)
{
currentSrc = parent[currentSrc];
}
int currentDest = dest;
while(parent[currentDest]!=currentDest)
{
currentDest = parent[currentDest];
}
if(currentSrc == currentDest)
return true;
else
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
int E = sc.nextInt();
/* Write Your Code Here
* Complete the Rest of the Program
* You have to take input and print the output yourself
*/
Edge input[] = new Edge[E];
Edge output[] = new Edge[V-1];
for(int i=0;i<E;i++)
{
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
Edge myedge = new Edge(a,b,c);
input[i] = myedge;
}
Arrays.sort(input,new minCom());
int parent[] = new int[V];
for(int i=0;i<V;i++)
parent[i] = i;
int count = 0;
int i=0;
while(count < V-1)
{
int src = input[i].src;
int dest = input[i].dest;
if(!unionFind(parent,src,dest))
{
output[count] = input[i];
parent[dest] = src;
count++;
}
i++;
}
int result = 0;
for( i=0;i<output.length;i++)
{
result += output[i].weight;
}
System.out.println(result);
}//for
}
共 (0) 个答案