C Program to Implement Adjacency List

This is a C Program to implement Adjacency List. An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists. Following is adjacency list representation of the above graph.

Here is source code of the C Program to Implement Adjacency List. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

// A C Program to demonstrate adjacency list representation of graphs

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

// A structure to represent an adjacency list node

```
struct AdjListNode {
```
```
    int dest;
```
```
    struct AdjListNode* next;
```
```
};
```
```
 
```

// A structure to represent an adjacency liat

```
struct AdjList {
```

    struct AdjListNode *head; // pointer to head node of list

```
};
```
```
 
```

// A structure to represent a graph. A graph is an array of adjacency lists.

// Size of array will be V (number of vertices in graph)

```
struct Graph {
```
```
    int V;
```
```
    struct AdjList* array;
```
```
};
```
```
 
```

// A utility function to create a new adjacency list node

struct AdjListNode* newAdjListNode(int dest) {

    struct AdjListNode* newNode = (struct AdjListNode*) malloc(

            sizeof(struct AdjListNode));

```
    newNode->dest = dest;
```
```
    newNode->next = NULL;
```
```
    return newNode;
```
```
}
```
```
 
```

// A utility function that creates a graph of V vertices

```
struct Graph* createGraph(int V) {
```

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

```
    graph->V = V;
```
```
 
```

    // Create an array of adjacency lists.  Size of array will be V

    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

```
 
```

    // Initialize each adjacency list as empty by making head as NULL

```
    int i;
```
```
    for (i = 0; i < V; ++i)
```
```
        graph->array[i].head = NULL;
```
```
 
```
```
    return graph;
```
```
}
```
```
 
```
```
// Adds an edge to an undirected graph
```

void addEdge(struct Graph* graph, int src, int dest) {

    // Add an edge from src to dest.  A new node is added to the adjacency

    // list of src.  The node is added at the begining

    struct AdjListNode* newNode = newAdjListNode(dest);

    newNode->next = graph->array[src].head;

```
    graph->array[src].head = newNode;
```
```
 
```

    // Since graph is undirected, add an edge from dest to src also

```
    newNode = newAdjListNode(src);
```

    newNode->next = graph->array[dest].head;

```
    graph->array[dest].head = newNode;
```
```
}
```
```
 
```

// A utility function to print the adjacenncy list representation of graph

```
void printGraph(struct Graph* graph) {
```
```
    int v;
```
```
    for (v = 0; v < graph->V; ++v) {
```

        struct AdjListNode* pCrawl = graph->array[v].head;

        printf("\n Adjacency list of vertex %d\n head ", v);

```
        while (pCrawl) {
```

            printf("-> %d", pCrawl->dest);

```
            pCrawl = pCrawl->next;
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
}
```
```
 
```

// Driver program to test above functions

```
int main() {
```

    // create the graph given in above fugure

```
    int V = 5;
```

    struct Graph* graph = createGraph(V);

```
    addEdge(graph, 0, 1);
```
```
    addEdge(graph, 0, 4);
```
```
    addEdge(graph, 1, 2);
```
```
    addEdge(graph, 1, 3);
```
```
    addEdge(graph, 1, 4);
```
```
    addEdge(graph, 2, 3);
```
```
    addEdge(graph, 3, 4);
```
```
 
```

    // print the adjacency list representation of the above graph

```
    printGraph(graph);
```
```
 
```
```
    return 0;
```
```
}
```

Output:

$ gcc AdjacencyList.c
$ ./a.out
 
Adjacency list of vertex 0
 head -> 4-> 1
 
 Adjacency list of vertex 1
 head -> 4-> 3-> 2-> 0
 
 Adjacency list of vertex 2
 head -> 3-> 1
 
 Adjacency list of vertex 3
 head -> 4-> 2-> 1
 
 Adjacency list of vertex 4
 head -> 3-> 1-> 0

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Skip List

» Next - C Program to Implement Hash Tables Chaining with Linked Lists

Related Posts:

Recommended Articles: