Adjacency list representation of a graph


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: Adjacency list representation of a graph

Hybrid View

  1. #1
    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. #2
    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. #3
    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. #4
    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. #5
    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!

Similar Threads

  1. Replies: 0
    Last Post: 10-27-2005, 01:16 AM
  2. Problem with linked lists and iterators
    By white94cam in forum C++
    Replies: 2
    Last Post: 03-31-2005, 12:02 AM
  3. recursion problem
    By Steven in forum Database
    Replies: 1
    Last Post: 06-21-2002, 10:16 AM
  4. Replies: 2
    Last Post: 11-09-2001, 09:44 PM
  5. ListBot Going Out of Business
    By Larry Rebich in forum vb.announcements
    Replies: 1
    Last Post: 06-28-2001, 02:22 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center