Thread: adjacency list question

  1. #1
    Registered User lord's Avatar
    Join Date
    Dec 2006
    Posts
    61

    adjacency list question

    For a current project I am creating I decided the best way to implement the code would be through an adjacency list. I am just simply confused on what the structs would look like and how to create the reference. For example,

    Code:
    [Vertex] [Adjacent Vertices]
         A             C,B,E
         B             C
         C             A,B,E
         D             E
         E             A,C
    
    A->C->B->E
    |
    B->C
    |
    C->A->B->E
     
    ...etc...
    I have one struct for all the vertices and another struct for the adjacent vertices. I need to be able to travel from vertex a to the adjacent vertex b, for example, but b should be a reference to the vertex node b so that I can "jump" from the adjacent vertice chain to the vertex chain.

    My structs are setup as follows:

    Code:
    struct adj_node
    {  
          char vertex;
           adj_node* path; //for the adjacency vertex chain (A->C->B->E)
    };
    
    struct node 
    {
        char vertex;
        adj_node* next; 
        node* down; //to travel down the vertex chain (A-B-C)
    };
    So what I am wondering is do my structs look setup correctly and how would I do the jumping from an adajcency vertex to a vertex?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Why wouldn't you just have nodes, which have a char vertex and a node** next which would be a dynamic array of pointers? You would then have that node[0] (and perhaps node[1], etc.) would be pointers to adjacent nodes; following a path might then look like current = current->next[0], or the like. You would also want int number_of_paths or something so that you know how big your next array is.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  4. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  5. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM