Graphs — Introduction, DFS, BFS, Prims Algorithm, Kruskal’s Algorithm and their Implementations
A graph G consists of a set of V or vertices (nodes) and a set if edges (arcs). Vertices are nothing but the nodes in the graph. Two adjacent vertices are joined by edges.
We write G = (V, E).
V is a finite non empty set of vertices.
E is a set of pairs of vertices. These pairs are called edges.
An edge e=(v, w), is a pair of vertices v and w, and is said to be incident with v and w. There are two types of Graphs i) Undirected graphs and ii) Directed graphs.
Undirected Graph:
V(G)= { 1,2,3,4,5}
E(G)={(1,2), (2,3), (3,4), (4,5), (1,5), (1,3), (3,5)}
You may notice that the edge incident with node 1 and node 5 is written as (1,5); we could also have written (5,1) instead of (1,5). The same applies to all the other edges therefore significant here. This is true for an undirected graph.
In an undirected graph, pair of vertices representing any edge is unordered. Thus (v,w) and (w,v) represent the same edge.
In a directed graph each edge is an ordered pairs of vertices, i.e. each edge is represented by a directed pair.
If e = (v,w) then v is tail or initial vertex and w is head of final vertex.
Subsequently (v,w) and (w,v) represent two different edges.
A Directed Graph
In a directed graph the direction of edge is indicated by an arrow.
V(G) = {1,2,3,4,5}
E(G) = { <1,2>, <2,3> < 3 ,4> <5,3> <5,4> <5,1> }
Directed graph can be referred as diagraph and undirected graph as graph.
Adjacent Vertices:
Vertex v1 is said to be adjacent to vertex v2 if there is an edge (v1, v2) or (v2, v1). let us consider the following graph
Vertices adjacent to node 3 are 1,5,6,4
Vertices adjacent to node 2 are 1 and 7
Path: A path from vertex v to vertex w is a sequence of vertices, each adjacent to the next. Consider the above example again.
- 1,3,4 is a path
- 1,3,6 is a path
- 1,2,7 is a path
- 1,3,4,7 is a path
You may notice that there is a path which starts at vertex 1 and finishes at vertex 1. i.e. path 1,3,4,7,2,1 such a path is called a cycle.
Cycle:- A cycle is a path in which first and last vertices are the same.
Complete graph:
If an undirected graph of n vertices consists of n(n-1)/2 number of edges then it is called as complete graph.
For example: Number of nodes=4
Number of edges=6 i.e. 4(4–1)/2=4*3/2=6
Sub Graph: A sub graph G’ of graph G is a graph such that the set of vertices and set of edges of G’ are proper subset of edges of G.
Weighted graph: A weighted graph is a graph which consists of weights along with edges.
Connected Graph:
A graph is called connected if there exists a path from any vertex to any other vertex. The above graph is a connected graph. There are graphs which are unconnected.
An unconnected graph looks in the following way,
It is one graph having two unconnected components. Since there are unconnected components, it is an unconnected graph.
In a digraph the path is called a directed path and a cycle is called as directed cycle.
- 1,2 is a directed path
- 1,3,5,7,6 is a directed path
- 1,4,5 is not a directed path
There is no directed cycle in the above graph.
Strongly Connected
A digraph is called strongly connected if there is a directed path from any vertex to any other vertex.
There does not exist a directed path from vertex 1 to vertex 4 also from vertex 5 to other vertices and so on. Therefore, it is a weakly connected graph.
Let us make the above graph strongly connected as
Degree: There is no limitation of number of edges incident on one vertex. It could be none, one or more. The number of edges incident on a vertex determines its degree.
- The degree of vertex 3 is 4.
In a digraph we attach an indegree and an outdegree to each of the vertex.
- The indegree of vertex 5 is 2
- Outdegree of vertex 5 is 1
Indegree of vertex v is the number of edges for which vertex v is a head and outdegree is the number of edges for which vertex is a tail.
Tree is a special type of graph. A graph is a tree if it has two properties.
i) It is connected and
ii) There are no cycles in the graph.
Graph Representation: Graph is a mathematical structure and finds its application in many areas of interest in which problems need to be solved using computers. Thus this mathematical structure must be represented as some kind of data structures. Two such representations are commonly used. These are,
- Adjacent matrix and
- Adjacency list representation
The choice of representation depends on the application and function to be performed on the graph.
Adjacency Matrix:
The adjacency matrix A for graph G = (V,E) with n vertices, is an n x n matrix of d bits, such that,
You may observe that the adjacency matrix for an undirected graph is symmetric, as the lower and upper triangles are same. Also all the diagonal elements are zero.
The total number of 1’s account for the number of edges in the digraph. The number of 1’s in each row tells the out degree of the corresponding vertex.
Adjacency List Representation
In this representation, we store a graph as a linked structure. We store all the vertices in a list and then for each vertex, we have a linked list of its adjacent vertices.
The adjacency list representation needs a list of all of its nodes. i.e.
And for each node a linked list of its adjacent node. Therefore we shall have
Note that adjacent vertices may appear in the adjacency list in arbitrary order. Also an arrow from v2 to v3 in the list linked to v1 does not mean that v2 and v3 are adjacent.
Graph Traversal
A graph traversal means visiting all the nodes of the graph. Commonly used two graph traversal methods are as follows,
- Depth First Search (DFS)
- Breadth First Search (BFS)
Depth First Search:
In graphs, we do not have any start vertex or any special vertex signaled out to start traversal from. Therefore the traversal may start from any arbitrary vertex.
We start with vertex v. An adjacent vertex is selected and a depth first search is initiated from it. i.e. V1,V2,….Vk are adjacent vertices to vertex v. We may select any vertex from this list. Say we select v1. Now all the adjacent vertices to v1 are identified and all of those are visited. Next v2 is selected and all its adjacent vertices visited and so on. This process continues till all the vertices are visited. Consider the following graph.
Depth First Search:
- Let us start with V1. Its adjacent vertices are V2, V8, and V3.
- Let us pick on V2. Its adjacent vertices are V1, V4, V5.
- V1 is already visited.
- Let us pick on V4. Its adjacent vertices are V2, V8.
- V2 is already visited.
- Let us pick on V8. Its adjacent vertices are V4, V5, V1, V6, V7.
- V4 and V1 are already visited.
- Let us pick on V5. Its adjacent vertices are V2, V8.
- Both are already visited. Therefore we back track.
We have V6 and V7 unvisited in the list of V8. We may visit any.
- We visit V6.Its adjacent are V8 and V3. Obviously the choice is V3. Its adjacent vertices are V1, V7. We visit V7.
All the adjacent vertices of V7 are already visited, we backtrack and find that we have visited all the vertices. Therefore the sequence of traversal is
We may implement the depth first search method by using a stack, pushing all unvisited vertices adjacent to the one just visited and popping the stack to find the next vertex to visit.
Algorithm for DFS
//Algorithm for Depth First Search
dfs (vertex V)
{
visited [V] = true;
for each w adjacent to V
if (!visited [w])
dfs(w);
}Breadth First Search
In DFS we pick on one of the adjacent vertices; visit all of the adjacent vertices and back track to visit the unvisited adjacent vertices.
In BFS we first visit all the adjacent vertices of the start vertex and then visit all the unvisited vertices adjacent to these and so on.
We start with V1. Its adjacent vertices are V2, V8, V3. We visit all one by one.
We pick on one of these, say V2. The unvisited adjacent vertices to V2 are V4, V5. We visit both. We go back to the remaining visited vertices of V1 and pick on one of those say V3. The unvisited adjacent vertices are V6, V7. There are no more unvisited adjacent vertices of V8, V4, V5, V6 and V7. Thus the sequence so generated is
V1 V2 V8 V3 V4 V5 V6 V7Here we need a queue instead of a stack to implement it. We add unvisited vertices adjacent to the one just visited at the rear and read at front to find the next vertex to visit.
Algorithm for BFS
bfs (vertex v)
{
vertex w;
queue q;
visited [v] = true;
initialise (q);
addqueue (q,v)
while (! Emptyqueue(q))
{
deletequeue (q,v);
for all vertices w adjacent to v
if (!visited [w])
{
addqueue (q,w);
visited[w] = true;
}
}
}
Shortest Path Problem:
We have seen in the graph traversals that we can travel through edges of the graph. It is very much likely in applications that these edges have some weights attached to it. This weight may reflect distance, time or some other quantity that corresponds to the cost we incur when we travel through that edge.
For eg, in the graph we can go from Delhi to Andaman through Madras at a cost of 7 or through Calcutta at a cost of 5. (These numbers may reflect the airfare in thousands.) In these and many other applications, we are often required to find a shortest path. i.e., a path having minimum weight between two vertices.
Length of the path is the sum of weights of the edges on that path. The starting vertex of the path is called the source vertex and the last vertex of the path is called the destination vertex.
Single Source Shortest Path Problem
There are many paths from A to H.
For example,
length of path A F D E H = 1 + 3 + 4 + 6 = 14
A B C E H = 2 + 2 + 3 + 6 = 13We may further look for a path with length shorter than 13 if exists.
Algorithm:
1. We start with source vertex A.
2. We locate the vertex closest to it. B F are adjacent vertices. Length of AF < length of AB so we choose F.
3. Now we look for all the adjacent vertices excluding the just earlier vertex of newly added vertex and the remaining adjacent vertices of earlier vertices, i.e., we have D,E and G (as adjacent vertices of F) and B (as remaining adjacent vertex of A).
We choose vertex B.
4) We go back to step 3 and continue till we exhaust all the vertices.
We choose path AFG.
Therefore the shortest paths from source vertex A to all the other vertices are
AB
ABC
ABD
ABCH
AF
AFE
AFG.SINGLE SOURCE SHORTEST PATH PROBLEM
Let G=(V,E) be a directed graph with weighting function w for the edges of G. The starting vertex of the path is called the source and the last vertex is called the destination. Let v be any other vertex which belongs to set of vertices V. The problem to determine a shortest path to given destination vertex v from source is called single source shortest path problem.
Dijkstra’s Algorithm
//Algorithm shortestpath(G,n,w,dist,v)
// dist[i], 1<=i<=n is the distance or short path starting from source passing through the
// vertices that are in S and ending at i
{
for i:= 1 to n do
{
s[i]:=0; (false)
dist[i]:=w[v,i];
}
s[v]:=1 (true);
dist[v]:=0;
for k:= 2 to n-1 do
{
choose from among vertices not in S such that dist[u] is minimum
s[u]:=1;
for (each e adjacent to u with s[w] =0)
{
if (dist[w]>dist[u]+w[u,w]) then
dist[w]:=dist[u]+w[u,w];
}
}
}
If 1 is the source vertex, the shortest path from 1 to 5 is 6. The shortest path from 1 to all other vertices age given in the table.
The greedy method to generate shortest paths from source vertex to the remaining vertices is to generate these paths in increasing order of path length.
According to Dijkstra’s algorithm, first we select a source vertex and include that vertex in the set S. To generate the shortest paths from source to the remaining vertices a shortest path to the nearest vertex is generated first and it is included in S. Then a shortest path to the second nearest vertex is generated and so on. To generate these shortest paths we need to determine,
- The next vertex to which a shortest path must be generated.
- A shortest path to this vertex.
The first for loop takes O(n) time. Each execution of second for loop requires O(n) time to select the next vertex and again at the for loop to update dist. So that total time for this loop is O(n2). Therefore time complexity for this algorithm is O(n2).
Example 2) Single source shortest path problem
In Divide and Conquer approach, a problem is divided recursively into sub problems of same kind as the original problem, until they are small enough to be solved and finally the solutions of the sub problems are combined to get the solution of the original problem. In Greedy approach, a problem is solved by determining a subset to satisfy some constraints. If that subset satisfies the given constraints, then it is called as feasible solution, which maximizes or minimizes a given objective function. A feasible solution that either maximizes or minimizes an objective function is called as optimal solution.
Spanning Trees
A Spanning tree of a graph is any tree that includes every vertex in the graph. A Spanning tree of a graph G is a sub graph of G that is a tree and contains all the vertices of G containing no circuit or cycle.
An edge of a spanning tree is called a branch
An edge in the graph that is not in the spanning tree is called a Chord.
It spans the graph, i.e. it includes every vertex of the graph.
It is a minimum cost spanning tree i.e. the total weights of all the edges is as low as possible.
Example 1) An Undirected graph and three of its spanning trees
If a graph consist of n vertices then the possible spanning trees are n ^ n-2, for above example n=3, i.e. 3 ^ 3–2=3 spanning trees.
You may notice that all the spanning trees differ from each other significantly, however for each structure
i) The vertex set is same as that of graph G
ii) The edge set is a subset of G(E) and
iii) There is no cycle.
Such a structure is called spanning tree of graph. Take any vertex V as an initial partial tree and add edges one by one so that each edge joins a new vertex to the partial tree.
MINIMAL SPANNING TREE
Frequently we encounter weighted graphs and we need to build a sub-graph that must include every vertex in the graph. To construct such a graph with least weight or least cost we must not have cycles in it.
Consider the above graph. The MST for this graph could be building a least cost communication network.
We begin by first selecting an edge with least cost, it can between any two vertices of graph G. Subsequently from the set of remaining edges, we can select another least cost edge and so on. Each time an edge is picked, we determine whether or not the inclusion of this edge into the spanning tree being constructed creates a cycle. If it does this edge is discarded. If no cycle is created, this edge is included in the spanning tree being constructed.
The minimum cost is BA.
Now we have
The least cost is AC. Therefore we choose AC. Now we have
The least cost is AD. Therefore we choose AD now we have
AF is the minimum cost edge. Therefore we add it to the partial tree. Now we have
Obvious choice is CE.
The only vertex left is G and we have the minimum cost edge that connects it to the tree is BG. Therefore we add it and the minimal spanning tree constructed would be of costs 9 + 3 + 7 + 5 + 4 + 8 = 36.
MINIMUM-COST SPANNING TREES
Let G=(V,E) be an undirected connected graph. A sub graph t=(V,E’) of G is a spanning tree of G if t is a tree.
Applications of Spanning Trees:
1) They can be used to obtain an independent set of circuit equations for an electric network.
2) Using the property of spanning trees that a spanning tree is a minimum su graph G’ of G such that V(G’)=V(G) and G’ is connected. If the nodes of G represent cities, edges of G represent possible communication links connecting the 2 cities, then minimum no of links needed to connect ’n’ cities is (n-1) .
Given a weighted graph in which edges have weights assigned to them where weights represent cost of construction, length of link,… One need to have min total cost or minimum total length. In either case the links selected have to form a tree. If this is not so, then the selection of links contain a cycle.
The identification of min cost spanning tree involves the selection of subset of edges.
The two algorithms used to obtain minimum cost spanning trees from a given graph are
- Prim’s Algorithm
- Kruskal’s Algorithm
Prim’s Algorithm
Algorithm prim(E, cost, n, t)
{
let (k,l) be an edge of minimum cost in E;
mincost := cost[k, l];
t[1,1]:=k;
t[1,2]:=1;
for i:=1 to n do
if (cost[i,l]<cost[i,k]) then near[i]:=l;
else near[i]:=k;
near[k]:=near[l]:=0;
for i:= 2 to n-1 do
{
Let j be an index such that near[j] != 0 and cost[j, near[j]] is minimum
t[I,1]:=j;
t[I,2]:=near[j];
mincost := mincost + cost[j,near[j]];
near[j] := 0;
for k:= 1 to n do
if (near[k]!= 0) and (cost[k,near[k]]>cost[k,j]) then
near[k]:=j;
}
return mincost;
}This is a greedy method to obtain a minimum cost spanning tree which builds the tree edge by edge. The next edge to be included is chosen according to a criteria i.e. choose an edge that results in minimum increase in sum of edges cost so far included.
The algorithm will start with a tree that includes only the min cost edge of ‘G’, then edges are added to this tree one by one. The next edge (i, j) to be added is such that ‘i’ a vertex already included in the tree & ‘j’ is a vertex not yet included, in the tree & cost (i, j) is minimum. Among all edges (i, j) efficiently,. We associate with each vertex j, a value near[j] which is a vertex in the tree such that cost [j, near[j]] is min. among all choices for next near[j]. We define near[j]=0 for all vertices j that are already in the tree.
The next edge to be included is defined by vertex ‘j’ such that near[j]!=0 and cost[j, near[j]] is minimum.
The Time Complexity of Prim’s algorithm is O(n2). The algorithm spends most of the time in finding the smallest edge. So time of the algorithm basically depends on how do we search this edge. Therefore Prim’s algorithm runs in O(n2) time.
KRUSKAL’S ALGORITHM
The set t(edges) is initially empty. As the algorithm progresses, edges are added to ‘t’. When ‘t’ is initially empty, each node of G forms a distinct trivial connected component. As long as no solution is found, partial graph formed by the nodes and edges in the ‘t’ consists of several connected components. The elements of t included in a given connected component form a minimum spanning tree for the nodes in this component. At the end of the algorithm only one connected component remains. So, t is then a minimum spanning tree for all nodes of G. To build bigger and bigger connected components, we examine the edges of G in the order of increasing length. If an edge joins 2 nodes in different connected components, we add it to t. Consequently, the 2 connected components now form a simple one. Otherwise the edge is rejected.
To construct a minimal spanning tree, we use the following procedure.
1) Arrange all edges in the increasing order of weight.
2) Select an edge with minimum weight. This is the first edge of spanning tree T to be constructed.
3) Select the next edge with minimum weight that do not form a cycle with the edges already included in T.
4) Continue step 3 until T contains (n-1) edges, where n is the number of vertices of G.
Kruskal’s Algorithm
Algorithm Kruskal(E,cost,n,t)
{
Construct a heap out of the edge costs using Heapify;
for i:= 1 to n do
parent[i]:= -1;
i:=0;
mincost := 0.0;
while ((i<n-1) and heap not empty)) do
{
delete a minimumcost edge (u,v) from heap;
and reheapify using Adjust;
j:=find(u);
k:=find(v);
if (j!=k) then
{
i:=i+1;
t[i,1]:=u;
t[i,2]:=v;
mincost := mincost+cost[u,v];
union(j,k);
}
}
if (i!= n-1) then
write (“no spanning tree”);
else
return mincost;
}Computing time of Kruskal’s algorithm is O(E log n). Where E is the number of edges.
/****************************************************************
PROGRAM FOR finding the Shortest Path Using Floyd's Algorithm
****************************************************************/
#include <stdio.h>
#include <conio.h>
void main()
{
int c[6][6],a[6][6];
int i,j,k,n;
clrscr();
printf("how many nodes: ");
scanf("%d",&n);for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
printf("Enter cost of path(%d,%d) ",i+1,j+1);
scanf("%d",&c[i][j]);
}for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=c[i][j];for(i=0;i<n;i++)
a[i][i]=0;for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf(" %d",a[i][j]);
printf("\n");
}
getch();
}
Transitive Closure
Transitive closure is basically a Boolean matrix ( matrix with 0 and 1 values) in which the existence of directed paths of arbitrary lengths between vertices is mentioned.
For example
The transitive closure can be generated with depth first search or with breadth first search. This traversing can be done from any vertex. While computing transitive closure we have to start with some vertex and have to find all the edges which are reachable to every other vertex. The reachable edges for all vertices has to be obtained.
Warshal’s Algorithm
While computing the transitive closure, we have to traverse the graph several times. To avoid this repeated traversing through graph a new algorithm is discovered by S.Warshal which is called Warshal’s algorithm. Warshal’s algorithm constructs transitive closure of given digraph with n vertices through a series of n-by-n Boolean matrices. The computations in Warshal’s algorithm are given by the following sequence.
R(0),…R(k-1),…,R(k),…,R(n)
Thus the key idea in Warshal’s algorithm is building of Boolean matrices.
Procedure to be followed:
1.start with computation of R(0). In R(0) any path with intermediate vertices is not allowed. That means only direct edges towards the vertices are considered. In other words the path length of one edge is allowed in R(0). Thus R(0) is adjacency matrix for the digraph.
2.Construct R(1) in which first vertex is used as intermediate vertex and a path length of two edges is allowed. Note that R(1) is built using R(0) which is already computed.
3.Go on building R(0) by adding one intermediate vertex each time and with more path length. Each R(k) has to be built from R(k-1).
4.The last matrix in this series is R(n), in this R(n) all the n vertices are used as intermediate vertices and the R(n) which is obtained is nothing but the transitive closure of given digraph.
Let us understand this algorithm with some example.
Here we have considered only direct edges from each source vertex. If the direct edge is present make 1 in the matrix. Path length is 1.
Here intermediate vertex is ‘a’ and using ‘a’ as intermediate vertex we have to find destination vertices with path length of 2. For instance from d to b a path exists with a as intermediate vertex. Path length up to 2.
Here intermediate vertices are a and b, we have to find path length of upto 3 edges going through intermediate vertices a and b. we will keep adjacency matrix of R(1) as it is and add more 1’s for path length 3 with intermediate vertices a and b. for instance we get d-a-b-c. Hence matrix [d][c]=1.
Here intermediate vertices are a,b and c, we have to find a path length of upto 4 edges going through intermediate vertices a,b and c. for instance a-b-c-d. Hence matrix [a][d]=1
Note that every vertex is reachable from every vertex. Let us formulate this algorithm. The central idea of this algorithm is that we can compute all the elements of each matrix R(k) from previous matrix R(k-1).
/*******************************************************************
PROGRAM FOR TRANSITIVE CLOSURE(WARSHAL'S) ALGORITHM
********************************************************************/
#include <stdio.h>
#include <conio.h>
void main()
{
int c[6][6],a[6][6];
int i,j,k,n;
clrscr();
printf("how many nodes: ");
scanf("%d",&n); for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
printf("Enter cost of path(%d,%d) ", i+1,j+1);
scanf("%d",&c[i][j]);
} for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if (c[i][j]!=0)
a[i][j]=1;
else
a[i][j]=0;
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if (!a[i][j])
a[i][j]=a[i][k]&&a[k][j]; for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf(" %d",a[i][j]);
printf("\n");
}
getch();
}
Program for DFS
/*------------------------------------------------
Graph Traversal using DFS
-------------------------------------------------*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
#define TRUE 1
#define FALSE 0int g[MAX][MAX];
int visit[MAX],n;/*----------------------------- Function to create a graph */
void create()
{
int ch,v1,v2,i,j,flag;
char ans='y';
flushall();printf("enter number of nodes ");
scanf("%d",&n);for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=FALSE;printf("enter the vertex number starting from 1\n");do
{
printf("\nenter vertices of an edge v1 and v2\n");
scanf("%d%d",&v1,&v2);
if (v1>n||v2>n)
printf("invalid vertex\n");
else
{
g[v1][v2]=TRUE;
g[v2][v1]=TRUE;
}
printf("\ndo you want to add more edges ? ");
ans=getche();
}while (ans=='y');
}/*---------------------- function to traverse graph using DFS */
void dfs( int v1)
{
int v2;
printf("%d\n",v1);
visit[v1]=TRUE;
for (v2=1; v2<=MAX; v2++)
if(g[v1][v2]==TRUE && visit[v2]==FALSE)
dfs(v2);
}
void main()
{
int i,j,v1;
clrscr();
create();
printf(" The Adjacency matrix of the graph is \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",g[i][j]);
printf("\n");
}for(i=1;i<=n;i++)
visit[i]=FALSE;printf("enter the vertex from which you want to traverse ");
scanf("%d",&v1);if (v1>=MAX)
printf("Invalid Vertex\n");
else
{
printf("The Depth First Search of the Graph is \n");
dfs(v1);
}
getch();
}
Program for BFS
/*--------------------------------------------------
Graph traversal using Breadth First Search(BFS)
----------------------------------------------------*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
#define TRUE 1
#define FALSE 0int g[MAX][MAX];
int visit [MAX];
int Q[MAX],n,front,rear;/*--------------------------- Function to create graph */
void create()
{
int ch,v1,v2,i,j,flag;
char ans='y';
flushall();printf("enter number of nodes ");
scanf("%d",&n);for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=FALSE;printf("enter the vertex number starting from 1\n");
do
{
printf("\nenter vertices of an edge v1 and v2\n");
scanf("%d%d",&v1,&v2);
if (v1>n||v2>n)
printf("invalid vertex\n");
else
{
g[v1][v2]=TRUE;
g[v2][v1]=TRUE;
}
printf("\ndo you want to add more edges ? ");
ans=getche();
}while (ans=='y');
}/*---------------Function to traverse graph using BFS */
void bfs( int v1)
{
int v2;
visit[v1]=TRUE;
front=rear=-1;
Q[++rear]=v1;
while(front!=rear)
{
v1=Q[++front];
printf("%d\n",v1);
for(v2=1;v2<=n;v2++)
{
if(g[v1][v2]==TRUE && visit[v2]==FALSE)
{
Q[++rear]=v2;
visit[v2]=TRUE;
}
}
}
}/*------------------ main function */
void main()
{
int i,j,v1;
clrscr();create();
printf(" The Adjacency matrix of the graph is \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",g[i][j]);
printf("\n");
}for(i=1;i<=n;i++)
visit[i]=FALSE;printf("enter the vertex from which you want to traverse ");
scanf("%d",&v1);if (v1>=MAX)
printf("Invalid Vertex\n");
else
{
printf("The Depth First Search of the Graph is \n");
bfs(v1);
}
getch();
}
Applications of Graphs:
The graph theory is used in the computer science very widely. There are many interesting applications of graph.
1) In computer networking such as LAN, WAN and internetworking.
2) In telephone cabling graph theory is effectively used.
3) In job scheduling algorithms.
Since graph is nothing but the collection of nodes (vertices) and edges one can find the best suited distance within vertices. If the distance between two vertices is reduced then the cost of cabling and the time in travelling through the nodes will get reduced. Therefore graph theory suggests few interesting algorithms.
