Minimum Spanning Tree von Array-Liste

Question

Ich frage mich, ob es möglich ist den minimalen Spanning Tree von einem Arraylist zu finden.

Das ist, was ich habe zur Zeit:

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(); 




    } 

} 

} 

ich gerade von jedem des Scheitel Denken wurde die Mindestanzahl zu finden, aber ich war nicht sicher, dass unbedingt so, wie ich es wollte auch funktionieren würde.

Answer 1

Sicher Sie können! Ich habe diese Seite gefunden, die einige schöne Dokumentation über die Verwendung von PRIMs Algorithmus enthält.

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

Sie könnten ein Stück Code konvertieren müssen um, aber das sollte trivial sein. Die Suche nach nur den billigsten Kanten ist eine Lösung, führt aber möglicherweise nicht immer zum minimalen Spannbaum. Auf diese Weise könnten Sie versehentlich "Umwege" in Ihrem Diagramm machen, wodurch Ihr Baum größer als beabsichtigt wird.