How to Implement Graph in C: Simple Adjacency List Example

To implement a graph in C, use an adjacency list or adjacency matrix to store edges. The adjacency list uses arrays of linked lists to represent connections efficiently, especially for sparse graphs.

Syntax

A graph in C can be represented using an adjacency list with the following components:

• struct Node: Represents a linked list node for neighbors.
• struct Graph: Contains an array of pointers to adjacency lists and the number of vertices.
• Functions: To create the graph, add edges, and display connections.

c

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

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

Example

This example shows how to create a graph with 4 vertices, add edges, and print the adjacency list representation.

c

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

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

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

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

// Create a graph
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;
}

// Add edge
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;

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

// Print graph
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 graphs in C include:

• Not initializing adjacency lists to NULL, causing undefined behavior.
• Forgetting to add edges in both directions for undirected graphs.
• Memory leaks by not freeing allocated nodes.
• Mixing up source and destination vertices when adding edges.

c

/* Wrong: Not initializing adjacency lists */
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    // Missing initialization to NULL here
    return graph;
}

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

Quick Reference

Graph Implementation Tips:

• Use adjacency lists for efficient memory with sparse graphs.
• Initialize all adjacency list heads to NULL.
• For undirected graphs, add edges both ways.
• Always check malloc return values in production code.
• Free memory after use to avoid leaks.

Key Takeaways

Use adjacency lists with linked nodes to represent graphs efficiently in C.

Always initialize adjacency list pointers to NULL before adding edges.

Add edges in both directions for undirected graphs to maintain symmetry.

Avoid memory leaks by freeing allocated nodes when done.

Test your graph by printing adjacency lists to verify connections.