Finding a Minimum Spanning Tree from an Adjacency List where the Adjacency List is in a string array using Prims Algorithm

Question

So I need some help coming up with a way to find a Minimum spanning tree. Suppose I have my graph in the form of an adjacency list:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

The first letter tells which node you are looking at, and the number tells how many connections to any other node there are. For example, A has two connections - one each to B and I. After that, the number that follows the letters simply tell the weight of an edge. B has weight 12 and I has weight 25. So I had originally planned to represent this entire thing as a String array called Graph[8]. Each line would be a different slot in the array. I am having difficulties figuring out how to accomplish this with either Prims or Kruskalls algorithm.

Answer 1

This isn't a direct answer to your question per-say (seems like you're doing schoolwork), but I think it will help you get started. Why not create a data structure that more closely matches your mental model and build up from there?

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}