C Program to Implement a Graph Using Adjacency Matrix

Introduction

A graph is a data structure that consists of a set of vertices (nodes) and a set of edges that connect pairs of vertices. One of the common ways to represent a graph 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 the graph. The element matrix[i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

Example:

• Graph Structure:

  1 - 2 | | 3 - 4 

• Adjacency Matrix:

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

Problem Statement

Create a C program that:

• Implements a graph using an adjacency matrix.
• Allows the user to add edges to the graph.
• Displays the adjacency matrix of the graph.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Define the Graph Structure: Use a 2D array to represent the adjacency matrix.
3. Implement Functions to Add Edges and Display the Matrix:

• Add an edge between two vertices.
• Display the adjacency matrix.

4. Create a Main Function: Allow the user to input the number of vertices, add edges, and display the adjacency matrix.

C Program to Implement a Graph Using Adjacency Matrix

#include <stdio.h> #include <stdlib.h> // Function to initialize the adjacency matrix to 0 void initializeMatrix(int matrix[][10], int vertices) { for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { matrix[i][j] = 0; } } } // Function to add an edge to the graph void addEdge(int matrix[][10], int src, int dest) { matrix[src][dest] = 1; matrix[dest][src] = 1; // If the graph is undirected } // Function to display the adjacency matrix void displayMatrix(int matrix[][10], int vertices) { printf("\nAdjacency Matrix:\n"); for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { printf("%d ", matrix[i][j]); } printf("\n"); } } int main() { int vertices, edges, src, dest; // Input the number of vertices in the graph printf("Enter the number of vertices: "); scanf("%d", &vertices); // Declare the adjacency matrix int matrix[10][10]; // Initialize the adjacency matrix initializeMatrix(matrix, vertices); // Input the number of edges in the graph printf("Enter the number of edges: "); scanf("%d", &edges); // Input the edges and add them to the graph for (int i = 0; i < edges; i++) { printf("Enter edge (source destination): "); scanf("%d %d", &src, &dest); addEdge(matrix, src, dest); } // Display the adjacency matrix displayMatrix(matrix, vertices); return 0; // Return 0 to indicate successful execution } 

Explanation

Function to Initialize the Adjacency Matrix

• The initializeMatrix function initializes all elements of the adjacency matrix to 0, indicating that initially, there are no edges between any pair of vertices.

Function to Add an Edge to the Graph

• The addEdge function takes the source vertex (src) and destination vertex (dest) as input and sets matrix[src][dest] and matrix[dest][src] to 1, indicating the presence of an edge between these vertices. This function assumes the graph is undirected.

Function to Display the Adjacency Matrix

• The displayMatrix function prints the adjacency matrix, showing the connections between vertices.

Main Function

• The main function allows the user to input the number of vertices and edges, adds edges to the graph, and then displays the adjacency matrix.

Output Example

Example Output:

Enter the number of vertices: 4 Enter the number of edges: 4 Enter edge (source destination): 0 1 Enter edge (source destination): 0 2 Enter edge (source destination): 1 3 Enter edge (source destination): 2 3 Adjacency Matrix: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 

Example Output (Different Graph):

If the graph has different edges, for example:

Enter the number of vertices: 3 Enter the number of edges: 2 Enter edge (source destination): 0 1 Enter edge (source destination): 1 2 Adjacency Matrix: 0 1 0 1 0 1 0 1 0 

Conclusion

This C program demonstrates how to implement a graph using an adjacency matrix. The adjacency matrix is a simple and straightforward way to represent a graph, making it easy to check if there is an edge between any two vertices. This program provides a practical example of how to create and use an adjacency matrix in C programming.