java - 数组列表中的最小生成树

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/

您可能需要转换一些代码，但这应该是微不足道的。只寻找最便宜的边是一种解决方案，但可能并不总是会产生最小生成树。这样，您可能会意外地在图表中走“弯路”，使您的树比预期的大。