Graph Structures in C Language: Adjacency Matrix and Adjacency List

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 store graph data. In this article, we will detail two common graph storage methods: the adjacency matrix and the adjacency list, and demonstrate them with C language code.

1. Adjacency Matrix

1.1 Overview

An adjacency matrix is a two-dimensional array used to represent the connection relationships between vertices in a graph. If there are n vertices, we need an n x n matrix. For an undirected graph, if there is an edge from vertex i to vertex j, then <span>matrix[i][j] = 1</span>, otherwise it is 0; for a directed graph, it is set to 1 only when there is an edge from i to j.

1.2 Advantages and Disadvantages

  • Advantages:

    • Simple and easy to understand, suitable for dense graphs (i.e., graphs with many edges).
    • Can quickly determine if there is an edge between two vertices (O(1) time complexity).

  • Disadvantages:

    • High space complexity; for sparse graphs (i.e., graphs with few edges), it wastes a lot of space.

1.3 Example Code

Below is an example code implementing an adjacency matrix in C language:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 10 // 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] = 0; // Initialize to 0
        }
    }
}

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

// 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, MAX_VERTICES);
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 2);
    printf("Adjacency Matrix:\n");
    printGraph(&graph);
    return EXIT_SUCCESS;
}

2. Adjacency List

2.1 Overview

An adjacency list is a more space-efficient data structure that uses linked lists to store other vertices connected to each vertex. Each element contains a pointer to the next connected node, allowing for an efficient representation of sparse graphs.

2.2 Advantages and Disadvantages

  • Advantages:

    • Space-efficient, very effective for sparse graphs.
    • Dynamic addition and deletion of nodes are more flexible.

  • Disadvantages:

    • Determining if two nodes are connected requires traversing the linked list, with a time complexity of O(V), where V is the number of connections for that node.

2.3 Example Code

Below is an example code implementing an adjacency list in C language:

#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) {
    // Add edge from src to dest
    Node* newNode= createNode(dest);
    newNode->next= graph->adjLists[src];
    graph->adjLists[src]= newNode;
    // Add reverse edge from dest to src (undirected)
    newNode= createNode(src);
    newNode->next= graph->adjLists[dest];
    graph->adjLists[dest]= newNode;
}

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

int main() {
    Graph *graph=createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 4);
    addEdge(graph, 4, 3);
    printGraph(graph);
    return EXIT_SUCCESS;
}

3. Conclusion

In this article, we introduced two common methods for representing graph data structures: the adjacency matrix and the adjacency list. Each method has its own advantages and disadvantages, and in practical applications, we can choose the appropriate data structure based on specific situations to optimize performance and resource utilization. We hope this article helps you better understand graph data structures in C language!

Leave a Comment