C Program to Implement Graph Using Adjacency List

1. Introduction

A graph consists of a set of nodes and edges connecting these nodes. One of the common ways to represent a graph in memory is by using an adjacency list. An adjacency list representation of a graph is an array of linked lists. The index of the array represents a vertex, and each element in its linked list represents the other vertices that form an edge with the vertex.

2. Program Overview

This program will:

1. Define a structure for the node of an adjacency list.

2. Initialize an adjacency list for a given number of vertices.

3. Provide functionalities to add an edge and display the list.

3. Code Program

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

// Define structure for a node in adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Number of vertices in the graph
int numVertices;
Node** adjacencyList;

// Function to initialize the adjacency list
void initializeGraph(int vertices) {
    numVertices = vertices;
    adjacencyList = malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; i++) {
        adjacencyList[i] = NULL;
    }
}

// Function to add edge
void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;

    // As it's an undirected graph, add edge from dest to src
    newNode = createNode(src);
    newNode->next = adjacencyList[dest];
    adjacencyList[dest] = newNode;
}

// Function to print the adjacency list
void printGraph() {
    for (int v = 0; v < numVertices; v++) {
        Node* temp = adjacencyList[v];
        printf("Vertex %d:", v);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    initializeGraph(5);
    addEdge(0, 1);
    addEdge(0, 4);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 3);
    printGraph();
    return 0;
}

Output:

Vertex 0: -> 4 -> 1
Vertex 1: -> 4 -> 3 -> 0
Vertex 2: -> 3
Vertex 3: -> 2 -> 1
Vertex 4: -> 1 -> 0

4. Step By Step Explanation

1. We begin by defining a structure Node for our adjacency list. This node holds the vertex number and a pointer to the next node.

2. The createNode function is used to initialize a new node with the given vertex value.

3. We maintain a global pointer, adjacencyList, which points to the array of linked lists for each vertex.

4. The initializeGraph function sets up the initial empty list for all vertices.

5. The addEdge function adds a vertex to the list of another vertex, thus indicating an edge between them. Since we are dealing with an undirected graph, we add connections in both directions.

6. printGraph prints out the adjacency list, allowing us to visually verify our graph structure.

7. The main function demonstrates initializing a graph, adding some edges, and then printing the resulting adjacency list.

This representation is space-efficient for sparse graphs but can become less efficient as the graph becomes denser.