Creating Adjacency List

Question

I am having problem to create adjacent list in correct order. I think there is some problem in CreateAdjList(void)method. I run out of ideas. Please give me some tips. Basically I have graph and creating Adjacency list on connected edges.

#include <stdio.h>
#include <stdlib.h>
#define maxV 100                               
typedef struct graphnode{                        
    int vertex;
    struct graphnode *next;
}Node;
Node **node;                             
Node **nodeT; 

FILE *fp;

void initial(int nv);                            
void AdjList(void);                              
void PrintAdjList(int nv);                           


int main()
{
    int nv;

    fp= fopen("input.txt","r");
    fscanf(fp,"%d",&nv);
    initial(nv);
    CreateAdjList();
    PrintAdjList(nv);

    return 0;
}



void initial(int nv)
{
    int i;
    node = new Node *[maxV];

    for(i=1;i<=nv;i++){
        node[i] = (Node *)malloc(sizeof(Node));
        node[i]->next=NULL;


    }

}


//CREATE ADJACENCY  LIST - 
void CreateAdjList(void)
{
    int v1,v2;
    Node *ptr;

while(fscanf(fp,"%d%d",&v1,&v2)!=EOF){

        ptr = (Node *)malloc(sizeof(Node));
        ptr->vertex = v2;
        ptr->next = node[v1]->next;    //Problem could be here
        node[v1]->next = ptr;

    }

    fclose(fp);
}




//PRINT LIST
void PrintAdjList(int nv)
{
    int i;
    Node *ptr;

    for(i=1; i<=nv; i++){
        ptr = node[i]->next;
        printf("    node[%2d]  ",i);
        while(ptr != NULL){
            printf("  -->%2d", ptr->vertex);
            ptr=ptr->next;
        }
        printf("\n");
    }
    printf("\n");

}

ACTUAL PROGRAM OUTPUT - WRONG ORDER . I attached output list in printed in revere way.

Input:

8
1 2
2 3
2 5
2 6
3 4
3 7
4 3
4 8
5 1
5 6
6 7
7 6
7 8
8 8
0 0

Expected Output:
Adjacency list represenation:
1: 2 
2: 3 5 6 
3: 4 7 
4: 3 8 
5: 1 6 
6: 7 
7: 6 8 
8: 8

My actual output is displayed wrong order. If you look at node the correct order should be 2 ->3->6->5

 node[ 1]    --> 2
 node[ 2]    --> 6  --> 5  --> 3
 node[ 3]    --> 7  --> 4
 node[ 4]    --> 8  --> 3
 node[ 5]    --> 6  --> 1
 node[ 6]    --> 7
 node[ 7]    --> 8  --> 6
 node[ 8]    --> 8

Answer 1

Adjacency List can represent a Graph in a very efficient way. It maintains a vertex-indexed array of the list to represent the edges and vertices of the graph as shown in below figure:

Array of ArrayList

An array of ArrayList can be used to implement the Adjacency List of the Graph. Below is the program depicting the usage of Array of ArrayList.

package com.vaibhav.graph;

import java.util.ArrayList;

public class Graph {
    private final int V;
    private ArrayList<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new  ArrayList[V];
        for(int i=0; i < V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
}

It have been beautifully explained here : Click Here

Answer 2

Had a crack at this because it's been a while since I've done C :)

What you're after is something more along the lines of below - note, there were several errors which I can't see how it would have worked. With the '0 0' at the end of the file, and the fact that you were using 1->nv in the loops, there never would have been a node[0] element and hence would always have failed.

In my example, I keep the array sparse (only allocating nodes that actually exist), while satisfying the other conditions. I also don't care what order they come in, so that input file could be unordered. Also note that the print method may need to be updated if the file data had sparse data (ie. first number was 10, and it was missing anything like '9 x').

void initial(int nv)
{
    node = (Node **)malloc(maxV * sizeof(Node *));
}

//CREATE ADJACENCY  LIST - 
void CreateAdjList(void)
{
    int v1,v2;
    Node *ptr;

    while(fscanf(fp,"%d %d",&v1,&v2)!=EOF){

        ptr = (Node *)malloc(sizeof(Node));
        ptr->vertex = v2;

        if (node[v1]==NULL) {
            node[v1] = (Node *)malloc(sizeof(Node));
            node[v1]->vertex = v1;
            node[v1]->next = NULL;
        }

        Node *next = node[v1];
        while (next->next!=NULL)
            next = next->next;

        next->next = ptr;

        //ptr->next = &(*(node[v1])->next);    //Problem could be here
        //node[v1]->next = ptr;
    }

    fclose(fp);
}