配列リストからの最小スパニングツリー

Question

ArrayListから最小スパニングツリーを見つけることができるのだろうかと思います。私はちょうど頂点のそれぞれから最小数を見つけることについて考えていたが、私はあまりわからなかった

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.ArrayList; 
import java.util.Scanner; 


public class GraphReading 
{ 
public static void main(String[] args) throws FileNotFoundException 
{ 
    File f= new File("Bridges.txt"); 
    Scanner sc= new Scanner(f); 

    ArrayList < ArrayList<Integer> > Vertices = new ArrayList<>(); 

    while(sc.hasNext()) 
    { 
     String Line =  sc.nextLine(); 
     String numbers[] = Line.split(" "); 

     ArrayList<Integer> List = new ArrayList<>(); 
     for(int i=0;i < numbers.length ;i++) 
     { 
       if(numbers[i].equals("")==false) 
        List.add( Integer.parseInt(numbers [i])); 
     } 
     Vertices.add(List); 
    } 
    printAllvertices(Vertices); 
} 
public static void printAllvertices( ArrayList < ArrayList<Integer> > Vertices ) 
{ 
    for(int i=0;i< Vertices .size();i++) 
    { 
     System.out.print("Vertice "+i+ " has "); 
      ArrayList<Integer> List = Vertices.get(i); 
      for(int j=0;j<List.size();j++) 
      { 
       System.out.print(List.get(j)+" "); 
      } 
      System.out.println(); 




    } 

} 

} 

それは必ずしも私もそれを望んでいたように動作します：

この

は、私が現在持っているものです。

Answer 1

もちろん可能です！私はPRIMのアルゴリズムを使用してそれを行う方法についての素晴らしい文書を持っているこのサイトを見つけました。

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

あなたは周りのコードのビットを変換する必要があるかもしれませんが、それは些細でなければなりません。もっとも安いエッジを探すことは解決策ですが、常に最小スパニングツリーになるとは限りません。こうすることで、意図せずにツリーを大きくして、誤ってグラフに「迂回路」を作ってしまう可能性があります。