Graphs

‘Graph’ is an ‘abstract data type’ which is used to implement ‘undirected graph’ and ‘directed graph’ concepts from mathematics.

Graph consists of finite set of ‘vertices (nodes)’ and interconnecting ‘edges’ to them. For undirected graph, edges are undirected too. And for directed graph, edges are directed. Each vertex is associated with a values called ‘vertex value’. A values can be associated with edges called as ‘edge value’.
 
Graph operations
Following are the operations that can be performed on a graph:
Operation
Function format
Explanation
Adjacent
(G, x, y)
Check if x and y vertices in graph G are adjacent.
Neighbors
(G, x)
List all the neighbor-vertices of vertex x in graph G
Add vertex
(G, x)
Add vertex x in graph G, if it is not there.
Remove vertex
(G, x)
Remove vertex x from graph G, if it is there.
Add edge
(G, x, y)
Add edge in between vertices x and y in graph G, if it is not there.
Remove edge
(G, x, y)
Remove edge in between vertices x and y in graph G, if it is there.
Get vertex value
(G, x)
Get values of vertex x in graph G.
Set vertex value
(G, x, v)
Set values of vertex x in graph G.
Get edge value
(G, x, y)
Get value of edge in between x and y in graph G, if edges have value.
Set edge value
(G, x, y, v)
Set value of edge in between x and y in graph G, if edges have value.

Graph representation

Graph is represented by following methods:

1. Adjacency List
Adjacency List representation of graph is a collection of mapping of each vertex and the list of neighboring vertices to it.
 
An ‘array of linked lists’ is used to implement Adjacency List as follows:
i. First node of each linked list in this list would represent the vertex for which we are finding adjacent vertices.
ii. Next nodes in each after the first node represents vertices adjacent to the vertex denoted by first node.
iii. Data in first node of the linked is considered as the weight of that node.
iv. Data in rest of the nodes of the linked list is considered as the weight of that edge.
 
Adjacency List for above graph would be:
 
This allows to store following information:
i. Additional data on vertices
ii. Data on edges
iii. Cost of an edge
 
 
We cannot store the direction of an edge using this method.
 
2. Adjacency Matrix
Adjacency matrix is 2-D matrix where rows represent the vertices and columns represent destination vertices. Data on edge and vertices must be stored externally. Only cost of one edge is stored for each pair of vertices. We cannot store direction of an edge using this method.

Adjacency Matrix can be represented using 2D arrays as follows:
 
 
10
20
30
40
50
60
10
0
7
5
0
0
0
20
7
0
6
0
4
0
30
5
6
0
12
0
0
40
0
0
12
0
10
9
50
0
4
0
10
0
0
60
0
0
0
9
0
0
Following are the time complexities required to perform general operations on graphs using above mentioned graph representations:
 
 

Graph traversal

For Graph traversal, we keep track whether that vertex is visited or not. Consider following graph.
Matrix representation of this graph would be:


Matrix representation of this graph would be:


 
1
2
3
4
5
6
1
0
7
5
0
0
0
2
7
0
6
0
4
0
3
5
6
0
12
0
0
4
0
0
12
0
10
9
5
0
4
0
10
0
0
6
0
0
0
9
0
0

Following are the methods for graph traversal:

1. Breadth First Search (BFS)
Breadth First Search traversal algorithm for graphs starts with given node and traverses neighboring vertex first and then traverses child vertex. It uses ‘queue’ for this purpose. This algorithm is used to find the shortest path from one vertex to another in a graph.

In BFS, initially all vertices are marked as ‘non-visited’. We mark them as ‘visited’ as soon as we visit them. Whenever we process a vertex, we add each of its neighboring vertex onto a queue. Once that vertex is processed, we remove next vertex from queue and process it in a same way.  

If we take first vertex i.e. root = 2, BFS algorithm should traverse graph as per follows:



Result of BFS traversal is: 2 1 3 5 4 6

2. Depth First Search (DFS)
Depth First Search (DFS) traversal algorithm for Graphs is similar to that for Trees. It starts with given node, traverses first sub-tree starting with this node, and then traverses other sub-tree and goes on. DFS can be implemented using ‘recursion’.

In DFS, we mark each vertex that we visit as ‘visited’. As soon as we find non-visited vertex, we start traversing its child node. It means, a child vertex of a given vertex is traversed before its sibling vertex. DFS method requires less memory compared to BFS method.

If we take first vertex i.e. root = 2, DFS algorithm should traverse graph as per follows:


Result of DFS traversal is: 2 1 3 4 5 6


Creating Adjacency Matrix & BFS and DFS traversal of graph using C
Above graph example is only taken to execute implementation of Adjacency matrix creation and BFS and DFS traversal of graph.

Code:
 
#include "stdio.h"
#define visited 1
#define not_visited 0
 
/*Add edge between vertices verA and verB with weight*/
void Add_Edge(int adjM[][20], int verA, int verB, int weight){
                adjM[verA][verB] = weight;
                adjM[verB][verA] = weight;
                printf("\nEdge %d-%d is added to Graph.", verA, verB);
               
}
 
void Drawline(int n){
                printf("\n");
                int i;
                for(i=0; i<n; i++)
                                printf("-------");
}
 
void Display_AdjM(int adjM[][20], int n){
                int i, j;
                printf("\nAdjacency Matrix for graph is as follows:\n");
                for(i=0; i<=n; i++){
                                if(i==1)
                                                Drawline(n);
                                printf("\n");
                                for(j=0; j<=n; j++){
                                                if(j == 0)
                                                                printf("%d   | ", adjM[i][j]);
                                                else
                                                                printf("%d     ", adjM[i][j]);
                                }
                }
                Drawline(n);
}
 
/*Depth First Search - using recurssion*/
void DFS_rec(int adjM[][20], int visVer[], int root, int n){
                int i;
                /*we are starting with vertex 'root'. So we mark it as visited*/
                visVer[root] = visited;
               
                /*print every non-visited node*/
                printf("%d  ", root);
               
                for(i=1; i<=n; i++){
                                if(adjM[root][i] && visVer[i] == not_visited){
                                                DFS_rec(adjM, visVer, i, n);
                                }
                }
}
 
/*Breadth First Search - using queue*/
void BFS(int adjM[][20], int visVer[], int root, int n){
                int queue[20], i, j, front, rear, curVer, adjVerDist;
               
                /*Create a queue*/
                for(i=0; i<n; i++)
                                queue[i] = 0;
                front = 0;
                rear = 0;
                /*whenever front = rear, queue would be empty*/
                /*queue created*/
               
                /*enqueue root from rear end*/
                queue[rear++] = root;
               
                /*mark root as visited*/
                visVer[root] = visited;
               
                /*check while queue is not empty*/
                while(front != rear){
                                /*dequeue vertext from front end*/
                                curVer = queue[front++];
                               
                                /*reset queue once emptied*/
                                if(front == rear)
                                                front = rear = 0;
                               
                                /*check if vertex is visited or not*/        
                                if(visVer[curVer] == visited){
                                               
                                                /*print every newly-visited node*/
                                                printf("%d  ", curVer);
                                               
                                                /*Traverse adj vertices of the current vertex*/
                                                for(i=1; i<=n; i++){
                                                                /*check if adj vertex is visited or not*/
                                                                /*Enqueue and mark visited if NOT visited. Skip if visited*/
                                                                adjVerDist = adjM[curVer][i];
                                                                if(adjVerDist != 0 && visVer[i] == not_visited){
                                                                                visVer[i] = visited;
                                                                                queue[rear++] = i;
                                                                }
                                                }
                                }
                }
}
 
void main(){
               
                int adjM[20][20];//This is Adjacency Matrix used to represent Graph
                int visVer[20];//This is array to check if vertex is visited or not
                int n;//no. of vertices
                int i, j, maxedges, verA, verB, weight;
               
                printf("Enter no. of vertices: ");
                scanf("%d", &n);
               
                /*mark all vertices as non-visited*/
                for(i=1; i<=n; i++)
                                visVer[i] = not_visited;
               
                /*reset adjacency matrix*/
                for(i=0; i<=n; i++)
                                for(j=0; j<=n; j++){
                                                /*Index 0 for rows and column indicate node numbers*/
                                                if(i == 0)
                                                                adjM[i][j] = j;
                                                else if(j == 0)
                                                                adjM[i][j] = i;
                                                /*Adj Matrix starts from index 1 for rows and columns*/
                                                else
                                                                adjM[i][j] = 0;
                }
               
                /*Display reset Adj Matrix*/
                printf("\nAdj Matrix before adding edges....\n");
                Display_AdjM(adjM, n);
               
                /*Add edges to the graph*/
                printf("\nThere are %d vertices in this graph (1 to %d)", n, n);
                printf("\nMaximum edges(non-self pointing) for this graph can be n(n-1)/2 : %d", (n*(n-1))/2);
                printf("\nEnter number of edges for this graph : ");
                scanf("%d", &maxedges);
               
                for(i=1; i<=maxedges; i++){
                                printf("\n---------------------Enter details for edge %d--------------------------------", i);
                                printf("\nEnter ver A : ");
                                scanf("%d", &verA);
                                printf("Enter ver B : ");
                                scanf("%d", &verB);
                                printf("Enter weight for edge %d-%d : ", verA, verB);
                                scanf("%d", &weight);
                                Add_Edge(adjM, verA, verB, weight);
                }
               
                /*Display Adj Matrix after adding edges*/
                printf("\nAdj Matrix after adding edges....\n");
                Display_AdjM(adjM, n);
               
                /*Check DFS traversal result*/
                printf("\nDFS traversal result is: ");
                DFS_rec(adjM, visVer, 2, n);
               
                /*mark all vertices as non-visited*/
                for(i=1; i<=n; i++)
                                visVer[i] = not_visited;
               
                /*Check BFS traversal result*/
                printf("\nBFS traversal result is: ");
                BFS(adjM, visVer, 2, n);
}
 
 
Output:
 
Enter no. of vertices: 6
 
Adj Matrix before adding edges....
 
Adjacency Matrix for graph is as follows:
 
0   | 1     2     3     4     5     6
------------------------------------------
1   | 0     0     0     0     0     0
2   | 0     0     0     0     0     0
3   | 0     0     0     0     0     0
4   | 0     0     0     0     0     0
5   | 0     0     0     0     0     0
6   | 0     0     0     0     0     0
------------------------------------------
There are 6 vertices in this graph (1 to 6)
Maximum edges(non-self-pointing) for this graph can be n(n-1)/2 : 15
Enter number of edges for this graph : 7
 
---------------------Enter details for edge 1--------------------------------
Enter ver A : 1
Enter ver B : 2
Enter weight for edge 1-2 : 7
 
Edge 1-2 is added to Graph.
---------------------Enter details for edge 2--------------------------------
Enter ver A : 1
Enter ver B : 3
Enter weight for edge 1-3 : 5
 
Edge 1-3 is added to Graph.
---------------------Enter details for edge 3--------------------------------
Enter ver A : 2
Enter ver B : 3
Enter weight for edge 2-3 : 6
 
Edge 2-3 is added to Graph.
---------------------Enter details for edge 4--------------------------------
Enter ver A : 2
Enter ver B : 5
Enter weight for edge 2-5 : 4
 
Edge 2-5 is added to Graph.
---------------------Enter details for edge 5--------------------------------
Enter ver A : 3
Enter ver B : 4
Enter weight for edge 3-4 : 12
 
Edge 3-4 is added to Graph.
---------------------Enter details for edge 6--------------------------------
Enter ver A : 5
Enter ver B : 4
Enter weight for edge 5-4 : 10
 
Edge 5-4 is added to Graph.
---------------------Enter details for edge 7--------------------------------
Enter ver A : 4
Enter ver B : 6
Enter weight for edge 4-6 : 9
 
Edge 4-6 is added to Graph.
Adj Matrix after adding edges....
 
Adjacency Matrix for graph is as follows:
 
0   | 1     2     3     4     5     6
------------------------------------------
1   | 0     7     5     0     0     0
2   | 7     0     6     0     4     0
3   | 5     6     0     12     0     0
4   | 0     0     12     0     10     9
5   | 0     4     0     10     0     0
6   | 0     0     0     9     0     0
------------------------------------------
DFS traversal result is: 2  1  3  4  5  6
BFS traversal result is: 2  1  3  5  4  6
--------------------------------

1 comment :