DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Adjacency list representation of a graph

1. Registered User
Join Date
Nov 2005
Posts
3

## 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.

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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.

3. Registered User
Join Date
Nov 2005
Posts
3
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.

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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
}

5. Registered User
Join Date
Nov 2005
Posts
3
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!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.