Minimum Spanning tree from array list

Question

I'm wondering if it's possible to find the minimum spanning tree from an ArrayList.

This is what I currently have:

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




    }

}

}

I was thinking about just finding the minimum number from each of the vertices but I wasn't too sure that would necessarily work the way I wanted it too.

Thoma · Accepted Answer · 2017-04-30 20:38:35Z

1

Sure you can! I found this site that has some nice documentation on how to do it using PRIM's algorithm.

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

You might need to convert a bit of code around, but that should be trivial. Looking for just the cheapest edges is a solution, but may not always result in the minimum spanning tree. This way you might accidentally make "detours" in your graph, making your tree larger than intended.

answered Apr 30, 2017 at 20:38

Thoma

892 silver badges4 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Thoma Over a year ago

Could you mark the answer as "answered" by pressing the green check if it really helped? It would help other users who have the same question, as you. :-)

Collectives™ on Stack Overflow

Minimum Spanning tree from array list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related