How to Implement Adjacency List in C: Simple Guide

To implement an adjacency list in C, use an array of pointers where each pointer refers to a linked list of nodes representing connected vertices. Each node contains the vertex number and a pointer to the next node, allowing efficient storage of graph edges.

Syntax

An adjacency list in C typically uses a struct for list nodes and an array of pointers to these nodes. Each node stores the connected vertex and a pointer to the next node in the list.

• struct Node: Represents a linked list node with vertex and next pointer.
• struct Graph: Contains the number of vertices and an array of adjacency lists.
• createNode(int v): Creates a new node for vertex v.
• addEdge(Graph*, int src, int dest): Adds an edge from src to dest.

c

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

struct Node* createNode(int v);
void addEdge(struct Graph* graph, int src, int dest);

Example

This example creates a graph with 4 vertices and adds edges between them. It then prints the adjacency list showing which vertices are connected.

c

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

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // For undirected graph, add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        struct Node* temp = graph->adjLists[v];
        printf("Vertex %d: ", v);
        while (temp) {
            printf("-> %d ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);
    return 0;
}

Output

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

Common Pitfalls

Common mistakes when implementing adjacency lists in C include:

• Not initializing the adjacency list array to NULL, causing undefined behavior.
• Forgetting to add edges in both directions for undirected graphs.
• Memory leaks by not freeing allocated nodes after use.
• Incorrect pointer assignments leading to lost nodes or corrupted lists.

c

/* Wrong: Not initializing adjacency lists */
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = 3;
graph->adjLists = malloc(3 * sizeof(struct Node*));
// Missing initialization to NULL

/* Right: Initialize all adjacency lists to NULL */
for (int i = 0; i < graph->numVertices; i++) {
    graph->adjLists[i] = NULL;
}

Quick Reference

• Use struct Node for linked list nodes storing vertex and next pointer.
• Use an array of struct Node* for adjacency lists.
• Initialize all adjacency list heads to NULL.
• Add edges by prepending new nodes to the list.
• For undirected graphs, add edges in both directions.

Key Takeaways

Use an array of linked lists to represent adjacency lists in C.

Initialize adjacency list pointers to NULL before adding edges.

Add edges by creating new nodes and linking them at the list head.

For undirected graphs, add edges in both directions.

Always manage memory carefully to avoid leaks.