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

advertisement

advertisement

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

**Related Posts:**

- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Check Programming Books