Implementing Graph Structures in C: Adjacency Matrix and Adjacency List Representations

In computer science, a graph is an important data structure used to represent relationships between objects. A graph consists of vertices (or nodes) and edges. Depending on different requirements, we can use various methods to represent a graph. In this article, we will introduce two common methods for graph representation: the adjacency matrix and the adjacency list, and demonstrate them with C code.

1. Adjacency Matrix

1.1 Overview

An adjacency matrix is a two-dimensional array used to represent the vertices of a graph and their connection relationships. If there are n vertices, an n x n matrix is constructed, where each element matrix[i][j] indicates whether there is an edge from vertex i to vertex j. If an edge exists, the element is 1 (or the weight value); otherwise, it is 0.

1.2 Example of Adjacency Matrix

Assuming we have a simple undirected graph as follows:

    (0)   /   \ (1)---(2)

This graph contains 3 vertices, with edges (0, 1), (0, 2), and (1, 2). The corresponding adjacency matrix is as follows:

    0   1   2
0 | 0 | 1 | 1 |
---------------
1 | 1 | 0 | 1 |
---------------
2 | 1 | 1 | 0 |

1.3 C Language Implementation

Below is a segment of code implementing the adjacency matrix in C:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100 // Maximum number of vertices

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

// Initialize 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] = (i == j) ? -1 : -9999; // Use -9999 to indicate no edge
        }
    }
}

// Add edge
void addEdge(Graph* g, int startVertex, int endVertex) {
    g->matrix[startVertex][endVertex] = g->matrix[endVertex][startVertex] = 
        (g->matrix[startVertex][endVertex] == -9999) ? 
        +10 : +10; // Assume weight is 10
}

// 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 graph;
    initGraph(&graph, 3);
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 2);
    printGraph(&graph);
    return EXIT_SUCCESS;
}

2. Adjacency List

2.1 Overview

Compared to the adjacency matrix, the adjacency list is a more space-efficient method. It uses linked lists to store information about all other vertices connected to each vertex. This method is particularly effective for sparse graphs (i.e., graphs where most possible connections do not actually exist).

2.2 Example Explanation

Using the previously mentioned undirected graph as an example, its corresponding adjacency list can be expressed as follows:

Vertex 0: > [ ] > [ ]
Vertex 1: > [ ] > [ ]
Vertex 2: > [ ] > [ ]

Here, each line lists the information of the nodes connected to the node represented by the index of that line.

2.3 C Language Implementation

Below is a segment of code in C that demonstrates how to construct a simple adjacency list using linked lists:

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

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

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

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

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

// Add edge
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    // Since this is undirected, also add the reverse path.
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Print graph
void printGraph(Graph* g) {
    for(int v = 0; v < g->numVertices; v++) {
        Node* temp = g->adjLists[v];
        printf("Adjacency list of vertex %d: ", v);
        while(temp) {
            printf("%d → ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Graph* g = createGraph(3);
    addEdge(g, 0, 1);
    addEdge(g, 0, 2);
    addEdge(g, 1, 2);
    printGraph(g);
    return EXIT_SUCCESS;
}

3. Conclusion

This article introduced two common and practical methods for implementing and representing graph structures in C: adjacency matrix and adjacency list. For densely connected small networks, the adjacency matrix can be chosen; while for sparse networks, the adjacency list is recommended, as it can utilize memory resources more efficiently. In practical applications, selecting the appropriate data structure based on specific situations will greatly enhance program performance and maintainability.