C Program to Implement Graph Using Adjacency Matrix

1. Introduction

A graph is a collection of nodes (or vertices) and edges. One of the primary ways to represent a graph in memory is by using an adjacency matrix. An adjacency matrix is a 2D array of size V x V where V is the number of vertices in a graph. The value m[i][j] is 1 if there's an edge between vertex i and vertex j, otherwise 0.

2. Program Overview

This program will:

1. Initialize an adjacency matrix for a given number of vertices.

2. Provide functionalities to add an edge and display the matrix.

3. Code Program

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

// Define maximum number of vertices in the graph
#define MAX_VERTICES 5

// 2D array for storing adjacency matrix
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

// Initialize the adjacency matrix to zero
void initializeGraph() {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            adjacencyMatrix[i][j] = 0;
        }
    }
}

// Add edge into the matrix
void addEdge(int start, int end) {
    // As it's an undirected graph, we'll add both edges
    adjacencyMatrix[start][end] = 1;
    adjacencyMatrix[end][start] = 1;
}

// Display the adjacency matrix
void displayMatrix() {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", adjacencyMatrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    initializeGraph();
    addEdge(0, 1);
    addEdge(0, 3);
    addEdge(1, 3);
    addEdge(2, 4);
    displayMatrix();
    return 0;
}

Output:

0 1 0 1 0
1 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0

4. Step By Step Explanation

1. We started by defining the maximum number of vertices and a 2D array called adjacencyMatrix to hold the graph representation.

2. The initializeGraph function sets every element of the adjacency matrix to zero, indicating there are no edges between any vertices initially.

3. The addEdge function updates the matrix by marking the intersection of the two vertices with a 1, indicating an edge between them. Since it's an undirected graph, both m[i][j] and m[j][i] are set to 1.

4. The displayMatrix function simply prints the current adjacency matrix.

5. In the main function, we initialize the graph, add some edges, and then display the resulting adjacency matrix.

By the end of this program, one can visually inspect the adjacency matrix and determine which vertices are connected. This representation is space-efficient for dense graphs but can be space-consuming for sparse graphs.