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