# Adjacency list representation of a graph

• 11-22-2005, 05:14 PM
ThePrise
Adjacency list representation of a graph
Hey everyone,
I'm starting to code a directed graph using an adjacency list and I'm running into a little trouble. I understand the concepts of the adjacency list structure, but I cant write seem to figure out how to code one. So far I'm using two doubly linked lists for storing the vertices and edges, and each is in its own class (I thought this would come in handy when later coding traversals in the graph). In the graph class, I'm thinking that an array list would work to store the adjacent vertices (each value in the array storing a list of vertices which are adjacent). However, if this is right then I'm not sure what to do with the edges, and how to make each edge know which vertices it is connecting.. In general, I'm looking for comments/advice on this type of graph implementation. Anything will help. Thanks a lot.
• 11-22-2005, 07:48 PM
nspils
Each "vertex node" has a field which is an ArrayList. The ArrayList is a list of the "edge nodes" for which the particular vertex is a starting point of an edge which terminates at that "edge node".

To traverse, you iterate down the "vertex list" to the starting point of interest, then out on the member "edgeList" to get to the nodes which are directly connected to that vertex.
• 11-22-2005, 09:16 PM
ThePrise
Thanks a lot. Let me just make sure I understand this; I should have a class for vertex nodes, and a class for edges, and a class for the graph itself. In the graph class, there's an Array List. Each value of the Array List (ArrayList[1], ArrayList[2], etc.) represents a vertex node, and contains a list of edges which begin that that vertex.
Or does each value in the array list represent a vertex and contain a list of vertices which are connected to that vertex?
When I reference edges, I mean the directed paths that lead between nodes in the graph.

ps. I'm not trying to be annoying or ask for too much here, but any pseudo-code or an actual example of something like this would be awesome if anyone knows where i can find it.
• 11-23-2005, 12:33 AM
nspils
I am familiar with the terminology you are using.

My suggestion is that, as you said, the graph class has a VertexList of VertexNode objects which have at least two data members: some means to identify the object (if you want) plus an "EdgeList" - an ArrayList of "EdgeNodes", one for each "edge" which radiates from the particular Vertex. The EdgeNode can store data such as weight (if you have any) and its name can just be some "edge" designation.

Perhaps a structure like this ...

public class SparseGraph
{
private static int count;
private ArrayList<VertexNode> myVertexList;

private static class VertexNode
{
private int countEdges;
private int nodeID;
private ArrayList<EdgeNode> myEdgeList;

and so on ...
}

private static class EdgeNode
{
private int nameEdge;
private int edgeWeight;
private double edgeWeight2;

and so on ...
}

public SparseGraph() { ... }
and so on
}
• 11-23-2005, 01:53 PM
ThePrise
Alright. This gives me a much better idea of how to get this off the ground. Thanks a lot, and if I have more questions I'll be sure to ask! :D