Implementing Graphs with Adjacency Matrix and Adjacency List in C

In data structures, a graph is a very important model that can represent various relationships, such as social networks, maps, and transportation networks. Graphs can mainly be represented in two ways: the adjacency matrix and the adjacency list. This article will detail these two representation methods and provide C language code examples to help you understand.

1. Basic Concepts of Graphs

Here, we first define some concepts:

Graph: A collection of vertices (Vertex) and edges (Edge).
Undirected Graph: Edges have no direction, meaning the connection between one vertex and another is bidirectional.
Directed Graph: Edges have direction, pointing from one vertex to another.

2. Adjacency Matrix

An adjacency matrix is a way to represent a graph using a two-dimensional array. If there are n vertices, we use an n x n matrix, where matrix[i][j] equals 1 indicates that there is an edge from vertex i to vertex j, while 0 indicates no edge. For undirected graphs, since edges are bidirectional, matrix[i][j] equals matrix[j][i].

Example Code – Adjacency Matrix

The following is a method to implement a simple undirected graph using an adjacency matrix in C:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100

typedef struct {
    int matrix[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

// Initialize an empty graph
void initGraph(Graph *g, int vertices) {
    g->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->matrix[i][j] = 0; // Initialize no edges to 0
        }
    }
}

// Add edge
void addEdge(Graph *g, int start, int end) {
    g->matrix[start][end] = 1;
    g->matrix[end][start] = 1; // Undirected edge
}

// Print adjacency matrix
void printGraph(Graph *g) {
    for (int i = 0; i < g->numVertices; i++) {
        for (int j = 0; j < g->numVertices; j++) {
            printf("%d ", g->matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    Graph g;
    initGraph(&g, 5); // Create an empty graph with 5 vertices
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 4);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    printf("Neighbor adjacency matrix:\n");
    printGraph(&g);
    return EXIT_SUCCESS;
}

Code Explanation

We first define the maximum number of supported nodes as 100, and then use a structure to store the corresponding data.
A two-dimensional array simulates an numVertices x numVertices adjacency matrix.
The initialization function sets all values to zero, indicating that initially, no nodes are connected.
When adding an edge, we only need to modify two positions to reflect the undirected nature (i.e., symmetry).

Disadvantages:

Although effective, the memory overhead increases as the number of nodes increases, making it unsuitable for sparse graphs with a large number of vertices.

Adjacency List

In certain cases, the adjacency list can be more efficient than the adjacency matrix: it uses linked lists or dynamic arrays, where each node only retains the other nodes it is connected to. This is known as the adjacency list representation.

Example Code – Adjacency List

The following is a C implementation of a simple undirected graph using the linked list method:

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

// Define linked list item structure
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* head[MAX_VERTICES];
    int numVertices;
} Graph;

// Initialize an empty graph
void initGraph(Graph* graph, int vertices) {
    graph->numVertices = vertices;
    for (int v = 0; v < vertices; v++)
        graph->head[v] = NULL;
}

// Add edge
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->head[src];
    graph->head[src] = newNode;

    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->head[dest];
    graph->head[dest] = newNode;
}

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

int main() {
    Graph g;
    initGraph(&g, 5); // Create an empty graph with 5 vertices
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 4);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    printf("Adjacency list:\n");
    printGraph(&g);
    return EXIT_SUCCESS;
}

Code Explanation – Linked List Implementation

The above code initializes a graph using linked lists, where each vertex points to a list of its adjacent vertices. This method is more memory-efficient for sparse graphs.

Overall, for sparse storage in large-scale random scenarios, the adjacency list provides outstanding convenience and efficiency.

We hope this site can help you learn and understand the C programming language effectively.