6 Nonlinear Data Structures: Graph

DOI: 10.1201/9781003105800-6

6.1 Concepts and Terminology of Graph

6.1.1 Introduction to Graph

As we know, in the tree structure, the main restriction is that each tree has one root node. However, if we remove that restriction, we end up with a more complex data structure called a graph. In the graph, there is not a root node at all.

6.1.2 Definition of Graph

A graph is defined as a set of nodes or vertices and a set of edges or arcs that connect the two vertices.

A set of vertices is described by listing the vertices as in a set. For example, V = {k, l, m, n} and the set of edges is determined as a sequence of edges. For example, E = {(k, l), (m, n), (k, n), (l, m)}

The graph is commonly defined as follows:

1. G = (V, E)

where V (G) is a finite, non-empty set of vertices of a graph, G. E (G) is a set of pairs of vertices or arcs each representing an edge of a graph.

6.1.3 Types of Graph

6.1.3.1 Directed, Undirected and Mixed Graph

Directed graphs are also called digraphs. A directed graph or digraph is a collection of nodes connected by edges, where the edges have a direction linked with them.

An undirected graph is a type of graph, in which a set of vertices or nodes are connected, and all the edges are bidirectional.

In directed graphs, the directions are shown on the edges (Figure 6.1).

FIGURE 6.1 Directed graph.

As shown in Figure 6.1., the edges between vertices are ordered. In this type of graph, edge E₁ is in between vertices v1 and v2. The v1 is called head and v2 is called tail. We can say, E₁ is set of (V₁, V₂) and not of (V₂, V₁).

Similarly, in an undirected graph, edges are not ordered (Figure 6.2).

FIGURE 6.2 An undirected graph.

In this type of graph, that is an undirected graph, the edge E₁ is set of (V₁, V₂) or (V₂, V₁).

Consider the following directed graph (Figure 6.3):

FIGURE 6.3 Directed graph.

1. V(G) = {A, B, C, D}
2. E(G) = {(A,A),(B,A),(B,D),(D,C),(A,B),(B,C),(A,C)}

In Figure 6.3, edge (A, B) and edge (B, A) are two different edges through both the edges that connect vertex A and vertex B. Some edges may connect one node with itself. These edges are called loops. For example, edge (A, A) is a loop.

The degree of a vertex is the number of edges incident to it. In-degree of a vertex is the number of edges pointing to that vertex and out-degree of a vertex is the number of edges pointing from that vertex. For example, the out-degree of node B in Figure 6.3 is 3, and its in-degree is 1 and degree of node B is 4.

Note: A tree is a special case of a directed graph.

A graph need not be a tree, but a tree must be a graph. In a graph, a node that is not adjacent to any other node is called an isolated node (Figure 6.4).

FIGURE 6.4 Graph containing isolated node D.

For example, node D in a graph is an isolated node shown in Figure 6.4. The degree of an isolated node is zero.

A graph with undirected and directed edges is said to be a mixed graph as shown in Figure 6.5.

FIGURE 6.5 Mixed graph.

6.1.3.2 Null Graph

A graph containing only an isolated node is called a null graph. A null graph contains an empty set of edges (Figure 6.6).

FIGURE 6.6 Null graph.

6.1.3.3 Complete Graph

If an undirected simple graph of ‘n’ vertices consists of n (n-1)/2 number of edges, then it is called a complete graph. The complete graph does not contain any loop edge. Here each node is connected. If the graph contains four nodes, then each node’s degree is three in a complete graph as shown in Figure 6.7.

FIGURE 6.7 Complete graph.

6.1.3.4 Strongly Connected Graph

A digraph is said to be strongly connected if for every pair of vertex there exists a path, that is, in such a graph path between V1and V2exist,then there is a path from V2to V1 is also present. For example, in Figure 6.8, a graph is a strongly connected graph.

FIGURE 6.8 Strongly connected graph.

6.1.3.5 Unilaterally Connected and Weakly Connected Digraph

A simple digraph is said to be unilaterally connected if for any pair of nodes of a graph at least one of the nodes of a pair is reachable from the other node.

The concept of “strongly connected” and “weakly connected” graphs are concerned with directed graphs.

If for any pair of nodes of the graph, both the nodes of the pair are reachable from one another, then the graph is called strongly connected.

If the digraph is treated as an undirected graph (means directions are not considered), and when it is connected graph, there exists a path from any pair of vertex to another and only then the graph is called weakly connected graph.

A unilaterally connected digraph is a graph in which every pair of node their exists either a path from node v1 to v2 or v2 to v1 for each pair of node as shown in Figure 6.9b.

FIGURE 6.9 Unilaterally connected, strongly connected, and weakly connected digraph. (a) Strongly connected graph. (b) Weakly connected graph but not unilaterally connected. (c) Unilaterally connected but not strongly connected.

While a unilaterally connected digraph is weakly connected, but a weakly connected digraph is not necessarily unilaterally connected.

A strongly connected digraph is, at the same time, unilaterally and weakly connected.

6.1.3.6 Simple Graph

A graph G is called a simple graph if the graph does not contain any loop or parallel edges. The graph shown in Figure 6.10 is simple.

FIGURE 6.10 Simple graph.

6.1.3.7 Multigraph

A graph G is called a multigraph if a graph contains loop or parallel edges. The graph shown in Figure 6.11 is a multigraph.

FIGURE 6.11 Multigraph.

6.1.3.8 Cyclic Graph

A graph with at least one cycle is known as a cyclic graph.

In Figure 6.12, the graph contains v1-v2-v3-v4-v1, v1-v3-v4-v1 and v3-v4-v3 cycles, so the above graph is called a cyclic graph.

FIGURE 6.12 Cyclic graph.

6.1.3.9 Acyclic Graph or Non-cyclic Graph

A graph with no cycles is called an acyclic graph or a non-cyclic graph.

In Figure 6.13., the graph does not have any cycles. Hence, it is a non-cyclic graph or an acyclic graph.

FIGURE 6.13 Acyclic graph.

6.1.3.10 Bipartite Graph

A simple graph G = (V, E) with vertex or nodes are partition into set V1 and V2 where V = {V1, V2} and V1 ∩ V2 = ф is called a bipartite graph if every edge of E joins a vertex in V1 to a vertex in V2.

In general, a bipartite graph has two sets of vertices, let us say, V1 and V2, and if an edge is drawn, it should connect any vertex in set V1 to any vertex in set V2. The graph shown in Figure 6.14 is bipartite.

FIGURE 6.14 Bipartite graph.

6.1.3.11 Complete Bipartite Graph

A complete bipartite graph is a simple graph in which the vertices can be partitioned into two disjoint sets V1 and V2 such that each vertex in V1 is adjacent to each vertex in V2. A complete bipartite graph is shown in Figure 6.15.

FIGURE 6.15 Complete bipartite graph.

Here, a bipartite graph is a simple graph where every vertex of the first set V1 is connected to every vertex in the second set V2.

6.2 Representation of Graph Using Adjacency Matrix and Adjacency List

There are two commonly used graph representation techniques:

1. Adjacency matrix representation
2. Adjacency lists representation

6.2.1 Adjacency Matrix Representation

6.2.1.1 Definition of Adjacency Matrix

Consider a graph G with a set of vertices V(G) and a set of edges E(G). If there are N nodes in V(G), for N >= 1, the graph G may be represented by an adjacency matrix which is a table with N rows and N columns where

A(i, j) = 1 if and only if there is an edge (V_i, V_j ) in E(G) 0 otherwise

If there is an edge connecting V_i and V_j in E (G), the value in the [i, j] position in the table is 1, otherwise, it is 0.

In this representation, the graph may be represented using a matrix of a total number of vertices per total number of vertices. This means if a graph with five vertices can be represented using a matrix of size 5 × 5. Within this matrix, both rows and columns are vertices. This matrix is filled with either 1 or 0. Here, 1 represents that there is an edge from row vertex to column vertex, and 0 describes that there is no edge from row vertex to a column vertex.

6.2.1.2 Example of Adjacency Matrix

See Figures 6.16 and 6.17.

FIGURE 6.16 Directed graph, G.

FIGURE 6.17 Adjacency matrix of directed graph G.

If the relation between two nodes is unordered, the graph is called an unordered or undirected graph (Figures 6.18 and 6.19).

FIGURE 6.18 Undirected graph, G.

FIGURE 6.19 Adjacency matrix of undirected graph G.

6.2.1.3 Algorithm of Creating or Representing Graph Using Adjacency Matrix

The algorithm for the creation of the graph using adjacency matrix will be as follows:

1. Declare an array of M [size] [size] which will store the graph, where the size = number of maximum nodes which we have stored in the graph.
2. Enter how many nodes you want in a graph.
3. Enter edges of graph by two vertices each say V_i, V_j indicates some edge.
4. If the graph is directed set M [i] [j] = 1. If the graph is undirected set M [i] [j] = 1 and M [j] [i] = 1 as well.
5. When all edges in the desired graph are entered, print the graph M [i] [j].

6.2.2 Adjacency List Representation

6.2.2.1 Basics of Adjacency List Representation

The use of the adjacency matrix to represent a graph is inappropriate due to its static implementation. To use this representation, we must know in advance the number of nodes that a graph has in order to set up storage. The solution to this problem is to use a linked structure, which makes allocations and de-allocations from an available pool. We will represent the graph using adjacency lists. This adjacency list stores information about only those edges that exist. The adjacency list contains a directory and a set of linked lists. This representation is also known as node directory representation. The directory contains one entry for each node of the graph. Each entry in the directory points to a linked list that represents a node that is connected to that node. Directory represent nodes and the linked list represent the edges.

Each node of the linked list has three fields:

1. Node identifier,
2. Link to next field,
3. An optional weight field contains the weight of the edge.

An undirected graph can also be stored using an adjacency list; however, each edge will be represented twice, once in each direction.

In general, an undirected graph of order N, which is the number of nodes N, with E edges requires N entries in the directory and 2*E linked list entries, whereas a directed graph will require N entries in the directory and E linked list entries.

6.2.2.2 Example of Adjacency List Representation for Directed Graph

Figure 6.22 shows the node directory representation of the directed graph as shown in Figure 6.20.

FIGURE 6.20 A directed graph.

The out-degree of a node in a directed or undirected graph can be determined by counting the number of entries in its linked list. Here, in Figure 6.21, node 2 having three nodes in its linked list, that is, node 2 has out-degree 3. However, node 2 does not present in the linked list means node 2 having zero in-degree. Similarly, count node 4 in the linked list part, which is two in number, so node 4 has in-degree two.

FIGURE 6.21 Sample node.

However, it is difficult to determine the in-degree of node, but we can easily obtain the out-degree (Figure 6.22).

FIGURE 6.22 Node directory representation for directed graph.

6.2.2.3 Example of Adjacency List Representation for Weighted Graph

Figure 6.23 shows a weighted graph (Figure 6.24), and Figure 6.25 shows its node directory representation for a weighted graph.

FIGURE 6.23 Weighted graph.

FIGURE 6.24 Sample node.

FIGURE 6.25 Node directory representation for a weighted graph.

6.3 Graph traversal Techniques (Breadth First Search and Depth First Search)

Graph traversal is a procedure used to search for a vertex or node in a graph. The graph traversal is also used to decide the order of vertices be visited in the search process only once. A graph traversal finds the edges to be used in the search process without creating loops that means using graph traversal, we visit all vertices of the graph only at one time without getting into a looping path. The majority of graph problems involve the traversal of a graph. Traversal of a graph means visiting each node exactly once.

There are two types of graph traversal techniques, and they are as follows:

1. Breadth first search (BFS)
2. Depth first search (DFS)

6.3.1 BFS Traversal of a Graph

6.3.1.1 Basics of BFS

In the graph, say vertex V₁ in a graph will be visited first, then all vertices adjacent to V₁ will be traversed suppose adjacent to V₁ are (V₂, V₃) then again from V₂ adjacent vertices will be printed. This process will be continued for all the vertices to be encountered. To keep track of all vertices and their adjacent vertices, we will make use of an array for the visited nodes. The nodes that get visited are set to 1. Thus, we can keep track of visited nodes.

6.3.1.2 Algorithm of BFS Traversal of a Graph

// Array visited [ ] is initialized to 0.
// q is queue-type data structure.
// BFS traversal on graph G is carried out beginning at
   vertex V.
void  BFS( int v)
{ 
  q: a queue type variable
  Initialize q;
  visited[ v] = 1;    //mark v as visited
  add vertex v to queue q;
  while( q is not empty )
  {
  Print node v;
  v  → delete an element from the queue ;
  for all vertices w adjacent from v
  { 
       if ( ! visited[ w] ) 
       {
       visited[ w] = 1;
       add the vertex w to queue q;
       } // completion of if statement
 } // completion of for loop
} // completion of while loop 
} // completion of BFS function

6.3.1.3 Example of BFS

Find BFS traversal for following graph G (Figure 6.26).

FIGURE 6.26 Given graph G.

Solution:

Step 1:

1. Start from BFS (1),
2. Print value 1,
3. Delete node 1 from the queue and insert not visited adjacent nodes to the queue.

Step 2:

1. Print value 2,
2. Delete node 2 from the queue and insert not visited adjacent nodes of 2 into the queue.

Step 3:

1. Adjacent nodes of 2 are {1, 5, 3, 6} but 1 and 3 are already visited so discard it and add 5 and 6 nodes into the queue.
2. Print value 3,
3. Delete node 3 and insert non-visited adjacent node to the queue, then

Step 4:

1. Adjacent nodes of node 3 are {1, 2, 6}, but all are already visited so discard it, and no node is added into the queue.
2. Print value 4,
3. Delete node 4 and insert non-visited adjacent nodes to the queue, then

Step 5:

1. Adjacent nodes of node 4 are {1, 7, 8}, but 1 is already visited so discard it and insert 7 and 8 to the queue.
2. Print value 5,
3. Delete node 5 and insert non-visited adjacent nodes to the queue, then

Step 6:

Adjacent nodes of node 5 are {6, 2} already visited.

1. Print value 6,
2. Delete node 6 and insert non-visited adjacent nodes to the queue, then

Step 7:

1. Adjacent nodes of node 6 are {5, 2, 3} already visited.
2. Print value 7,
3. Delete node 7 and insert non-visited adjacent node to the queue, then

Step 8:

1. Adjacent nodes of node 7 are {4, 8} already visited.
2. Print value 8,
3. Delete node 8 and insert non-visited adjacent nodes to the queue, then

Step 9:

1. Adjacent nodes of node 8 are {7, 4} already visited.
2. Queue is now empty because front > rear or front index cross to the rear index, this condition shows that queue is empty, then stop the BFS algorithm.
3. We get the following trace as follows:
4. By using this trace, we will find the BFS spanning tree, which is as follows:
5. Before that, spanning tree is a subset of Graph G, which has all the nodes or vertices covered with the minimum possible number of edges. Hence, a spanning tree does not have cycles or loops, and it cannot be disconnected (Figure 6.27).

   

   FIGURE 6.27 BFS spanning tree of Figure 6.25.

6. Nodes of the tree are printed in order of their level.
7. Finally, the nodes are visited by using BFS is as follows:
   1. 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8.

6.3.1.4 Implementation of Graph Traversing Using the BFS Technique

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define waiting 2
#define visited 3
int n;
int adj[MAX][MAX];
int state[MAX];
void create_graph(); //Create a graph using adjacency matrix
void BF_Traversal();  // traverse a graph using BFS technique 
void BFS(int v);                 // Breadth first search function

int queue[MAX], front = -1,rear = -1;
void insert_queue(int vertex);
int delete_queue();
int isEmpty_queue();

// main function definition
int main()
{
create_graph();
BF_Traversal();
return 0;
}

void BF_Traversal()
{
int v;
for(v=0; v<n; v++)
state[v] = initial;
printf("Enter start Vertex for BFS: \n");
scanf("%d", &v);
BFS(v);
}
// pass node v as the first node for traversing graph using
BFS traversing technique
void BFS (int v)
{
int i;
insert_queue(v);
state[v] = waiting;
//Continue the while loop till queue is not empty
while( !isEmpty_queue() )
{
v = delete_queue( );
printf("%d ",v);
state[v] = visited;
//check all adjacent nodes of node v and check whether the
adjacent nodes are visited or not
for(i=0; i<n; i++)
{
if(adj[v][i] == 1 && state[i] == initial)
{
insert_queue(i);
state[i] = waiting;
} //if completed
} // for loop completed 
} // while loop completed
printf("\n");
}
//insert vertex or node in the queue
void insert_queue (int vertex)
{
if(rear == MAX-1)
{
printf("Queue is full\n");
}
else
{
if(front == -1)
{
front = 0;
}
rear = rear+1;
queue[rear] = vertex ;
}
}
//Queue is empty or not function 
int isEmpty_queue ()
{
if(front == -1 || front > rear)
return 1;
else
return 0;
}
//delete node from the queue
int delete_queue ()
{
int delete_item;
if (front == -1 || front > rear)
{
printf ("Queue is empty \n");
exit(1);
}
delete_item = queue[front];
front = front+1;
return delete_item;
}
//create adjacency graph and initialize it
void create_graph()
{
int count, max_edge, origin, destin;
printf("Enter number of vertices : ");
scanf("%d", &n);
max_edge = n*(n-1);
for(count=1; count<=max_edge; count++)
{
printf("Enter edge %d( -1 -1 to quit ) : ",count);  //exit
from for loop enter -1 -1
scanf("%d %d", &origin, &destin);
if((origin == -1) && (destin == -1))
break;

if(origin>=n || destin>=n || origin<0 || destin<0)//Check node
numbers are in between 0 and n-1
{
printf("Invalid edge!\n");
count--;
}
else
{
adj[origin][destin] = 1;  //Otherwise insert the edge into the
adjacency array
}
} // for loop completed 
}

Output:

6.3.1.5 Time Complexity of BFS

If the graph is implemented using an adjacency matrix, that is, an array of size V × V, then, for each node, you have to traverse an entire row of length V in the matrix to discover all its outgoing edges. Therefore, the time complexity of BFS is T (n) = O(n² ) where n is the number of vertices in the graph.

If your graph is implemented using adjacency lists or node directory representation, wherein each node maintains a list of all its adjacent edges, then, for each node, you could discover all its neighbors by traversing its adjacency list just once in linear time. Therefore, the time complexity of BFS is T (n) = O ( V + E ), where V is the number of vertices in the graph and E is the number of edges in the graph.

6.3.1.6 Advantages of BFS

1. In this procedure in any way, it will find the goal.
2. It finds the minimal solution in the case of multiple paths.

6.3.1.7 Disadvantages of BFS

1. BFS consumes large memory space. Its time complexity is more.
2. It has long pathways when all paths to a destination are on approximately the same search depth.

6.3.1.8 Applications of BFS

1. Finding the shortest path from source to other vertices in an unweighted graph.
2. Finding the quick and efficient solution of a puzzle such as Rubik’s cube by applying BFS on the state space.
3. Creating bipartite graphs.

6.3.2 . DFS Traversal of a Graph

6.3.2.1 Basics of DFS

In the DFS traversal of a graph, we follow the path as deeply as we can go. When there is no adjacent vertex present, then we travel backward and look for the not-visited vertex. We will maintain a visited array to mark all the visited vertices. A node already reported as visited should not be selected for the traverse. Marking of visited vertices can be performed using a global array visited[ ]. The visited array[ ] is set to zero.

6.3.2.2 Non-recursive DFS Algorithm

1. Push node V1 on the stack.
2. Print node V1 value.
3. Mark node V1 value in the visited array as 1.
4. Find all adjacent nodes of node v1.
5. Repeat step 4 until all adjacent node ends.
6. If node v1 does not have any adjacent node, then pop node V1 from the stack.
7. Repeat steps 1–6 until the stack is empty.

6.3.2.3 Recursive DFS Algorithm

1. Step 1: Start
2. Step 2: n - number of nodes in graph G.
3. Step 3: Initialize visited [ ] to 0

for(i=0; i<n; i++)
visited [i]= 0

1. Step 4: Void DFS (vertex i)

                           {
                           print i;
                           visited [i] = 1;
                           for each w adjacent to i
                           if (! visited [w])
                           DFS (w);
                           }
   

2. Step 5: stop.

6.3.2.4 Explanation of Logic for Depth First Traversal (DFS)

In DFS, the basic data structure for storing the adjacent nodes is stack. In our program, we have used a recursive call to the DFS function. When a recursive call is invoked, a push operation is performed. When we exit from the loop, a pop operation will be performed (Figure 6.28).

FIGURE 6.28 An undirected graph.

Step 1: Start with vertex 0, print it so ‘0’ node is printed. Mark 0 node as visited.

Step 2: Find adjacent vertex to 0, there are two adjacent vertices 1 and 2, out of that choose one say node 1 is chosen if it is not visited, call DFS (1), that is, 1 will get inserted into the stack, mark node 1 as visited in the visited array.

After exiting loop 1 will be popped and print 1.

Step 3: Find adjacent to 1 that is vertex 0 or 3 but 0 is already visited, so remaining node 3 is chosen if it is not visited and call DFS (3), that is, 3 will get pushed onto stack, mark it as visited in a visited array.

After existing, loop 3 will be popped and print 3.

Step 4: Find adjacent to 3 that is vertex 2 if it is not visited call DFS (2), that is, 2 will be pushed onto the stack and mark node 2 as visited in a visited array.

After existing, loop 2 will be popped and print 2.

Since all nodes are visited once then stop the procedure.

So the output of DFS is 0 1 3 2.

6.3.2.5 Implementation of Graph Traversing Using the DFS Technique

#include<stdio.h>
void DFS( int );  //DFS function declaration
int G[10][10], visited[10], n;  //n is number of vertices and
                                graph is stored in array G[10][10]
                                //visited[10] is visited array 
//main function definition
int main()
{
int i, j;
printf("Enter number of vertices: \n");
scanf("%d",&n);
//read the adjacency matrix, enter 1 if edge is present and 0
if edge is not present
printf("Enter adjacency matrix of the graph: \n");
for(i=0;i<n;i++)
{
        for(j=0;j<n;j++)
        {
        scanf("%d",&G[i][j]);
        }
}
//visited array is initialized to zero
for(i=0;i<n;i++)
{
        visited[i]=0;
}
//call DFS with 0 node as start node
printf("DFS traversal of a graph : ");
DFS(0); 
return 0;;
}
//Recursive DFS function definition
void DFS (int i)
{
int j;
printf("\t %d",i);
visited[i]=1;
for(j=0;j<n;j++)
{
        if( !visited[j] && G[i][j] == 1)
        {
        DFS(j);
        }
}
}

Output:

6.3.2.6 Time Complexity of DFS

If graph is implemented using an adjacency matrix, that is, an array of size V × V, then, for each node, you have to traverse an entire row of length V in the matrix to discover all its outgoing edges. Therefore, the time complexity of DFS is T (n) = O (n²) where n is the number of vertices in the graph.

If your graph is implemented using adjacency lists or node directory representation, wherein each node maintains a list of all its adjacent edges, then, for each node, you could discover all its neighbors by traversing its adjacency list just once in linear time. Therefore, the time complexity of DFS is T (n) = O (V + E), where V is the number of vertices in the graph and E is the number of edges in the graph.

6.3.2.7 Advantages of DFS

1. DFS consumes very little memory space.
2. It will reach the goal node in less period than BFS if it traverses in the right path.

6.3.2.8 Disadvantages of DFS

1. Many states may keep reoccurring.
2. Sometimes the states may also enter into infinite loops.

6.3.2.9 Applications of DFS

1. For finding connected components of the graph.
2. For finding strongly connected components.
3. For solving maze problems.
4. For finding cycles in graphs and finding the largest cycle in graph.

6.4 Applications of Graph as Shortest Path Algorithm and Minimum Spanning Tree

6.4.1 Shortest Path Algorithm

Let G = (V, E) be a graph with n vertices.

The problem is to find out the shortest distance from the vertex to all other vertices of a graph.

6.4.1.1 Dijkstra’s Algorithm for Shortest Path

Dijkstra’s algorithm is also called a single source shortest path algorithm. It is based on a greedy or optimal technique. Greedy algorithm is the algorithm, which picks the best solution at the moment without regard for consequences. In this algorithm, we use

1. Visited array
2. Cost matrix
3. Distance matrix

6.4.1.2 Dijkstra’s Algorithm

1. Start.
2. Create a cost matrix C [ ] [ ] from the adjacency matrix adj[ ] [ ].
   1. C [i] [j] is a cost of going from vertex i to vertex j.
   2. If there is no edge between vertices i and j, then C [i] [j] is set to be infinity.
3. Array visited [ ] is initialized to zero.

   for (i=0; i<n; i++)
   visited [i]=0;
   

4. If vertex 0 is the source vertex, then visited [0] is marked as 1.
5. Build the distance matrix by storing the cost of vertices from vertex number 0 to (n-1) from the source vertex 0.

   for (i=1; i<n; i++)
        distance [i] = cost [0] [i] ;
   

   Initial distance of source vertex is initiated as 0. that is. distance [0].

6. for (i=1; i<n; i++)

   Choose a vertex w, such that distance [w] is minimum and visited [w] is 0.

   Mark visited [w] as 1.

   Recompute the shortest distance of rest vertices from the source. Only the vertices not

   marked as 1 in array visited [ ] should be considered for recalculation of distance.

   That is,

   for each vertex v
   if (visited[v]==0)
   distance [v]=min (distance[v], distance[w] + cost[w][v])
   

7. Stop.

6.4.1.3 Time Complexity

T (n) = O (n²)

6.4.1.4 Example Showing Working of Dijkstra's Algorithm

Show working of Dijkstra’s algorithm on a graph given as below (Figure 6.29):

FIGURE 6.29 Given undirected weighted graph G.

Solution:

Source vertex is taken as 0.

Cost matrix:

Distance matrix:

Visited array:

First iteration:

1. Select vertex 0.
2. Mark visited [0] as 1.
3. Calculate distance of vertex 1 from 0 using cost matrix. Cost of vertex 1 from 0 is 10.
4. Cost of vertices 3 and 4 from vertex 0 is 30 and 100, respectively. Therefore, update the distance matrix.

   Distance matrix:

   

   Visited array

   Second iteration:

   1. Select vertex 1.
   2. Mark visited [1] as 1.
   3. Re-adjust distances.
   4. Cost of going to vertex 2 from the source vertex 0, through selected vertex 1 is given by, distance [1] + cost [1] [2] = 10 +50 = 60. Distance of 60 is better than existing distance of ∞ or infinity.
   5. Cost of going to vertex 3 from the source vertex 0, through selected vertex 1 is given by, distance [1] + cost [1] [3] = 10 + ∞=∞ which is worse than existing distance of 30.
   6. Similarly, cost of going to vertex 4 through vertex 1 is ∞ which is worse than existing distance of 100.

   Distance matrix:

   

   Visited array:

   Third iteration:

   Vertex selected = 3

   Cost of going to vertex 2 through 3 = dist[3] + cost[3] [2] = 30+20 = 50

   Cost of going to vertex 4 through 3 = dist[3] + cost[3] [4] = 30+60 = 90

   Distance of vertices 2 and 4 should be changed.

   

   Distance matrix:

   

   Visited array:

   Fourth iteration:

   Vertex selected = 2

   Cost of going to vertex 4 through 2 = dist[2] + cost[2] [4] = 50+10 = 60

   Distance of vertex 4 should be changed.

   

   Distance matrix with final distances:

   

   Visited array:

6.4.2 Minimum Spanning Tree

6.4.2.1 Basic Concept of Spanning Tree and Minimum Spanning Tree

A spanning tree is a minimal sub-graph of a given graph and they follow or satisfy all of the following three conditions:

1. A number of vertices in a spanning tree are equal to the number of vertices in a given graph G.
2. A minimal sub-graph or tree has a lesser number of edges than the given graph G.
3. Minimal spanning tree should be connected and there should not be any cycle.

Simply, a spanning tree is a subset of an undirected Graph that has all the vertices connected by a minimum number of edges.

If all the vertices are connected in a graph, then there exists at least one spanning tree. In a graph, there may exist more than one spanning tree. If graph G, contains ‘n’ vertices, then the spanning tree contains ‘n’ vertices and (n-1) edges.

6.4.2.2 Properties Spanning Tree

1. There is no cycle in a spanning tree.
2. Any vertex can be reached from any other vertex.

A Minimum Spanning Tree (MST) is a subset of the edges of a connected weighted undirected graph that connects all the vertices with the minimum possible total edge weight.

6.4.2.3 Example of Spanning Tree

Given Graph G =

Here in the spanning tree, all the vertices are visited as in graph G, but the edges are less than graph G (Figures 6.30 and 6.31).

FIGURE 6.30 Undirected graph G.

FIGURE 6.31 Given undirected graph G and its four spanning trees.

Finding a spanning tree of a weighted graph G, having minimum cost can be calculated using Greedy strategy.

Feasible solution: Final graph must contain all vertices, and they must be connected with no cycle.

Optimal solution: It is a feasible solution with the minimum cost.

There are two types of algorithms to find MST:

1. Prime’s algorithm
2. Kruskal’s algorithm

6.4.2.4 Prime’s Algorithm

Let G (V, E) is a connected weighted undirected graph with no loops and parallel edges. If graph G contains any parallel edge, then choose a less weight edge from the parallel edge and remove another one. Also, if any loop is there in the graph, then remove that loop also. Therefore, after removing the loop and the largest parallel edge if any from graph G. Now for graph G, we will find the MST using Prime’s algorithm.

Prime’s Algorithm

1. Label all the vertices as unchosen.
2. Let the tree T consist of ‘n’ nodes, initially with no edge. T is also called a solution vector.
3. Choose any arbitrary vertex ‘u’ and label it as chosen.
4. while (there is an unchosen vertex)

   {
   pick the lightest edge between any chosen 'u' and unchosen 'v'
   label v as chosen T  = T + <u, v>
   if and only  <u, v> does not give rise to cycle in T
   }
   

Now we will represent Prime’s algorithm in different ways as follows:

Let G(V, E) is a connected weighted undirected graph with no loops and parallel edges.

1. Create two sets V and V’ such that V’ is empty initially.
   1. V contains all vertices of graph G.
   2. Select minimum weighted edge (i, j) from G and add i and j into set V’.
2. T is the solution vector that contains no edges initially, that is, it is an empty set of edges.
3. Repeat step 4 while V is not equal to V’.
4. Find all neighbors of all vertices which are in set V’ such that one endpoint of the neighboring edge is in V’ and another not in V’ or another is present in V. In addition, edge weight is minimum and not form a loop or cycle. That edge to add to the solution vector T.
5. Make the sum of all selected edge weights that gives us the minimum weighted spanning tree.
6. Stop.

Example: Calculate minimum cost-spanning tree using Prime’s Algorithm (Figure 6.32).

FIGURE 6.32 Given undirected weighted graph G.

Solution:

1234567AdjacencyMatrix:[∞1∞4∞∞∞1∞264∞∞∞2∞∞56∞46∞∞3∞4∞453∞87∞∞6∞8∞3∞∞∞473∞]

Step 1:

Set V = {1, 2, 3, 4, 5, 6, 7}

Set V’ = empty set initially

T = { } = empty set initially

Step 2: First iteration:

By choosing 1 as a starting node

V’ ={ 1, 2}

T ={ <1,2> }

Step 3: Second iteration:

<2, 3> edge having minimum weight and does not form a cycle so choose <2, 3> edge and insert into the solution vector T. Node 3 is inserted into the set V’.

V’ ={ 1, 2, 3}

T ={ <1, 2>, <2, 3> }

Step 4: Third iteration:

<1, 4> edge having minimum weight and does not form a cycle so choose <1, 4> edge and insert into the solution vector T. Node 4 is inserted into the set V’.

V’ ={ 1, 2, 3, 4}

T ={ <1, 2>, <2, 3>, <1, 4> }

Step 5: Fourth iteration:

<4, 5> edge having minimum weight and does not form a cycle so choose <4, 5> edge and insert into the solution vector T. Node 5 is inserted into the set V’.

V’ ={ 1, 2, 3, 4, 5}

T ={ <1, 2>, <2, 3>, <1, 4>, <4, 5> }

Step 6: Fifth iteration:

<4, 7> edge having minimum weight and does not form a cycle so choose <4, 7> edge and insert into the solution vector T. Node 7 is inserted into the set V’.

V’ ={ 1, 2, 3, 4, 5, 7}

T ={ <1, 2>, <2, 3>, <1, 4>, <4, 5>, <4, 7> }

Step 7: Sixth iteration:

<7, 6> edge having minimum weight and does not form a cycle so choose <7, 6> edge and insert into the solution vector T. Node 6 is inserted into the set V’.

V’ ={ 1, 2, 3, 4, 5, 7, 6}

T ={ <1, 2>, <2, 3>, <1, 4>, <4, 5>, <4, 7>, <7, 6> }

Step 8: Seventh iteration:

Now V’ = V, so terminate the loop.

Step 9: Add weights of all edges in solution vector T as,

1 + 2 + 4 + 3 + 4 + 3 =17

Step 10: Stop the algorithm.

The above algorithm is also explained in the following way (Figure 6.33):

FIGURE 6.33 Minimum cost-spanning tree for graph G.

1. Select Node 1:
   1. 1 – 2 → 1 ✓
   2. 1 – 4 → 4 ✓
2. Select Node 2:
   1. 2 – 1 → 1
   2. 2 – 3 → 2 ✓
   3. 2 – 4 → 6
   4. 2 – 5 → 4
3. Select Node 3:
   1. 3 – 2 → 2
   2. 3 – 5 → 5
   3. 3 – 6 → 6
4. Select Node 4:
   1. 4 – 1 → 4
   2. 4 – 2 → 6
   3. 4 – 5 → 3 ✓
   4. 4 – 7 → 4 ✓
5. Select Node 5:
   1. 5 – 2 → 4
   2. 5 – 3 → 5
   3. 5 – 4 → 3
   4. 5 – 6 → 8
   5. 5 – 7 → 7
6. Select Node 7:
   1. 7 – 4 → 4
   2. 7 – 5 → 7
   3. 7 – 6 → 3 ✓
7. Select Node 6:
   1. 6 – 3 → 6
   2. 6 – 5 → 8
   3. 6 – 7 → 3

Minimum weight = 1+2+4+3+4+3 = 17

Another minimum cost-spanning tree for graph G can be as follows (Figure 6.34):

FIGURE 6.34 Minimum cost-spanning tree for graph G.

Minimum weight = 1+2+3+4+4+3 = 17

Disadvantages of Prime’s Algorithm:

1. The list of edges has to be searched from the beginning as a new edge is added.
2. If there is more than one edge with the same weight, then all possible spanning trees are required to be found for minimal tree.

Complexity Analysis of Prime’s Algorithm:

1. Complexity analysis is based on an algorithm that uses the cost matrix as a data structure and works on it. Since the matrix has to be scanned repeatedly the time complexity of the algorithm is O (n²).
2. Prime’s Algorithm does not use the Greedy Method fully because at the first step it gives the freedom to choose any vertex.

6.4.2.5 Kruskal’s Algorithm

Kruskal’s Algorithm uses the Greedy approach as it goes on choosing the lightest edges and then choose the next lightest edge and so on.

All the edges are sorted in ascending order while choosing the next edge. Care is to be taken that it should not give rise to a cycle.

Let G(V, E) is a connected weighted undirected graph with no loops and parallel edges.

1. T = null; T is a solution vector.
2. V_s = Set of Vertices
3. Construct a priority queue containing all edges in E in ascending order.
4. For each V ∈ V_s add {V} to V_s.
5. while (|V_s| > 1) // if V_s set contains only one element then terminate the loop.

                      {
                      choose <V, W> an edge ∈ Q (Priority Queue) with least
                      weight.
                      delete <V, W> from Q
                      if (<V, W> are in different sets W1 and W2 in Vs)
                      {
      
                      replace W1 and W2 in Vs by W1 U W2
                      add <V, W> to T
                      }
   
                      if (<V, W> are in the same set)
                      {
                      it suggests a cycle
                      discard <V, W>
                      }
                 } // While loop complete
   

Example: Find out the minimum cost of a spanning tree by using Kruskal’s algorithm (Figure 6.35).

FIGURE 6.35 Given undirected weighted graph G.

Solution:

Step 1:

T = null

V_s = null

E = {<V_1, V₂>, <V₂, V₃>….} //set of all edges

T is a solution vector, initially null with no edges.

V_s is the set of vertices and at the initial step it is null.

Step 2: Arrange all the edges in ascending order according to their weights.

When you select any edge then add it to the set of vertices V_s and the Tree, T is solution vector.

Care must be taken that there should not be any cycle.

Priority Queue:

V₁ – V₇ → 1 ✓

V₃ – V₄ → 3 ✓

V₂ – V₇ → 4 ✓

V₃ – V₇ → 9 ✓

V₂ – V₃ → 15 // creates loop so discard

V₄ – V₇ → 16 // creates loop so discard

V₄ – V₅ → 17 ✓

V₁ – V₂ → 20 // creates loop so discard

V₁ – V₆ → 23 ✓

V₅ – V₇ → 25

V₆ – V₇ → 36

V₅ – V₆ → 38

V_s = {{V₁}, {V₂}, {V₃}, {V₄}, {V₅}, {V₆}, {V₇}}

This is the set of vertices at the initial stage.

Step 3: We select edge V₁ – V₇ because it has minimum weight. Add it to V_s and T.

V_s = {{V₁, V₇}, {V₂}, {V₃}, {V₄}, {V₅}, {V₆}}

T = {<V₁, V₇>}

Step 4: Next select V₃ – V₄ with weight 3.

V_s = {{V₁, V₇}, {V₂}, {V₃, V₄}, {V₅}, {V₆}}

T = {<V_1, V₇>, <V₃, V₄>}

Step 5: Next edge is V₂ – V₇ with weight 4.

V_s = {{V₁, V₇, V₂}, {V₃, V₄}, {V₅}, {V₆}}

T = {<V₁, V₇>, <V₃, V₄>, <V₂, V₇>}

Step 6: Next edge is V₃ – V₇ with weight 9.

V_s = {{V₁, V₇, V₂, V₃, V₄}, {V₅}, {V₆}}

T = {<V_1, V₇>, <V₃, V₄>, <V₂, V₇>, <V₃, V₇>}

Step 7:

The next edge is V₂ – V₃ with weight 15. We discard this edge because it results in cycle. After all, V₂ and V₃ are in the same set in V_s.

Therefore, the next edge is V₄ – V₇ with weight 16, we discard this edge also because it results in cycle. V4 and V₇ are in the same set in V_s.

Therefore, the next edge is V₄ – V₅ with weight 17. Select it.

V_s = {{V₁, V₇, V₂, V₃, V₄, V₅}, {V₆}}

T = {<V_1, V₇>, <V₃, V₄>, <V₂, V₇>, <V₃, V₇>, <V₄, V₅>}

Step 8:

The next edge is V₁ – V₂ with weight 20. We discard this edge because it results in cycle. V₁ and V₂ are in the same set in V_s.

The next edge is V₁ – V₆ with weight 23. Select it.

V_s = {{V₁, V₇, V₂, V₃, V₄, V₅, V₆}}

T = {<V_1, V₇>, <V₃, V₄>, <V₂, V₇>, <V₃, V₇>, <V₄, V₅>, <V₁, V₆>}

Step 9: So all vertices of the given graph are visited. Stop this process. We get tree which is minimum cost-spanning tree as follows (Figure 6.36):

FIGURE 6.36 Minimum cost-spanning tree for graph G.

Minimum cost of spanning tree= 23 + 1 + 4 + 9 + 3 + 17 = 57

Note: The above tree satisfies all the conditions to become a spanning tree and mainly it uses greedy strategy because we choose or select the edge with minimum weight as the first edge instead of choosing any random edge like in Prime’s Algorithm.

Example: Find minimum cost-spanning tree by using Kruskal’s algorithm (Figure 6.37).

FIGURE 6.37 Given undirected weighted graph G.

Solution:

Step 1:

T = null

V_s = null

E = {<V_1, V₂>, <V₂, V₃>….} //set of all edges

T is a solution vector, initially null with no edges.

V_s is the set of vertices and at the initial step it is null.

Step 2: Arrange all the edges in ascending order according to their weights.

When you select any edge, then add it to the set of vertices V_s and the Tree, T is the solution vector.

Care must be taken that there should not be any cycle.

Priority Queue:

A – F → 2 ✓

B – F → 3 ✓

A – B → 4 // creates loop so discard

C – E → 5 ✓

B – C → 6 ✓

B – E → 7 // creates loop so discard

D – E → 7 ✓

C – D → 8

E – F → 9

V_s = {{A}, {B}, {C}, {D}, {E}, {F}}

This is the set of vertices at the initial stage.

Step 3: We select edge A – F because it has minimum weight. Add it to V_s and T.

T = {<A, F>}

V_S = {{A, F}, {B}, {C}, {D}, {E}}

Step 4: We select edge B – F because it has minimum weight. Add it to V_s and T.

T = {<A, F>, <B, F>}

V_S = {{A, F, B}, {C}, {D}, {E}}

Step 5:

The next edge is A – B with weight 4. We discard this edge because it results in cycle. A and B are in the same set in V_s.

Step 6:

Therefore, the next edge is C – E with weight 5. Select it.

T = {<A, F>, <B, F>, <C, E>}

V_S = {{A, F, B}, {D}, {C, E}}

Step 7:

Therefore, the next edge is B – C with weight 6, select it.

T = {<A, F>, <B, F>, <C, E>, <B, C>}

V_S = {{A, F, B, C, E}, {D}}

Step 8:

The next edge is B – E with weight 7. We discard this edge because it results in cycle. In addition, B and E are in the same set in V_s.

Step 9:

Therefore, next edge is D – E with weight 7, select it.

T = {<A, F>, <B, F>, <C, E>, <B, C>, <D, E>}

V_S = {{A, F, B, C, E, D}}

Step 10: So all vertices of a given graph are visited. Stop this process. We get tree that is minimum cost-spanning tree as follows (Figure 6.38):

FIGURE 6.38 Minimum cost-spanning tree for graph G in Figure 6.36.

Minimum cost = 2+3+5+6+7 = 23

Time complexity of Kruskal’s Algorithm:

1. Adding all vertices to V_s would require the time complexity O (n).
2. In the while loop, we are supposed to take a union of two sets, which can be done in O (n).
3. Whenever an edge is chosen and deleted the queue, it shows the corresponding status. These operations require the complexity O (1).
4. 4. In the while loop, the loop repeats itself for the entire edge list. Hence, the complexity would be O (|E|).
5. Complexity of the algorithm would hence be O (|E|log2|E|).

6.5 Interview Questions

1. What is a graph?
2. What are the components that a graph consists of?
3. What is the difference between a connected graph and a non-connected graph?
4. What is the difference between a directed graph and a non-directed graph?
5. What are weighted graphs?
6. How do you represent components of a graph in a computer program?
7. What are the applications of graph data structure?
8. How does depth first traversal work?
9. How does breadth first traversal work?
10. What are the different applications of DFS and BFS?
11. Describe in brief, the terms related to the graph: in-degree, out-degree, nodes and edges.
12. Write an algorithm for BFS on graph.
13. Explain the time complexity of the BFS algorithm.
14. Write a note on the advantages and disadvantages of the BFS algorithm.
15. Explain the in-degree and out-degree of a node with examples.
16. Define the following terms with respect to the graph:
    1. In-degree of a node
    2. Directed graph
    3. Weighted graph
    4. Predecessor
17. Explain the shortest path algorithm for graph with a suitable example.
18. Write a note on MST?
19. Explain in detail the DFS traversal of a graph.
20. Describe non-recursive DFS algorithm in brief.
21. What are the different applications of DFS?

6.6 Multiple Choice Questions

1. Let us consider an unweighted graph G. Let a breadth-first traverse of G be done from a node r. Let d (r, u) and d (r, v) be the lengths of the shortest paths from r to u and v respectively, in G. of u is visited before v during the breadth-first traversal, which of the following statements is correct?
   1. d(r, u) < d (r, v)
   2. d(r, u) > d(r, v)
   3. d(r, u) <= d (r, v)
   4. None of the above

   Answer: (C)

2. How many undirected graphs which are not necessarily connected can be formed out of a provided set V= {V 1, V 2,…V n} of n vertices?
   1. n(n-l)/2
   2. 2^n
   3. n!
   4. 2^(n(n-1)/2)

   Answer: (D)

3. Which of the following statements is/are TRUE for an undirected graph?
   1. P: Number of odd degree vertices is even
   2. Q: The sum of degrees of all vertices is even
      1. P Only
      2. Q Only
      3. Both P and Q
      4. Neither P nor Q

      Answer: (C)

4. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
   1. A 1/8
   2. 1
   3. 7
   4. 8

   Answer: (C)

5. Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is
   1. E
   2. 2E
   3. V
   4. 2V

   Answer: (B)

6. How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v₁, v₂, ... v_n} of n vertices?
   1. n(n-1)/
   2. 2ⁿ
   3. n!
   4. 2^n(n-1)/2

   Answer: (D)

7. Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
   1. There exists a cutset in G having all edges of maximum weight.
   2. There exists a cycle in G having all edges of maximum weight
   3. Edge e cannot be contained in a cycle.
   4. All edges in G have the same weight

   Answer: (A)

8. What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
   1. 1
   2. 2
   3. 3
   4. n

   Answer: (C)

9. Consider a directed graph with n vertices and m edges such that all edges have the same edge weights. Find the complexity of the best-known algorithm to compute the MST of the graph?
   1. O(m+n)
   2. O(m logn)
   3. O(mn)
   4. O(n logm)

   Answer: (A)

10. For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim’s algorithm to construct an MST?
    1. (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
    2. (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
    3. (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
    4. (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

    Answer: (C)

11. What is the number of edges present in a complete graph having n vertices?
    1. (n*(n+1))/2
    2. (n*(n-1))/2
    3. n
    4. Information given is insufficient

    Answer: B

12. In the given graph, identify the cut vertices.
    1. B and E
    2. C and D
    3. A and E
    4. C and B

    Answer: D

13. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
    1. True
    2. False

    Answer: B

14. What is the maximum number of edges in a bipartite graph having 10 vertices?
    1. 24
    2. 21
    3. 25
    4. 16

    Answer: C

15. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G’(Complement of G) is ___________
    1. (n*n-n-2*m)/2
    2. (n*n+n+2*m)/2
    3. (n*n-n-2*m)/2
    4. (n*n-n+2*m)/2

    Answer: A

16. A graph with all vertices having an equal degree is known as a __________
    1. Multigraph
    2. Regular graph
    3. Simple graph
    4. Complete graph

    Answer: B

17. Which of the following ways can be used to represent a graph?
    1. Adjacency list and adjacency matrix
    2. Incidence matrix

       C. Adjacency list, adjacency matrix as well as incidence matrix

    3. No way to represent

    Answer: C

18. Which of the following is true?
    1. A graph may contain no edges and many vertices
    2. A graph may contain many edges and no vertices
    3. A graph may contain no edges and no vertices
    4. A graph may contain no vertices and many edges

    Answer: B

    
19. The given Graph is regular.
    1. True
    2. False

    Answer: A

20. A connected planar graph having 6 vertices, 7 edges contain _____________ regions.
    1. 15
    2. 3
    3. 1
    4. 11

    Answer: B

21. Which of the following statements is false or true?
    1. If an undirected simple graph of ‘n’ vertices consists of n (n-1)/2 number of edges then it is called a complete graph.
    2. A simple digraph is said to be unilaterally connected if for any pair of nodes of a graph at least one of the nodes of a pair is reachable from the other node.
       1. Statement 1 is false
       2. Statement 2 is false
       3. Statements 1 and 2 are false
       4. Statements 1 and 2 are true

       Answer: D