Graphs 385
n7 g Program to find shortest distances using Dijkstra's algorithm */
#include<stdio.h
#define MAX 100
#define TEMP 0
#define PERM 1
#define infinity 9999
#define NIL -1
void findPath(int s,int v):
void Dijkstra (int s);
int min_temp ();
void create_graph ();
int n; /*Denotes number of vertices in the graph*/
int adj (MAX J[MAX]:
predecessor (MAX) ; /*predecessor of each vertex in shortest path*/
int
int pathLength (MAX];
int status [MAX]:
main ()
int s, Vi
Create_graph();
printf( "Enter source vertex : ");
scanf ("%d", &s);
Dijkstra (s);
while (1)
printf("Enter destination vertex(-1 to quit): ");
scanf ("%d", &V);
if (v==-1)
break;
if (v<0v>=n)
printf ("This vertex does not exist\n*);
else if (v==s)
printf("Source and destination vertices are same\n");
else if (pathLength [v]==infinity)
source to destination vertex\n");
printf("There is no path from
else
findPath (s,v);
}/*End of main () */
void Dijkstra(int s)
int i, current;
/*Make all vertices temporary*/
for (i=0; i<n; it+)
{
predecessor (i) = NIL;
pathLength (i] = infinity;
status [i) = TEMP;
7"Make pathength of source vertex equal to 0*/
pathLength (s) = 0;
while (1)
pathLength
7*Search for temporary vertex with minimum
and make it current vertex*/
current = min_temp ();
if (current==NIL)
return;
status(current) = PERM;
Data
386 Structures
for (i=0; icn; i++)
{
/*Checks for adjacent temporary vertices*/
throughCin Depth
[i]==TEMP)
i£ (adi ícurrent)[i]!=0 && status
if(pathLength[current] + adj (current] [i] < pathLengthril )
predecessor [i] = current; /*Relabel */
pathLength[ i] = pathLength (current] + adj (currentliil.
)/*End of Dijkstra () */
with minimum value of pathlength, Returns NIL if no temporary
/*Returns the temporary vertex
vertices left have pathlength infinityt/
vertex left or all temporary
int min_temp ()
int i;
int min = infinity;
ínt k = NIL;
for (i=0; i<n; i++)
[i]<min)
if(status(i]z=TEMP &te pathLength
min = pathLength(i ];
k = i;
return k;
)/*End of min_temp () */
void findPath(int s,int v)
int i, u;
path/
int path(MAX]; /*stores the shortestshortest path/
int shortdist = 0; 7*l ength of
vertices in the shortest path/
int count = 0; /*number of
/*Store the full path in the array path*/
while (v!=s)
count++;
path(count ) = V;
u = predecessor [v);
shortdist += adj (u] [v);
V= u;
)
count++;
path(count]=s;
printf("Shortest Path is : ) ;
for (i=count; i>=l; i--)
printf("%d " path[i]);
printf("\n Shortest distance is : %d\n", shortdist);
}/*End of findPath () */
void create_graph ()
{
int i, max_edges, origin, destin, wt;
printf ("Enter number of vertices : ");
Scanf ("%d", &n) ;
max_edges = n* (n-1) ;
for (i=1; i<=max_edges; i++)
printf ("Enter edge %d(-1 -1 to quit) : ",í):
scanf ("%d %d", &origin, &destin) i
raphs
(dest1n1))
&&
if ((origin=-1)
break;
weight for thíg edge:")
print f (" Enter
scanf ("&d",&wt): originc0 | | dest 1n«0)
(origin>=n | | destin>=n | |
if
printf ("Inva1id edge! \n")
i--;
)
else
adj (origin] (destin) wti
n7 12 Program for
#include<stdio. h> creating minimum spanning tree using Prim's
#include<stdlib. h> algorithm*/
#define MAX 10
#define TEMP 0
#define PERM 1
#define infinity 9999
#define NIL -1
struct edge
int u;
int v;
int n;
int adj (MAX] [MAX);
int predecessor [MAX];
int status [ MAX];
int length (MAX];
void create_graph 0;
void maketree (int r, struct edge tree (MAX] );
int min_temp ():
main()
int wt_tree = 0;
int i, root;
struct edge tree [ MAX);
create_graph ()
printf ("Enter root vertex : ");
scanf ("%d", &root) ;
maketree (root, tree) ; are : \n");
printf ("Edges to be included in spanning tree
for (i=1; i<=n-1; i++)
print f ("&d->",treeli) .u) ;
printf ("%d\n",tree [i) .v):
[tree [i] .v];
wt_tree += adj (tree (i) .u)
Data STrucTures TrrougGn DepTh
404
Drintf("Wei ght. of spanning tree is: td\n", wt_tree)
}/*End of main() */
void ma ketree (int r, struct edge tree (MAX] )
int current, i;
int count = 0;/*number of vertices in the tree*/
for (i=0; i<n; it+) /*Initialize all vertices*/
predecessor (i) = NIL;
length(i) = infinity;
status(i) = TEMP:
length{r) = 0; /*Make length of root vertex 0*/
while(1)
{
/*Search for temporary vertex with minimum length
and make it current ver tex*/
current = min_temp();
if (current==NIL)
if (count==n-1) /*No temporary vertex left */
return;
else /*Temporary vertices left with length infinity*/
printf( "Graph is not connected, No spanning tree possible\n") ;
exit (1) ;
status (current] =PERM; /*Make the current vertex permanent */
/*Insert the edge (predecessor (current], current) into the tree,
except when the current vertex is root*/
if (current!=r)
count++;
tree (count].u = predecessor [ current];
tree [count].v = current;
for (i=0; i<n; it+)
if(adj [current) [i] >0 && status (i]==TEMP)
if (adj (current)[i) < length(i])
predecessor [i] = current;
length[i) = adj [current][i);
)/*End of make_tree () */
/*Returns the temporary vertex with minimum value of length, Returns NIL if no temporary
vertex left or all temporary vertices left have pathLength infinity*/
int min_temp ()
int i;
int min = infinity:
int k = -1;
for (i=0; i<n; i++)
if (status (i]==TEMP && length(i]<min)
min = length( il:
k = i;
return k;
}/*End of min_temp() */
Graphs
void create_ graph ()
{
int i, max_edges, origin,
printf ("Enter number of destin, wt;
vertices
scanf ("%d", &n); "):
max_edges = n* (n-1) /2; /*Undirected graph*/
for (i=l; i<=max_eges; i++)
print£ ("Enter edge %d(-1 -1 to
scan£ ("%d %d", &origin, &destin) ;
quit):",i);
if( (origin==-1) &&
break;
(destin==-1))
printf ( "Enter weight for this edge : ");
Scanf ("%d" ,&wt) ;
if (origin>=n | | destin>=n | |
{
origin<0 | | destin<0)
printf (" Invalid edge! \n");
i--;
else
adj [origin] (destin] = wt;
adj (destin] (origin) = wt;
}/*End of create_graph () */
algorithm*/
Kruskal 's
minimum spanning tree by
a
ogTam for creating
#include<stdio. h>
#include<stdlib.h>
#define MAX 100
#de fine NIL -1
struct edge
int u;
int ;
int weight;
struct edge link;
}*front = NULL;
void ma ke_tree (struct edge tree(]);
void insertpque (int i, int j,int wt):
struct edge del_pque ():
int is Empty_pque ():
void create_graph();
int n; /*Total number of vertices in the graph */
main()
int i;
edges of spanning tree*/
struct edge tree (MAX); /*Will contain the
tree*/
int wt_tree = 0: /*Weight of the spanning
Create_graph();
make_tree(tree) ;
printf("Edges to be included in minimum spanning tree are : \n");
for ( i l ; i<=n-1; i++)
printf ("%d->",tree(i).u) :
printf("%d\n",tree(i] .v) ;
Wt_tree += tree [i].weight;
print£(" Weight of this minimum spanning tree is : %d\n" ,wt_tree):
)/*End of main () /
void make_tree (struct edge tree())
struct edge *tnp;
int v1, v2,root_v1, root_v2 ;
int father (MAX); /*Hol ds father of each vertex*/
int i, count = 0; /*Denotes number of edges included in the tree*/
for (i=0; i<n; i++)
father (i) NIL;
/*Loop till queue becomes empty or till n-1 edges have been inserted in the tree*/
while(!isEmpty_pque (0 &be count<n-1)
tmp = del_pque () i
vl = tnp->u;
Graphs 409
v2 = tmp->V;
while (v1!=NIL)
root_v1 = vl;
v1 = father [v1] ;
while (v2!=NIL)
root_v2 = v2;
v2 = father (v2] :
if (root_v1!=root_v2 )/*Insert the edge (v1, v2) */
count++;
tree[count].u = tmp->u;
tree[count].v = tmp->v;
tree (count). weight = tmp->weight;
father [root_v2]=root_v1;
if (count <n-1)
printf ("Graph is not connected, no spanning tree possible\n") ;
exit (1) ;
}
}/*End of make_tree() */
/*Inserting edges in the linked priority gueue*/
void insert_pque(int i, int j,int wt)
struct edge *tmp,*g;
tmp = (struct edge *) malloc (sizeo£ (struct edge) );
tmp->u = i;
tmp->V = j
tmp->weight = wt;
/*Queue is empty or edge to be added has weight less than first edge*/
if (front=-NULL | | tmp->weight<front->weight)
tmp->link = front;
front = tmp;
else
g = front;
while (g->link! =NULL && g->link->weight<=tmp->weight)
g = g->link;
tmp->link = q->link;
g->link = tmp;
if (g->link==NULL) /*Edge to be added at the end*/
tmp->link = NULL;
}
}/*End of insert_pque () */
/*Deleting an edge from the linked priority queue*/
Struct edge *del_pque ()
struct edge *tmp;
tmp = front;
front = front->link;
return tmp;
}/*End of del_pque () */
int isEmpty_pque)
if (front==NULL)
return l;
else
return 0;
}/*End of iS Emptypque () "/
void create_graph)
int i, wt,max_edges, origin, destin;
printf ("Enter number of vertices : ");
Scanf("%d", en) ;
max_edges = n* (n-1) /2 ;
for (i=1; i<max_edges; i++)
printf ("Enter edge %d(-1 -1 to quit): ", i) ;
scanf ("%d %d", &origin, &destin);
if ( (origin==-1) &&
break:
(destinzz-1))
print£ ("Enter weight for this edge : ");
Scanf("%d" ,&wt);
if (origin>=n | | destin>=n | | origin<0 ||
destin<0)
printf (" Invalid edge! \n");
i--;
else
insert_pque (origin, destin, wt) ;
}/*End of Create_graph() */
/*P7. 14 Program for topological sorting*/
#include<stdio. h>
#include<stdl ib. h>
#define MAX 100
int n; /*Number of vertices in the graph*/
idt adj (MAX J (MAXJ i /*Adjacency Matrix*/
void create_graph();
int queue [MAXJ, tront -1,rear = -1:
void insert_queue (int v);
int delete_queue ():
int isEmptyqueue (0;
int indegree(int v);
main(0
int i, V, count,topo_0rder (MAX], indeg (MAXJ:
create_graph() ;
/*Find the indegree of each vertex*/
for (i=0; i<n; i++)
indeg[i) = indegree (i) ;
if (indeg [i] =0)
insert_queue (i) ;
cOunt = 0;
while(!isEmpty_queue () && count<n)
V delete_queue ():
topo_order (++count) = V; /*Add vertex v to topo_order array*/
/*Delete all edges going fron vertex v */
for (i=0; i<n; i++)
if(adj [v] [il==1)
adj [v] [il = 0;
indeg (il = indeg (i]-1 ;
if (indeg [i] ==0)
insert_queue (i) :
if (count<n)
print f ("No topological ordering possible, graph contains cycle\n"):
exit(1) ;
print£ ("Vertices in topological order are :\n"):
for (izl; i<=count; i++)
414
(i]);
printf ("%d , topo_order
printf ("\n");
)*End of main () */
void insert queue (int vertex)
{
if (rear==MAX-1)
n") ;
printf ("Queue Overflow\
else
initially empty */
if (front==-1) /*If queue is
front = 0;
rear = rear+l;
queue [rear] = vertex ;
}/*End of insert_queue() */
int is Empty_queue (0
{
if (front==-1 | | front>rear)
return 1;
else
return 0;
}/*End of isEmpty_queue () */
int delete_queue ()
int del_item;
if (front==-1 | front>rear)
printf("Queue Underflow\n");
exit (1) ;
else
{
del_item = queue [ front};
front = front+1;
return del_item;
)/*End of delete_queue () */
int indegree (int v)
int i, in_deg = 0;
for (i=0; i<n; it+)
if (adj ([il [v] ==1)
in _deg++;
return in_degi
}/*End of indegree() */
The function create_graph() is same as in programP7.9.
algorithm*/
/*P7.11 Program to find shortest path matrix by Modified Warshal1 's
#include<stdio . h>
#include<stdlib.h>
#define infinity 9999
#define MAX 100
int n;/*Number of vertices in the graph */
int adj (MAX] [MAX ]: / *Weighted Adjacency matrix */
int D[MAX) [ MAX]; /*Shortest Path Matrix*/
int Pred[MAX] [MAX]; /*Predecessor Matrix*/
void create_graph() ;
void FloydWarshalls () ;
void findPath (int s, int d);
void isplay (int matrix (MAX] [MAX], int n) ;
main ()
{
int s,d;
Create_graph() ;
FloydWarshalls() ;
while (1)
printf("Enter source vertex (-1 to exit) :");
Scanf("%d", &s);
if (s==-1)
break;
printf( "Enter destination vertex : ");
scanf("%d",&d);
if (s<0 | |s>n-1 | | d<0 | | d>n-1)
{
printf ("Enter valid vertices \n\n");
Graphs
397
continue;
printf("Shortest
findPath(s,d) : path is : "):
print f("Length of this path is
%d\n", D[s) [d]):
1/End of main () *,
void FloydWarshalls )
int i,j,k:
for (i=0: i<n; i++)
for(j=0; j<n; j++)
if (adj (i)3]==0)
{
D[i](j) =
Pred[i) [j)infEinity:
= -1;
else
D[i] [3] = adj (il 3):
Pred[i) [3) =i;
)
for (k=0; k<n; k++)
for (i0; i<n; i++)
for (j=0; j<n; j++)
i£ (D[i) (k] +D[k] (3) < D[i] [j])
D[i] [j) = D[i] (k] +D[k] (3);
Pred[i] [3) = Pred[k] [3]:
printf ("Shortest path matrix is :\n");
display (D, n);
printf ("\n\nPredecessor matrix is : \n");
display (Pred, n);
for (i=0; i<n; i++)
if (D[i](i]<0)
printf("Error : negative cycle\n");
exit (1) :
}/*End of FloydWarshalls ()*/
void findPath(int s,int d)
int i,path(MAX],count;
if (D[s] (a] ==infinity)
printf ("No path \n");
return;
count = -1;
do
{
path(++count) = d;
d = Pred[s] (d):
) while (d!=s);
path( ++count] s;
for (i=count; i>=0; i--)
printf("%d ",path[i));
printf ("\n"):
}/End of findPa th () */
void di splay (int matrix[ MAX] (MAX],int n)
{
int i,j:
for (i=0; i<n; i++)
for (j=0; j<n; j++)
printf ("%7d", matrix (i] [j]) ;
printf("\n");
)
)/End of display () */
The function create graph() is same as in Program P7.9.
