Write a program, which given inputs as integer pairs representing edges, creates an adjacency list for a graph.

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>
#include <stdlib.h>

#define V 8 /* Number of vertices */
typedef struct node *LINK;
struct node {
    int v;
    LINK next;
};

LINK newnode(int v, LINK next){
    LINK x = malloc(sizeof *x);
    x -> v = v;
    x -> next = next;
    return x;
}

int main(void){
    int i, j;
    LINK adj[V];
    for(i = 0; i < V; i++)
        adj[i] = NULL;  /* initialize each to link to a empty list */
    /* now read in edges as vertex pairs */
    printf("\nEnter vertex pairs - Press  to end\n");
    while(scanf("%d%d", &i, &j) == 2) {
        adj[j] = newnode(i, adj[j]);
        adj[i] = newnode(j, adj[i]);
    }

    /* display list */
    LINK tmp;
    for (i = 0; i < V; i++){
        printf("Vertex %2d: ", i);
        tmp = adj[i];
        while(tmp != NULL){
            printf("%3d", tmp->v);
            tmp = tmp->next;
        }
        printf("\n");
    }

    return 0;
}

When you compile and execute the above program it produces the following result on Linux:

Enter vertex pairs - Press  to end
0 1 3 4 6 7 9 8 12 4 5 0 2 4 6 17
Vertex  0:   5  1
Vertex  1:   0
Vertex  2:   4
Vertex  3:   4
Vertex  4:   2 12  3
Vertex  5:   0
Vertex  6:  17  7
Vertex  7:   6

Brief Explanation

  • An adjacency list is an array of linked lists, and is another commonly used representation of graphs.
  • The data structure consists of a linked list for each vertex, with a node for each vertex that is connected to that vertex.
  • For an undirected graph, if there is a node for j in i's linked list, then there must also be a node for i in j's linked list. e.g From the result of the program, considering the vertex pair 3-4, node 4 is found in Vertex 3 while node 3 is found in Vertex 4.

Add comment


Security code
Refresh