Implementation of Graph in C || Directed and Undirected Graph

Graph:

A graph is the collection of vertices and edges or the set of vertices and edges. Mostly represented as G={V, E} here, G is for "Graph", V is for Vertices and E is for "Edges" in the graph.


Vertices and Edges:

Nodes in the graph are known as vertices whereas the line connecting two nodes in a graph is known as Edge between these two nodes or the connection between two nodes are known as an edge.


Types of Graph:

There are so many types and subtypes of the graph but I am writing three of them which are mostly used in programming


  1. Directed
  2. Undirected
  3. Weighted

Where Graphs are Used?

Graphs are mostly used to represent the relation between two or more things. For example, Facebook uses the graph structure to represent the connection between two friends, in Facebook people are the nodes and if two nodes have a connection between them that's mean these two nodes (persons) are friends on Facebook. Google maps tell us about the minimum distance between two cities or two places by using the weighted graph.


Representation of Graph:

In our daily life, we represent a graph by drawing nodes and connecting them by edges. But in programming, there is no way to represent the graph by drawing nodes etc. We can represent the graph in two ways


  1. Adjacency List
    Uses Linked List.
  2. Adjacency Matrix
    Uses 2d arrays.
Here is the implementation of Graph by using Adjacency Matrix. The following code is basically the implementation of the Undirected graph but if you remove the highlighted lines and initialize "j" with 0 in pink line in the code, the code will be the implementation of the Directed graph.

#include<stdio.h>
#include<stdlib.h>
int main(){

    int choice,addMatrix[10][10],totalNodes;

    while(1){
        printf("\nPress\n1 : Create a Graph\n2 : Display Graph\n3 : Exit\n");
        scanf("%d",&choice);
        switch(choice){
            case 1 :
                printf("Enter total No of Nodes : ");
                scanf("%d",&totalNodes);
                addMatrix[10][10]=0;
                createGraph(addMatrix,totalNodes);
            break;
            case 2 : displayAdjacencyMatrix(addMatrix,totalNodes);
            break;
            case 3 : exit(0);
        }
    }

    return 0;
}

void createGraph(int addMatrix[10][10],int totalNodes){
    int i,j;
    char adjacent;

    for(i=0;i<totalNodes;i++){

        printf("\n");

        for(j=i;j<totalNodes;j++){

            printf("Is Node %d is Adjacent to Node %d ? (Y/N): ",i,j);
            fflush(stdin);
            scanf("%c",&adjacent);

            if(adjacent=='Y' || adjacent=='y'){
                addMatrix[i][j]=1;
                addMatrix[j][i]=1;
            }else{
                addMatrix[i][j]=0;
                addMatrix[j][i]=0;
            }
        }
    }
}

void displayAdjacencyMatrix(int addMatrix[10][10],int totalNodes){
    int i,j;

    printf("\n\n");
    for(i=0;i<totalNodes;i++){
        for(j=0;j<totalNodes;j++){
            printf(" %d",addMatrix[i][j]);
        }
        printf("\n");
    }
}

Comments

Popular posts from this blog

c/c++ Programming questions || Practice problems for beginners || Simple c programs

How to become a Good Programmer