有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

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) 个答案