Add Vertex to existing Graph: C Program Example

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

Write a C program that implements a function to add a new vertex to an existing graph.

Add Vertex to existing Graph: C Program Example

Vertices are represented by numbers 1, 2, 3, and 4.

Edges are represented by lines connecting the vertices.

Sample Solution:

C Code:

#include <stdio.h>

#define MAX_VERTICES 100

// 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");
    }
}

// Function to add a new vertex to the graph
void addVertex(int graph[MAX_VERTICES][MAX_VERTICES], int* vertices) {
    if (*vertices >= MAX_VERTICES) {
        printf("Cannot add more vertices. Maximum limit reached.\n");
        return;
    }

    // Increment the number of vertices
    (*vertices)++;

    // Add the new vertex
    for (int i = 0; i < *vertices; i++) {
        graph[i][*vertices - 1] = 0;
        graph[*vertices - 1][i] = 0;
    }

    printf("New vertex added successfully.\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) / 2) {
        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;
        }

        graph[start][end] = 1;
        graph[end][start] = 1; // For undirected graph
    }

    // Display the original adjacency matrix
    printf("Original Graph:\n");
    displayGraph(graph, vertices);

    // Add a new vertex
    addVertex(graph, &vertices);

    // Display the modified adjacency matrix
    printf("Graph after adding a new vertex:\n");
    displayGraph(graph, vertices);

    return 0;
}

Output:

Enter the number of vertices: 4
Enter the number of edges: 3
Enter edge 1 (start end): 0 1
Enter edge 2 (start end): 1 2
Enter edge 3 (start end): 2 3
Original Graph:
Adjacency Matrix:
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
New vertex added successfully.
Graph after adding a new vertex:
Adjacency Matrix:
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

Explanation:

In the exercise above,

Display Function (displayGraph):

Prints the adjacency matrix of the graph.

Add Vertex Function (addVertex):

Checks if the maximum limit of vertices (MAX_VERTICES) has been reached.
Increments the number of vertices (vertices) and adds the new vertex connections to the existing graph.

Main Function (main):

Inputs the number of vertices and edges from the user.
Constructs the initial graph based on user input.
Displays the original adjacency matrix.
Calls addVertex to add a new vertex.
Displays the modified adjacency matrix after adding the new vertex.

Flowchart:

C Programming Code Editor:

Previous: Graph Representation in C Using Adjacency Matrix.
Next: C Program to add directed edge in Graph.