Data Structures: Graphs
Graphs -> Concepts
Sorry! I can’t give that mathematical definition, involving all those Vs and Es, for the Graphs. Rather, take it this way — a graph is a collection of some finite VERTICES and some finite EDGES which happen to connect these vertices. If I consider a given list of cities as my list of VERTICES then you can, probably, call the air routes between them as to be the EDGES for them.
Based on this analogy, we can say that a Directed Graph is a one in which you have one way air routes and that you can not come back through that same route; means, you can fly from Delhi to Mumbai but can not come back through that same route. Similarly, if you have two way air routes between the cities then I call it, an Undirected Graph. Finally, if its not a sponsored journey then certainly you will have to bear the ticket fare, which means every route (EDGE) has some cost of journey attached and that makes it a Weighted Graph. No fare, no weight!
Undirected Graph:- Vertices: A, B, C, D Edges: AB, AC, BA, CD, DC
Weighted Graph:- Vertices: A, B, C, D Weighted Edges: AC-10, AB-17, CD-13
You might be thinking by now, what these Graphs have to do with computers! Well, to name a few I’ll give you some applications of it — in the study of information routing on computer networks (helps in finding the shortest routes); electronic circuit designing (helps to find out the electrical loops and overlaps); ticketing software uses it to find out the shortest route… Got the idea!
Note:- When I said route here, I meant the direct path between the adjacent vertices and that no other vertex is there in that path except the two adjacent vertices forming the path.
Graphs ->Adjacency Matrix
I said while describing the concepts of Graphs that its a collection of vertices and edges. Now, if I call these vertices as to be the pieces of similar information and the edges as to be the various linkages between them, then, you can certainly think of representing any Graph with the help of Linked Lists, can’t you?
Well, we’ll see that implementation in our next section. But for now, you’ve a bit simpler representation of Graphs, the Adjacency Matrix. This matrix shows you all the direct linkages between the vertices; meaning the direct edges between the vertices. Let me explain this with the help of an example -
Consider, this directed graph. It has five vertices and five edges — AD, BD, CB, DE and EC. The Adjacency matrix for this will be -
Now you know why it is called as an adjacency matrix. It only shows the direct paths between the vertices but you can see there exist paths which have intermediate vertices also; like from A to B you have D->E->C.
Remember, it does not matter if the graph is weighted, the adjacency matrix is gonna remain the same.
Note:- When I say route, I mean the direct path between the vertices and that no other vertex is there in that path except the two adjacent vertices forming the edge. I guess you know how to store a 2D-matrix in an array! That is left for your practice.
Graphs -> Traversal (DFS & BFS)
Great! you got the adjacency matrix of a graph, but that does not mean you can surf through that graph. Well, you got specific procedures to traverse a graph, viz. Depth First Search and Breadth First Search.
We have seen traversal of a list, which we did by sequentially printing the values in the list. In graphs, traversal means visiting every vertex in the graph (and you might process the value of that visited vertex). In sequential traversing of a list we start from the first element and finally reach the last element by sequentially incrementing the list’s INDEX value by 1 every time.
Depth First Search:-
Here, the starting point can be any vertex and the next vertex to be visited is decided by the traversal you choose. If you choose the DFS, the next vertex to be visited will be the adjacent vertex (to the starting point), which has the highest depth value(??????…look at the graph below) and then the next adjacent vertex with the next higher depth value and so on till all the adjacent nodes for that vertex are not visited. We repeat this same procedure for every visited vertex of the graph.
Well, I got to explain this with the help of a graph -
Algorithm:-
Step-1: Set the starting point of traversal and push it inside the stack
Step-2: Pop the stack and add the popped vertex to the list of visited vertices
Step-3: Find the adjacent vertices for the most recently visited vertex( from the Adjacency Matrix)
Step-4: Push these adjacent vertices inside the stack (in the increasing order of their depth) if they are not visited and not there in the stack already
Step-5: Go to step-2 if the stack is not empty
C implementation (dfs.c):-
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void visit(int);
int visited(int);
int instack(int);
void push(int);
int count();
int pop();
struct node
{
int value;
node *next;
};
struct node *bottom,*top;
int visited_list[10],k,nodes;
void main()
{
/*declare an array;*/
static int edges[10][10];
int i,j,vertex=0,adjnode;
clrscr();
bottom=(struct node*)malloc(sizeof(node));
top=bottom;
bottom->next=NULL;
/*get the no. of nodes from the user;*/
printf("Enter the number of nodes: ");
scanf("%d",&nodes);
/*loop: get the edges for these nodes;*/
for(i=0;i<nodes;i++)
for(j=0;j<nodes;j++)
{
printf("Is there any edge between nodes %d and %d: ",i,j);
scanf("%d",&edges[i][j]);
}
/*---------------------------------------------------*/
/*while all the nodes are not visited do the following steps*/
do
{
visit(vertex);/*visit the current node;*/
for(j=0;j<nodes;j++)/*find all its adjacent nodes;*/
/*push them in the stack if they are not visited and not there in the stack;*/
if(edges[vertex][j]==1)
{
adjnode=j;
if(!visited(adjnode) && !instack(adjnode))push(adjnode);
};
vertex=pop();/*pop the unvisted node from the stack;*/
}while(vertex!=NULL);/*end of while*/
for(k=0;k<nodes;k++)printf("%d->",visited_list[k]);
getch();
}/*end of main*/
/*------------------------------------------------------------*/
void push(int value)
{
struct node *curr=(struct node*)malloc(sizeof(node));
if(bottom->value==NULL)
{
bottom->value=value;
top=bottom;
}
else
{
top->next=curr;
curr->value=value;
top=curr;
curr->next=NULL;
}
}
int pop()
{
struct node *curr;
int value,no_nodes;
curr=bottom;
if(bottom==top && bottom->value!=NULL)
{
value=bottom->value;
bottom->value=NULL;
}
else
{
no_nodes=count()-1;
for(int i=1;i<no_nodes;i++)
curr=curr->next;
top=curr;
curr=curr->next;
value=curr->value;
top->next=NULL;
free(curr);
}
return(value);
}
int count()
{
struct node *curr;
int count=1;
curr=bottom;
while(curr->next!=NULL)
{
curr=curr->next;
count++;
}
return(count);
}
void visit(int node)
{
/*add the node to the list of visited nodes;*/
visited_list[k]=node;
k++;
}
int visited(int node)
{
int found=0,result;
/*check for this node in the list of visited nodes;*/
for(int i=0;i<nodes;i++)
if(visited_list[i]==node)found=1;
if(found==1) result=1; else result=0;
return(result);
}
int instack(int node)
{
int found=0,result;
struct node *curr;
/*check the stack elements for the node;*/
curr=bottom;
if(bottom==top)
{
if(node==curr->value)found=1;
}
else
{
while(curr->value!=NULL)
{
if(node==curr->value)found=1;curr=curr->next;
}
}
if(found==1)result=1; else result=0;
return(result);
}The dfs.c code does not have enough comments but you can always ask me for any clarifications. I have strictly followed the algorithm for the implementation.
Breadth First Search:-
We make use of a QUEUE here instead of a stack and the adjacent vertices are inserted inside the queue in the increasing order of their BREADTH, so that the first adjacent vertex to be visited will be the one with the least breadth value. Try out implementation on your own after you study the DFS one.
Note:- We push the adjacent vertices in the stack in the increasing order of their depth values so that when you pop the stack, you visit the vertex with higher depth value first and then the next higher depth value.
Graphs -> Linked List Representation
You can imagine the possible way of representing a graph using a linked list. Well, you do not have just one list but a list for every VERTEX. A linked list of all these individual lists will finally represent the graph. These individual lists depict the adjacent edges for a particular vertex.
If there would have been an edge from A to B in the graph, in the linked list representation we would have an extra node B after or before D in the down list for A. You can understand from the above representation that there are two types of Lists — one to maintain the adjacency list of every vertex and the other one to maintain the graph. Accordingly, we have two types of List nodes — one which has that red coloured pointer and the other with the black colour pointer. Sorry, to use such a raw language to explain! You will realise the difference after I give you the respective NODE structures.
Although there is no formal algorithm for the linked list representation, I am giving an informal one so that you understand its C implementation.
Algorithm:-
Step-1: Make the list that holds the graph, having all the vertices in the graph
Step-2: For every vertex in that list do the following —
a. find the adjacent vertices, if any
b. add that vertex in the adjacency list for this current vertex
Isn’t it easy..
C implementation:-
struct adj_node /*the NODE which forms the part of the adjacency list; look at figure [B]*/
{
char vertex_val;
struct adj_node *adj_next; /*red pointer*/
};
struct node /*the NODE which forms the part of the Graph; look at figure [A]*/
{
char vertex_val;
struct adj_node *down;
struct node *next; /*black pointer*/
};
struct node *graph;
LinkListrepresentation()
{
struct node *cur_vertex, *aux_ptr;
struct adj_node *adj_cur, *new;
/*Step-1 of the algorithm is expected from you or refer linked LISTS*/
/*Step-1 gives you a list, being pointed by 'graph' */
cur_vertex = graph; /*first node of the graph in consideration*/
/*Step-2 starts here*/
while ( cur_vertex != NULL)
{
aux_ptr = graph; /*an auxiliary pointer to the graph*/
adj_cur = NULL; /*an auxiliary pointer to keep track of the adjacency lists*/
cur_vertex->down = adj_cur;
while (aux_ptr != NULL)
{
printf("Is there any edge between %c and %c ",aux_ptr->vertex_val, cur_vertex->vertex_val);
scanf("%d", &edge);/*step-2: part-A*/
if( edge == 1) /*step-2: part - B*/
if( adj_cur == NULL)
{
adj_cur = (struct adj_node *)malloc(sizeof(adj_node));
adj_cur ->vertex_val = aux_ptr->vertex_val;
adj_cur -> adj_next = NULL;
}
else
{
new = (struct adj_node *)malloc(sizeof(adj_node));
new -> vertex_val = aux_ptr ->vertex_val;
adj_cur ->adj_next = new;
adj_cur = new;
adj_cur ->adj_next = NULL;
}
aux_ptr = aux_ptr ->next;
}
cur_vertex = cur_vertex ->next;
}
}Note:- If you don’t want to use aux_ptr, you can always maintain a Adjacency List for the graph and check it for every vertex, to find the respective adjacent edges.
Graphs -> Transitive Closure/ Warshall’s Algorithm
We have seen Adjacency Matrix, which tells you whose directly connected to whom, no! Remember, I left a special note there, saying that there can be many other paths which may exist and might not be visible from the Adjacency matrix, as these paths may have intermediate vertices. To find all such round about or via-paths there is a procedure to be followed, known as the transitive closure, which results in a matrix showing all those via-paths, if ever exist.
Get Akash Nath’s stories in your inbox
Join Medium for free to get updates from this writer.
Before I give you the algorithm, I need to create some background for it, as its a little complicated one. The input to this algorithm is an adjacency matrix, which has 1s for any row-column pair if there exists an edge between them. What we’ll be doing here is — checking out for every vertex, the incoming and outgoing links. If there exist both incoming and outgoing links for a particular vertex, we will put a 1 for the row-column pair formed by them in the adjacency matrix. Let me explain this with the help of an example -
Let’s take the vertex E into consideration. You have an edge coming from D and you have an edge going to C; quite visible from the matrix. So, as I said, we’ll put a 1 for the element DC in the matrix. Similarly, for the vertex C, we’ll put 1 for the element EB. We’ll do this for all the vertex in the graph and what you get at the end is the Transitive Closure of this graph. This way of finding the transitive closure was derived by Warshall and thus the name, Warshall’s algorithm.
Algorithm:-
Step-1: Copy the Adjacency matrix into another matrix called the Path matrix
Step-2: Find in the Path matrix for every element in the Graph, the incoming and outgoing edges
Step-3: For every such pair of incoming and outgoing edges put a 1 in the Path matrix
C implementation:-
transclosure( int adjmat[max][max], int path[max][max])
{
for(i = 0; i < max; i++)
for(j = 0; j < max; j++)
path[i][j] = adjmat[i][j];
for(i = 0;i <max; i++)
for(j = 0;j < max; j++)
if(path[i][j] == 1)
for(k = 0; k < max; k++)
if(path[j][k] == 1)
path[i][k] = 1;
}Note:- Well, there are other ways to find the transitive closure but Warshall has actually simplified them and hence I have referred that only.
Graphs -> Shortest Path Algorithm
Well, you can make out that it concerns to weighted graphs only. After you apply this algorithm you get a TREE, which shows you the shortest paths to all the other vertices from any given starting vertex. Sorry, I am running short of words. I better take an example for this. Consider the weighted graph below.
You can see there are no alternative paths and no loops in the resultant Shortest Path tree. The tree gives you the shortest path from A to rest of the vertices.
The algorithm is very comprehensive and here it is….
Algorithm:-
Step-1: Set the starting vertex
Step-2: Find the BFS (or DFS) for it
Step-3: For every vertex in the BFS
A. Find the shortest path from it to the starting vertex
B. Add that shortest path to the resultant TREE if its already not there and not forming a loop
C implementation:-
The implementation in C will be given later on..
Note:- The algorithm has been slightly modified wherein I have asked to find the BFS or DFS. As such you can also proceed without that. I would suggest you to go for BFS if your starting vertex is at much lower breadth level and to go for DFS if it is at a lower depth level. How to find that? Well, in that case your Adjacency list should hold the depth and breadth information, remember.
Graphs -> Spanning Tree Algorithm
This is a little different algorithm and a minor diversion of the shortest path algorithm you can say. In shortest path algorithm, we find the shortest path from all the vertices to a particular starting vertex. Here, its the shortest path between each vertex to every other vertex in the graph. Follow the example given below to understand better.
Now, find the adjacent edges to A and D.
The resultant Spanning Tree with no loops giving you the shortest distance between any two vertices.
The algorithm is very comprehensive and here it is….
Algorithm:-
Step-1: Take the least weighing edge of the graph and add it to the minimum Spanning Tree
Step-2: Find the adjacent edges for the vertices in the spanning tree
Step-3: Find the least among all those edges
Step-4: Add that edge to the spanning tree if its not forming a loop in the tree and that its not already there in the tree.
Step-5: Stop if all vertices in the Graph have been covered by the Tree else go to step-2
C implementation (sta.c file):-
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct edge
{
int start;
int end;
int cost;
};
static struct edge curr_edge[20],span_tree[20];
struct node
{
int value;
struct node *next;
};
struct node *start=(struct node*)malloc(sizeof(node)),*curr;
int visited(int);
void addnode(int);
struct edge nextedge(void);
int vercnt(void);
void main()
{
/*step-1:store the graph in form of edges in a structured(start,end,weight) array;*/
static int max=0,min,nodes,i,j,k,t,t_array[10][10];
clrscr();
start->value=NULL;
start->next=NULL;
curr=start;
printf("Enter the no. of vertices of the graph: ");
scanf("%d",&nodes);
for(i=1;i<nodes;i++)
for(j=1;j<nodes;j++)
{
printf("\nEnter the cost for the edge %d---%d : ",i,j);
scanf("%d",&t_array[i][j]);
}
for(i=1;i<nodes;i++)/*to remove the redundancy of the edge value*/
for(j=1;j<nodes;j++)
if(t_array[i][j]!=0)
t_array[j][i]=0;
for(i=1;i<nodes;i++)/*Take the edge values in the edge structure*/
for(j=1;j<nodes;j++)
if(t_array[i][j]!=0)
{
curr_edge[k].start=i;
curr_edge[k].end=j;
curr_edge[k].cost=t_array[i][j];
k++;
}
/*step-2:pick up the edge with the minimum weight & add to the spanning tree;*/
for(k=0;k<20;k++)
if(max < curr_edge[k].cost)
max=curr_edge[k].cost;
min=max;
for(k=0;k<20;k++)
if(curr_edge[k].cost!=0)
if(min>curr_edge[k].cost)
{
min=curr_edge[k].cost;
i=k;
}
span_tree[t].start=curr_edge[i].start;
span_tree[t].end=curr_edge[i].end;
span_tree[t].cost=curr_edge[i].cost;
addnode(span_tree[t].start);
addnode(span_tree[t].end);
while((t+1) < vercnt())
{
t++;
span_tree[t]=nextedge();
}
t=0;
while(span_tree[t+1].start!=0)
{
printf("%d--%d::::%d\n",span_tree[t].start,span_tree[t].end,span_tree[t].cost);
t++;
}
getch();
}
/*---------------------------------------*/
struct edge nextedge()
{
struct node *tmp_1;
static struct edge tmp_a[20],least;
int i,j,k=0,max=0,min;
for(tmp_1=start;tmp_1->value!=NULL;tmp_1=tmp_1->next)
for(i=0;i<20;i++)
if(tmp_1->value==curr_edge[i].start||tmp_1->value==curr_edge[i].end)
{
tmp_a[k].start=curr_edge[i].start;
tmp_a[k].end=curr_edge[i].end;
tmp_a[k].cost=curr_edge[i].cost;
k++;
}
for(k=0;k<20;k++)
if(max < tmp_a[k].cost)
max=tmp_a[k].cost;
for(k=0;k<20;k++)
for(j=0;j<=20;j++)
if(tmp_a[k].start==span_tree[j].start
&& tmp_a[k].end==span_tree[j].end)tmp_a[k].cost=0;
min=max;
for(k=0;k<20;k++)
if(tmp_a[k].cost!=0)
if(min>=tmp_a[k].cost)
{
min=tmp_a[k].cost;
i=k;
}
least.start=tmp_a[i].start;
least.end=tmp_a[i].end;
least.cost=tmp_a[i].cost;
if(!visited(least.start))addnode(least.start);
if(!visited(least.end))addnode(least.end);
return(least);
}
/*--------------------------------------------------*/
void addnode(int value)
{
struct node *tmp;
if(start->value==NULL)
{tmp=start;
tmp->value=value;
tmp->next=NULL;
}
else
{
tmp=(struct node*)malloc(sizeof(node));
curr->next=tmp;
tmp->value=value;
curr=tmp;
tmp->next=NULL;
}
}
/*--------------------------------------------------*/
int visited(int nodval)
{
struct node *tmp=start;
int ok;
while(tmp->value!=NULL)
{
if(nodval!=tmp->value)ok=0;
else
{
ok=1;
break;
}
tmp=tmp->next;
}
return(ok);
}
/*---------------------------------------------------*/
int vercnt()
{
int count=0;
struct node *tmp = start;
while(tmp->value!=NULL)
{
count++;
tmp=tmp->next;
}
return(count);
}Note:- You might have observed and off course it is true to certain extent that depending upon which vertex you choose when more than one least weighing edges are there at a stage, your tree may vary.
Link to other topics on Data Structures:
