Adjacency Matrix of Graph in C

Program in C to represent Graph using Adjacency Matrix.

Adjacency Matrix Representation of Graph in C Programming

       In C programming, an adjacency matrix is commonly used to represent a graph. It is implemented as a 2D array where:

  • Rows represent starting vertices.
  • Columns represent ending vertices.
  • Each cell A[i][j] holds either:
    • 1 if there’s an edge between vertex i and vertex j.
    • 0 if there’s no edge between vertex i and vertex j.

How to Represent Graph using Adjacency Matrix in C

  1. Input the number of vertices (V) and edges (E).
  2. Initialize a 2D array with all elements set to 0.
  3. For each edge:
    • Input the starting vertex u and ending vertex v.
    • Set A[u][v] = 1.
    • For an undirected graph, also set A[v][u] = 1.
  4. Display the adjacency matrix.

 Assignment 3. Set A a) SPPU:

Write a C program that accepts the vertices and edges of an undirected  graph and stores it as an adjacency matrix. Display the adjacency matrix.
download code
 
#include <stdio.h>

int main() {
    int vertices, edges;
    int i, j;

    // Input the number of vertices
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    // Input the number of edges
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    // Initialize adjacency matrix with all zeros
    int adjacencyMatrix[vertices][vertices];
    for (i = 0; i < vertices; i++) {
        for (j = 0; j < vertices; j++) {
            adjacencyMatrix[i][j] = 0;
        }
    }

    // Input the edges and update the adjacency matrix
    printf("Enter the edges (vertex1 vertex2):\n");
    for (i = 0; i < edges; i++) {
        int vertex1, vertex2;
        scanf("%d %d", &vertex1, &vertex2);

        // Update the adjacency matrix for an undirected graph
        adjacencyMatrix[vertex1][vertex2] = 1;
        adjacencyMatrix[vertex2][vertex1] = 1; // For undirected graph
    }

    // Display the adjacency matrix
    printf("\nAdjacency Matrix:\n");
    for (i = 0; i < vertices; i++) {
        for (j = 0; j < vertices; j++) {
            printf("%d ", adjacencyMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

For an undirected graph, the adjacency matrix is symmetric, and each edge is represented twice.  If you enter 3 vertices and 3 edges the expected construction and output will be as given below.

Step-by-Step Construction:

  1. Initialize a 3×3 matrix with all zeros:

     
    0 0 0
0 0 0
0 0 0

  2. Add the edges:

    • Edge (0, 1):

      • Set matrix[0][1] = 1 and matrix[1][0] = 1.

    • Edge (1, 2):

      • Set matrix[1][2] = 1 and matrix[2][1] = 1.

    • Edge (2, 0):

      • Set matrix[2][0] = 1 and matrix[0][2] = 1.

  3. Final Adjacency Matrix:

     
    0 1 1
1 0 1
1 1 0
 

 Assignment 3. Set A a) SPPU: (Directed Graph)

Write a C program that accepts the vertices and edges of an directed  graph and stores it as an adjacency matrix. Display the adjacency matrix.
download code
 
#include <stdio.h>

int main() {
    int vertices, edges;
    int i, j;

    // Input the number of vertices
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    // Input the number of edges
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    // Initialize adjacency matrix with all zeros
    int adjacencyMatrix[vertices][vertices];
    for (i = 0; i < vertices; i++) {
        for (j = 0; j < vertices; j++) {
            adjacencyMatrix[i][j] = 0;
        }
    }

    // Input the edges and update the adjacency matrix
    printf("Enter the edges (vertex1 vertex2):\n");
    for (i = 0; i < edges; i++) {
        int vertex1, vertex2;
        scanf("%d %d", &vertex1, &vertex2);

        // Update the adjacency matrix for a directed graph
        adjacencyMatrix[vertex1][vertex2] = 1; // Only set matrix[vertex1][vertex2] = 1
    }

    // Display the adjacency matrix
    printf("\nAdjacency Matrix:\n");
    for (i = 0; i < vertices; i++) {
        for (j = 0; j < vertices; j++) {
            printf("%d ", adjacencyMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

 Assignment 3. Set A b) SPPU:  

Introduction to Degree, Indegree, and Outdegree

          In graph theory, the degree of a vertex is a fundamental concept that describes the number of edges connected to that vertex. The definitions vary slightly for undirected and directed graphs.

1. Degree in an Undirected Graph:

  • The degree of a vertex is the number of edges incident to it.

  • For example, if a vertex v is connected to 3 edges, its degree is 3.

2. Indegree and Outdegree in a Directed Graph:

  • In a directed graph, edges have a direction, so we define two types of degrees:

    • Indegree: The number of edges coming into a vertex.

    • Outdegree: The number of edges going out of a vertex.

  • For example:

    • If vertex v has 2 edges coming into it and 1 edge going out of it, its indegree is 2, and its outdegree is 1.

  • The total degree of a vertex in a directed graph is the sum of its indegree and outdegree.

 Assignment 3. Set A b) SPPU:

Write  a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. implement functions to print indegree, outdegree and total degree of all vertices of graph.
download code
 
#include <stdio.h>

// Function to compute and print indegree, outdegree, and total degree
void computeDegrees(int adjacencyMatrix[][100], int vertices) {
    int indegree[100] = {0}; // Array to store indegree of each vertex
    int outdegree[100] = {0}; // Array to store outdegree of each vertex
    int totalDegree[100] = {0}; // Array to store total degree of each vertex

    // Compute outdegree and indegree
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if (adjacencyMatrix[i][j] == 1) {
                outdegree[i]++; // Increment outdegree of vertex i
                indegree[j]++; // Increment indegree of vertex j
            }
        }
    }

    // Compute total degree and print results
    printf("\nVertex\tIndegree\tOutdegree\tTotal Degree\n");
    for (int i = 0; i < vertices; i++) {
        totalDegree[i] = indegree[i] + outdegree[i]; // Total degree = indegree + outdegree
        printf("%d\t%d\t\t%d\t\t%d\n", i, indegree[i], outdegree[i], totalDegree[i]);
    }
}

int main() {
    int vertices, edges;
    int adjacencyMatrix[100][100] = {0}; // Initialize adjacency matrix with zeros

    // Input the number of vertices
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    // Input the number of edges
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    // Input the edges and update the adjacency matrix
    printf("Enter the edges (vertex1 vertex2):\n");
    for (int i = 0; i < edges; i++) {
        int vertex1, vertex2;
        scanf("%d %d", &vertex1, &vertex2);

        // Update the adjacency matrix for a directed graph
        adjacencyMatrix[vertex1][vertex2] = 1; // Only set matrix[vertex1][vertex2] = 1
    }

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

    // Compute and print indegree, outdegree, and total degree
    computeDegrees(adjacencyMatrix, vertices);

    return 0;
}

         In the context of an adjacency matrix, a row represents the connections (edges) going out from a specific vertex. Let me break it down for you:

What is a Row in an Adjacency Matrix?

An adjacency matrix is a 2D array (matrix) where:

  • Each row corresponds to a vertex in the graph.

  • Each column also corresponds to a vertex in the graph.

  • The value at matrix[i][j] indicates whether there is an edge from vertex i to vertex j.

For example, consider the following adjacency matrix for a graph with 3 vertices (0, 1, and 2):

 
0 1 1 
0 0 1 
1 0 0

Here:

  • Row 0: [0, 1, 1] corresponds to vertex 0.

  • Row 1: [0, 0, 1] corresponds to vertex 1.

  • Row 2: [1, 0, 0] corresponds to vertex 2.

 

What Does Row: [0, 1, 1] Mean?

The row [0, 1, 1] corresponds to vertex 0. Let’s break it down:

  • The row has 3 columns, representing vertices 0, 1, and 2.

  • Each value in the row indicates whether there is an edge from vertex 0 to the corresponding vertex.

Interpretation:

  • matrix[0][0] = 0: No edge from vertex 0 to itself.

  • matrix[0][1] = 1: There is an edge from vertex 0 to vertex 1.

  • matrix[0][2] = 1: There is an edge from vertex 0 to vertex 2.

So, the row [0, 1, 1] tells us that:

  • Vertex 0 has outgoing edges to vertices 1 and 2.

 

Why is the Row Important?

The row in the adjacency matrix is used to calculate the outdegree of a vertex. The outdegree is the number of edges going out from a vertex. To find the outdegree of a vertex:

  • Count the number of 1s in its corresponding row.

Example:

  • For vertex 0, the row is [0, 1, 1].

  • Number of 1s: 2.

  • Outdegree of vertex 0: 2.

Representation:

Adjacency Matrix:
      0  1  2  (Columns represent vertices)
0  [ 0, 1, 1 ]  → Row for vertex 0
1  [ 0, 0, 1 ]  → Row for vertex 1
2  [ 1, 0, 0 ]  → Row for vertex 2

  • Row 0: [0, 1, 1] → Vertex 0 has edges to vertices 1 and 2.

  • Row 1: [0, 0, 1] → Vertex 1 has an edge to vertex 2.

  • Row 2: [1, 0, 0] → Vertex 2 has an edge to vertex 0.

  •  

Example:

0 1 1 
0 0 1 
1 0 0

Rows and Their Meanings:

  1. Row 0: [0, 1, 1]

    • Vertex 0 has edges to vertices 1 and 2.

    • Outdegree: 2.

  2. Row 1: [0, 0, 1]

    • Vertex 1 has an edge to vertex 2.

    • Outdegree: 1.

  3. Row 2: [1, 0, 0]

    • Vertex 2 has an edge to vertex 0.

    • Outdegree: 1.

 Assignment 3. Set B (a) SPPU:

Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement function to traverse the graph using Breadth First Search (BFS) traversal.
download code

#include <stdio.h>

#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// Queue implementation for BFS
typedef struct {
    int items[MAX_VERTICES];
    int front;
    int rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

bool isEmpty(Queue* q) {
    return q->rear == -1;
}

void enqueue(Queue* q, int value) {
    if (q->rear == MAX_VERTICES - 1) {
        printf("Queue is full\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

// Graph implementation
typedef struct {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            graph->adjMatrix[i][j] = 0;
        }
    }

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    // For undirected graph
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;
}

void printGraph(Graph* graph) {
    printf("\nAdjacency Matrix:\n");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("Vertex %d: ", i);
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

// BFS implementation with clear output
void BFS(Graph* graph, int startVertex) {
    bool visited[MAX_VERTICES] = {false};
    Queue* q = createQueue();

    visited[startVertex] = true;
    enqueue(q, startVertex);

    printf("\nBFS Traversal starting from vertex %d:\n", startVertex);
    printf("Visited order: ");
    
    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        // Explore all adjacent vertices
        for (int i = 0; i < graph->numVertices; i++) {
            if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                enqueue(q, i);
            }
        }
    }
    printf("\n\n");
    free(q);
}

int main() {
    int vertices, edges, src, dest;
    int startVertex;

    printf("Graph Traversal using BFS Algorithm\n");
    printf("===================================\n\n");
    
    printf("Enter number of vertices (max %d): ", MAX_VERTICES);
    scanf("%d", &vertices);

    Graph* graph = createGraph(vertices);

    printf("Enter number of edges: ");
    scanf("%d", &edges);

    printf("\nEnter edges (source destination):\n");
    for (int i = 0; i < edges; i++) {
        printf("Edge %d: ", i + 1);
        scanf("%d %d", &src, &dest);
        if (src >= vertices || dest >= vertices) {
            printf("Error: Vertex index out of range!\n");
            i--; // Retry this edge
            continue;
        }
        addEdge(graph, src, dest);
    }

    printGraph(graph);

    printf("\nEnter starting vertex for BFS (0 to %d): ", vertices - 1);
    scanf("%d", &startVertex);
    
    if (startVertex < 0 || startVertex >= vertices) {
        printf("Invalid starting vertex!\n");
    } else {
        BFS(graph, startVertex);
    }

    free(graph);
    return 0;
}

 Assignment 3. Set B (b) SPPU:

Write a c program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement function to traverse the graph using Depth First Fearch (DFS) traversal.
download code
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// Graph structure
typedef struct {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

// Function to create a graph
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    // Initialize adjacency matrix to 0
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            graph->adjMatrix[i][j] = 0;
        }
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(Graph* graph, int src, int dest) {
    // For undirected graph
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;
}

// Function to print the adjacency matrix
void printGraph(Graph* graph) {
    printf("\nAdjacency Matrix:\n");
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

// DFS recursive helper function
void DFSUtil(Graph* graph, int vertex, bool visited[]) {
    // Mark the current vertex as visited
    visited[vertex] = true;
    printf("%d ", vertex);

    // Recur for all adjacent vertices
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->adjMatrix[vertex][i] == 1 && !visited[i]) {
            DFSUtil(graph, i, visited);
        }
    }
}

// DFS traversal function
void DFS(Graph* graph, int startVertex) {
    // Create visited array
    bool visited[MAX_VERTICES] = {false};

    printf("\nDFS Traversal starting from vertex %d:\n", startVertex);
    DFSUtil(graph, startVertex, visited);
    printf("\n");
}

int main() {
    int vertices, edges, src, dest;
    int startVertex;

    printf("Graph Traversal using DFS Algorithm\n");
    printf("===================================\n\n");
    
    printf("Enter number of vertices (max %d): ", MAX_VERTICES);
    scanf("%d", &vertices);

    Graph* graph = createGraph(vertices);

    printf("Enter number of edges: ");
    scanf("%d", &edges);

    printf("\nEnter edges (source destination):\n");
    for (int i = 0; i < edges; i++) {
        printf("Edge %d: ", i + 1);
        scanf("%d %d", &src, &dest);
        if (src >= vertices || dest >= vertices) {
            printf("Error: Vertex index out of range (0-%d)!\n", vertices-1);
            i--; // Retry this edge
            continue;
        }
        addEdge(graph, src, dest);
    }

    printGraph(graph);

    printf("\nEnter starting vertex for DFS (0 to %d): ", vertices - 1);
    scanf("%d", &startVertex);
    
    if (startVertex < 0 || startVertex >= vertices) {
        printf("Invalid starting vertex!\n");
    } else {
        DFS(graph, startVertex);
    }

    free(graph);
    return 0;
}
Table of Contents
Adjacency Matrix Representation
Adjacency List Representation
Piyu's CS

Computer Science Education

Contact Us

info@piyuscs.com