Adjacency List & Prim's Algo

[s.johns]

First, if anyone is willing to help one on one off the forum via phone/chat, please see this post: http://www.codeguru.com/forum/showthread.php?t=450720

As an overview, I need to use an adjacency list/matrix to use Prim's algorithm to find a minimum spanning tree and total weight.

This is an UNdirected graph:

loaf berry(18) fig(5) carrot(6)
orange jack(25) salad(21) berry(10)
carrot fig(2) loaf(6) salad(12)
ivy jack(16) banana(24)
salad carrot(12) orange(21) pizza(28)
pizza jack(18) salad(28) fig(29)
berry orange(10) fig(14) loaf(18) grape(20)
fig berry(14) carrot(2) loaf(5) pizza(29)
grape berry(20) banana(17) jack(10)
jack grape(10) pizza(18) orange(25) ivy(16)
banana ivy(24) grape(17)

so loaf goes to berry, fig, and carrot, with a distance of 18, 5, and 6.

orange is the vertex.

The first step is to setup and store everything inside an adjacency list/matrix.

I have some code for Prim's algo already, but I am not sure how to start this with an adjacency list.

Here's the example output of the input quoted above:

orange -> berry
berry -> fig
fig -> carrot
fig -> loaf
carrot -> salad
berry -> grape
grape -> jack
jack -> ivy
grape -> banana
jack -> pizza

weight: 24

[s.johns]

Thanks for the help

I would also need to store the name of the vertex too, right?

So adjacencyList is a map that contains an object of class Edge, right?

[s.johns]

Thanks for the tip about the Map class

How do I initialize the adjacencyList though? When I try to run clear() on the adjacencyList, it comes up saying " variable adjacencyList might not have been initialized"

import java.io.*;
import java.util.*;

public class Primsmap
{
	public static void main(String args[])
	{
		// initiate new adjacencyList
		Map<Vertex, List<Edge>> adjacencyList;

		adjacencyList.clear();
	}
}

class Edge{
  // name of vertex
  Vertex to;
  // stores the weight
  int weight;
}

class Vertex{
  // stores the name the vertex points to
  String name;
}

[keang]

How do I initialize the adjacencyList though? When I try to run clear() on the adjacencyList, it comes up saying " variable adjacencyList might not have been initialized"

The clue is in the error message. You have declared a variable of type Map but you haven't actually created a map object yet. You need to do something like:

Map<Vertex, List<Edge>> adjacencyList = new HashMap<Vertex, List<Edge>>();

[s.johns]

Thanks keang!