C Program to add directed edge in Graph

Last update on December 20 2024 13:05:11 (UTC/GMT +8 hours)

Write a C function to add a directed edge between two vertices in a graph.

Sample Solution:

C Code:

#include <stdio.h>

#define MAX_VERTICES 100

// Function to add a directed edge from 'start' to 'end'
void addDirectedEdge(int graph[MAX_VERTICES][MAX_VERTICES], int start, int end, int vertices) {
    if (start < 0 || start >= vertices || end < 0 || end >= vertices) {
        printf("Invalid vertices.\n");
        return;
    }

    graph[start][end] = 1;
}

// Function to display the adjacency matrix
void displayGraph(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int vertices, edges;

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

    if (vertices <= 0 || vertices > MAX_VERTICES) {
        printf("Invalid number of vertices. Exiting...\n");
        return 1;
    }

    int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // Initialize the adjacency matrix with zeros

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

    if (edges < 0 || edges > vertices * (vertices - 1)) {
        printf("Invalid number of edges. Exiting...\n");
        return 1;
    }

    // Input edges and construct the adjacency matrix
    for (int i = 0; i < edges; i++) {
        int start, end;
        printf("Enter edge %d (start end): ", i + 1);
        scanf("%d %d", &start, &end);

        // Validate input vertices
        if (start < 0 || start >= vertices || end < 0 || end >= vertices) {
            printf("Invalid vertices. Try again.\n");
            i--;
            continue;
        }

        addDirectedEdge(graph, start, end, vertices);
    }

    // Display the adjacency matrix
    displayGraph(graph, vertices);

    return 0;
}

Output:

Enter the number of vertices: 5
Enter the number of edges: 6
Enter edge 1 (start end): 0 1
Enter edge 2 (start end): 1 2
Enter edge 3 (start end): 2 3
Enter edge 4 (start end): 3 4
Enter edge 5 (start end): 4 0
Enter edge 6 (start end): 2 4
Adjacency Matrix:
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
0 0 0 0 1
1 0 0 0 0

Explanation:

The above C program represents a directed graph using an adjacency matrix. Here's a brief explanation:

Function addDirectedEdge:

Take a graph represented by an adjacency matrix, the start and end vertices of a directed edge, and the total number of vertices.
Checks if the provided vertices are valid.
If valid, it adds a directed edge from the 'start' vertex to the 'end' vertex by updating the corresponding entry in the adjacency matrix.

Function displayGraph:

Takes a graph represented by an adjacency matrix and the total number of vertices.
Displays the adjacency matrix on the console.

Main Function:

Reads the number of vertices and edges from the user.
Creates an adjacency matrix initialized with zeros.
Takes input for directed edges, validates the vertices, and adds them to the graph using the "addDirectedEdge()" function.
Displays the resulting adjacency matrix.

Flowchart:

C Programming Code Editor:

Previous: Add Vertex to existing Graph: C Program Example.
Next: Program for DFS traversal in Graph.