Data Structures using ‘C’ - Graphs

Data Structures using ‘C’ Unit 7

Unit 7 Graphs
Structure:
7.0 Introduction
7.1 Overview of Graphs
Self Assessment Questions
7.2 Adjacency lists & Adjacency Matrix
7.2.1 Adjacency lists
7.2.2 Adjacency Matrix
Self Assessment Questions
7.3 Depth – First Traversal
Self Assessment Questions
7.4 Breadth – First Traversal
7.5 Spanning Trees
Self Assessment Questions 7.6 Summary 7.7 Terminal Questions 7.0 Introduction In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics. A graph G is defined as follows: G=(V,E), where V is a finite, non-empty set of vertices (singular: vertex) and E is a set of edges (links between pairs of vertices). When the edges in a graph have no direction, the graph is called undirected, otherwise called directed. In practice, some information is associated with each node and edge.
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 207
Graph data structures are non-hierarchical and therefore suitable for data sets where the individual elements are interconnected in complex ways. For example, a computer network can be simulated with a graph. Hierarchical data sets can be represented by a binary or nonbinary tree. Objectives At the end of this unit, you will be able to understand the:
 Overview of Graphs
 Brief introduction of Adjacency lists & Adjacency Matrix
 Depth – First Traversal
 Breadth – First Traversal
 Spanning Trees and two algorithms for finding the minimum spanning tree .
7.1 Overview of Graphs A graph is a collection of nodes, called vertices, and line segments, called arcs or edges, that connect pairs of nodes. A path is a sequence of vertices in which each vertex is adjacent to the next one. In Figure 7-1, {A, B, C, E} is one path and {A, B, E, F} is another. Note that both directed and undirected graphs have paths. In an undirected graph, you may travel in either direction.
A cycle is a path consisting of at least three vertices that starts and ends with the same vertex. In Figure 7.1(b), B, C, D, E, B is a cycle. Note, however, that the same vertices in Figure 7-1(a) do not constitute a cycle
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 208
because in a digraph, a path can only follow the direction of the arc,
whereas in an undirected graph, a path can move in either direction along
the edge. A loop is a special case of a cycle in which a single arc begins
and ends with the same vertex. In a loop, the end points of the line are the
same.
Two vertices are said to be connected if there is a path between them. A
graph is said to be connected if, suppressing direction, there is a path from
any vertex to any other vertex. Furthermore, a directed graph is strongly
connected if there is a path from each vertex to every other vertex in the
digraph. A directed graph is weakly connected if at least two vertices are
not connected. (A connected undirected graph would always be strongly
connected, so the concept is not normally used with undirected graphs.) A
graph is disjoint if it is not connected. Figure 7-2 contains a weakly
connected graph (a), a strongly connected graph (b), and a disjoint
graph (c).
(a) Directed graph (b) Undirected graph
Fig. 7.1: Directed and undirected graphs
The degree of a vertex is the number of lines incident to it. In Figure 7-2(a),
the degree of vertex B is 3 and the degree of vertex E is 4. The outdegree
of a vertex in a digraph is the number of arcs leaving the vertex; the
indegree is the number of arcs entering the vertex. Again in Figure 7-2(a)
the indegree of vertex B is 1 and its outdegree is 2; in Figure 7-2(b) the
indegree of vertex E is 3 and its outdegree is 1.
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 209
Fig. 7.2: Connected and disjoint graphs
Self Assessment Questions
1. Define a graph with neat diagram.
2. Explain directed and Undirected graph with neat diagram.
7.2 Adjacency lists & Adjacency Matrix
Two main data structures for the representation of graphs are used in
practice. The first is called an adjacency list, and is implemented by
representing each node as a data structure that contains a list of all adjacent
nodes. The second is an adjacency matrix, in which the rows and columns
of a two-dimensional array represent source and destination vertices and
entries in the graph indicate whether an edge exists between the vertices.
Adjacency lists are preferred for sparse graphs; otherwise, an adjacency
matrix is a good choice. Finally, for very large graphs with some regularity in
the placement of edges, a symbolic graph is a possible choice of
representation.
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 210
7.2.1 Adjacency lists In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node and the other denoting the destination node of the corresponding arc. Typically, adjacency lists are unordered. In computer science, an adjacency list is a closely related data structure for representing graphs. In an adjacency list representation, we keep, for each vertex in the graph, all other vertices which it has an edge to (that vertex's "adjacency list"). For instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an instance of this type of representation, as can the representation in Cormen et al in which an array indexed by vertex numbers points to a singly-linked list of the neighbors of each vertex.
The graph pictured above has this adjacency list representation:
a
Adjacent to
b,c
b
Adjacent to
a,c
c
Adjacent to
a,b
a
b
c
b
a
c
c
a
b
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 211
The adjacency list uses a two-dimensional ragged array to store the edges.
An adjacency list is shown in Figure 7.4.
Fig. 7.4: Adjacency list
The vertex list is a singly linked list of the vertices in the list. Depending on
the application, it could also be implemented using doubly linked lists or
circularly linked lists. The pointer at the left of the list links the vertex entries.
The pointer at the right in the vertex is a head pointer to a linked list of
edges from the vertex. Thus, in the nondirected graph on the left in Figure
6.4, there is a path from vertex B to vertices A, C, and E. To find these
edges in the adjacency list, we start at B's vertex list vertex and traverse the
linked list to A, then to C, and finally to E.
7.2.2 Adjacency Matrix
The adjacency matrix uses a vector (one-dimensional array) for the
vertices and a matrix (two-dimensional array) to store the edges (see Figure
7-3). If two vertices are adjacent – that is, if there is an edge between them
– the matrix intersect has a value of 1; if there is no edge between them, the
intersect is set to 0. If the graph is directed, then the intersection in the
adjacency matrix indicates the direction.
A
B
C
D
E
F
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 212
Fig. 7.3: Adjacency matrix
In addition to the limitation that the size of the graph must be known before
the program starts, there is another serious limitation in the adjacency
matrix: Only one edge can be stored between any two vertices. Although
this limitation does not prevent many graphs from using the matrix format,
some network structures require multiple lines between vertices.
Self Assessment Questions
1. Explain the Adjacency lists with suitable example.
2. Explain the Adjacency matrix for directed graph.
7.3 Depth – First Traversal
In the depth-first traversal, we process all of a vertex's descendents before
we move to an adjacent vertex. This concept is most easily seen when the
graph is a tree. In Figure 7.5, we show the preorder traversal, one of the
standard depth-first traversals.
In a similar manner, the depth-first traversal of a graph starts by processing
0 1 0 0 0 0
1 0 1 0 1 0
0 1 0 1 1 0
0 0 1 0 1 0
0 1 1 1 0 1
0 0 0 0 1 0
A
B
C
D
E
F
A B C D E F
(a) Adjacency matrix for non-directed graph
(a) Adjacency matrix for directed graph
0 1 0 0 0 0
0 0 1 0 1 0
0 0 0 1 1 0
0 0 0 0 0 0
0 0 0 1 0 1
0 0 0 0 0 0
A
B
C
D
E
F
A B C D E F
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 213
the first vertex of the graph. After processing the first vertex, we select any
vertex adjacent to the first vertex and process it. As we process each vertex,
we select an adjacent vertex until we reach a vertex with no adjacent entries.
This is similar to reaching a leaf in a tree. We then back out of the structure,
processing adjacent vertices as we go. It should be obvious that this logic
requires a stack (or recursion) to complete the traversal.
The order in which the adjacent vertices are processed depends on how the
graph is physically stored.
Fig. 7.5: Depth first traversal of a tree
Let's trace a depth-first traversal through the graph in Figure 7.7 The
number in the box next to a vertex indicates the processing order. The
stacks below the graph show the stack contents as we way down the graph
and then as we back out.
Fig. 7.6: Depth first traversal of a graph
6
8
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 214
1. We begin by pushing the first vertex, A, into the stack. 2. We then loop, pop the stack, and, after processing the vertex push all of the adjacent vertices into the stack. To process X at Step 2, therefore, we pop X from the stack, process it, and then push G and H into the stack, giving the stack contents as shown in Figure 6-6(b)-H G. 3. When the stack is empty, the traversal is complete. Self Assessment Questions
1. Explain the depth first traversal of a graph with suitable example.
7.4 Breadth – First Traversal
In the breadth-first traversal of a graph, we process all adjacent vertices of a vertex before going to the next level. Looking at the tree in, Figure 7.7, we see that its breadth-first traversal starts at level 1 and then processes all the vertices in level 2 before going on to process the vertices in level 3.
Fig. 7.7: Breadth-first traversal of a tree
The breadth-first traversal of a graph follows the same concept we begin by picking a starting vertex; after processing it, we process all of its adjacent vertices. After we process all of the first vertex adjacent vertices, we pick the first adjacent vertex and process all of its vertices, then the second adjacent vertex and process all of its vertices and so forth until we are finished.
The breadth-first traversal uses a queue rather than a stack, As we process each vertex, we place all of its adjacent vertices in the queue. Then, to
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 215
select the next vertex to be processed, we delete a vertex from the queue and process it. Let's trace this logic through the graph in Figure 7.8.
Fig. 7.8: Breadth-first traversal of a graph
1. We begin by enqueuing vertex A in the queue. 2. We then loop, dequeuing the queue and processing the vertex from the front of the queue. After processing the vertex, we place all of its adjacent vertices into the queue. Thus, at Step 2 in Figure 7.8(b]), we dequeue vertex X, process it, and then place vertices G and H in the queue. We are then ready for Step 3, in which we process vertex G. 3. When the queue is empty, the traversal is complete.
7.5 Spanning Trees
A spanning tree of a graph is an undirected tree consisting of only those edges necessary to connect all the nodes in the original graph. For any pair of nodes there exists only one path between them and the insertion of any edge to a spanning tree forms a unique cycle. Those edges left out of the Spanning tree that were present in the original graph connect paths together in the tree.
If a DFS is used, those edges traversed by the algorithm form the edges of the tree, referred to as depth first spanning tree. If a BFS is used, the
1
2
3
4
5
6
7
8
9
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 216
spanning tree is formed from those edges traversed during the search, producing a breadth first spanning tree. Examples:
A
B C D E
F Fig. 7.9a the graph
A
B C D E
F Fig. 7.9b DFS spanning tree Fig. 7.9c BFS spanning tree Network: A network is a graph that has weights or costs associated with its edges. It is also called weighted graph.
Eg.:
Fig. 7.10
A
E
B C D
F
6 1 5
1
5 5
2
4
3
3
2
6
4
5
6
6
Costs/weights
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 217
Minimum spanning tree: This is a spanning tree that covers all vertices of a network such that the sum of the costs of its edges is minimum. There are two algorithms for finding the minimum spanning tree, given a network. 1) Kruskal’s algorithm 2) Prim’s algorithm 1. Kruskal’s algorithm to find min. spanning tree. Step 1: Arrange all edges in ascending order of their cost to form an input set. Step 2: From this input set, take each edge and if it does not form a cycle, include it in the output set, which forms the minimum spanning tree. The sum of the costs of the edges in the output set is the least. Note: If a vertex u is reachable from vertex w and w is reachable from u, then the path between u and w is called a cycle. Eg. in fig. 7.10 above, the set [(1, 2) (2, 3), (3, 4), (4, 1)] is a cycle and the superset [(1, 2) (2, 5) (5, 6) (6, 4) (4, 1)] also is a cycle. Eg. Applying Kruskal’s algorithm to the network of fig. 7.10, we get Step 1: Input set = { (1, 3), (4, 6), (2, 5), (3, 6), (2, 3), (3, 4), (1, 4), (1, 2), (3, 5), (5, 6)} Step 2: Output set = { (1, 3) (4, 6) (2, 5), (3, 6), (2, 3)} Minimum cost = 1+2+3+4+5 = 15.
Thus, minimum spanning tree is an shown:
Fig. 7.11
1
2
4
3
5
6
3
1
5
4
2
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 218
2. Prim’s algorithm to find minimum spanning tree: Step 1: Let S be the set of vertices in the spanning tree and A be the set of all vertices in the network. Let E be the set of all edges forming the spanning tree. Initially let E = { } and S = {V1} where V1 is the starting vertex in A. Step 2: While (S not equal to A) do {
 find (a, b) to be a low-cost edge such that a is in S and b is in (A – S).
 E = E Union {(a, b)}
 S = S Union { b }
} Eg. For the network in fig. (6.10), we get outputs after applying steps of Prim’s algorithm, as follows: Step 1: E = { }, S = { 1 } A = { 1, 2, 3, 4, 5, 6 } Step 2 Pass 1[of while loop]  E = { (1, 3)}, S = { 1, 3 } Pass 2  E = { (1, 3), (3, 6) }, S = { 1, 3, 6} Pass 3  E = { (1, 3), (3, 6), (6, 4)}, S = {1, 3, 6, 4} Pass 4  E = { (1, 3), (3, 6), (6, 4), (3, 2)}, S = {1, 2, 3, 4, 6} Pass 5  E = { (1, 3), (3, 6) (6, 4) (3, 2) (2, 5)} S = { 1, 2, 3, 4, 5, 6} Now since S = A, while loop terminates and E has the set of edges forming the minimum spanning tree (same as in fig. 7.11) and whose cost is 15. Note: Given a network (= weighted graph), many spanning trees can be formed but only one minimum spanning tree can be obtained [especially when the weights of the network are unique].
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 219
Exercise: Derive the minimum spanning tree for the graph below using both the Prim’s and Kruskal’s methods – Fig. 7.12 Answer: E = { (a, b), (b, c), (b, d), (b, f), (d, e)} Cost = 56 Optimal path algorithems: If we have a graph representing the highway system of India, where the vertices represent cities and the edges indicate highways, a motorist who wants to travel from Mumbai to Delhi would like to know:
1) Is there a path from Mumbai to Delhi ?
2) If there is more than 1 path from Mumbai to Delhi, which path is the shortest ?
1) Dijkstra’s algorithm to find shortest path from a given starting point (= source vertex) in the graph to any destination point. Step 1: Let S be the start/source node and T be the last node to be given a permanent label. Assign a temporary label l(i) =  to all nodes except for S, whose label is given 0 and is made permanent by setting P to S. Step 2: For each node i with a temporary label, redefine l(i) to be the smaller of l(i) and l(p) +d(p, i) where d(p, i) = cost of edge (p, i). Find the node i with the smallest temporary label; set p = i and make the label l(p) permanent. Step 3: If node T has a temporary label, then repeat step 2 else T has a permanent label and this corresponds to the length of the shortest path from S to T.
a
b
c
e
f
d
16
21
11
5
14
6
19
33
10
18
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 220
Eg: Find the shortest paths from S to all nodes in the fig. 7.13.
Fig. 7.13 From the given graph above, form the adjacency matrix:
S 1 2 3 4 5 S 0  13  16 8 1  0  6  10 2 13  0 14  17 3  6 14 0 5 17 4 16   5 0 7 5 8 10 17 17 7 0 Note: If there is no direct path from vertex A to B, then adjacency matrix [A, B] set to .
S
1
13
8
5
7
10
6
17
4
2
17
14
3
5
Source
16
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 221
Applying the steps of the Dijkstra’s algorithm, we get the outputs as shown:
S
1
2
3
4
5
Vertices in the shortest path
Step 1 
Label ( ) Permanent ?
0 





S
Pass 1 of step 2 
Label ( ) Permanent ?
0 

13

16
8 
5
Pass 2 of step 2 
Label ( ) Permanent ?
0 
18
13 
25
15
8 
2
Pass 3 step 2 
Label ( ) Permanent ?
0 
18
13 
25
15 
8 
4
Pass 4 of step 2 
Label ( ) Permanent ?
0 
18 
13 
20
15 
8 
1
step 3 
Label ( ) Permanent ?
0 
18 
13 
20 
15 
8 
3
Thus, to go from S to 4, shortest path is of cost 15 and goes through vertices 5 & 2. To move to 3 from S, the shortest path goes through nodes 5, 2, 4, and 1 and is of cost 20. In pass 2 of step 2, the distance from S to node 1 has changed from  to 18 because the least of the values (l(i), d(p, i) + l(p)) has to be chosen, according to step 2 of algorithm. Here l(i) is label assigned to node 1 (= ), l(p) is label assigned to permanent node 5( = 8) and d(p, i) is cost of edge from p to i, i.e., cost of edge from node 5 to 1 (= 10, as understood from adjacency matrix, 5th row and 1st column intersection).  min (, 10 + 8) = 18 assigned to node 1. In pass 3 of step 2,
l(i) = l(3) = 25
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 222
l(p) = l(4) = 15
d(p, i) = d(4, 3) = 5
 min (25, 15+5) = 20 assigned to node 3.
2) Floyd-Warshall’s all pairs shortest path algorithm. Given the initial cost
adjacency matrix as A (i, j), calculate the matrix Ak (i, j) to be the cost of
the shortest path from i to j going through no intermediate vertex of
index greater than k thus –
Ak (i, j) = min (Ak–1 (i, j) , Ak–1(i, k) + Ak–1(k, j)) where k  1.
Initial cost adjacency matrix is
A V1 V2 V3
V1 0 4 11
V2 6 0 2
V3 3  0
Fig. 7.14
A1 V1 V2 V3 ( A1 (3, 2)
V1 0 4 11 = min (A (3, 2), A (3, 1) + A (1, 2)
V2 6 0 2 = min (, 3 + 4)
V3 3 7 0 = min (, 7)
= 7)
A2 V1 V2 V3 ( A2 (1, 3)
V1 0 4 6 = min (A1 (1, 3), A1 (1, 2) + A1 (2, 3))
V2 6 0 2 = min (7, 4 + 2)
V3 3 7 0 = min (7, 6)
= 6)
V1 V2
V3
3
2
11
4
6
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 223
A3 V1 V2 V3 ( A3 (2, 1)
V1 0 4 6 = min (A2 (2, 1), A2 (2, 3) + A2 (3, 1)
V2 5 0 2 = min (6, 2 + 3)
V3 3 7 0 = min (6, 5)
= 5)
Thus, the shortest distances between all pairs of vertices in the graph can
be obtained by looking up the final values in the A3 matrix.
Tip: Copy the kth row and column as it is in the Ak matrix from the Ak–1 matrix
and derive the other values using the given formula in the algorithm.
Exercise: Apply the Dikjsha’s algorithm and Floyd-Warshall’s all pairs
algorithm to get the shortest path(s) [Source vertex is 1] in the graph below:
V1 V2 V3 V4
V1 0 12 10 16
V2 6 0 5 4
V3 8 2 0 6
V4 9 3 1 0
Fig. 7.15 Answer
Self Assessment Questions
1. Define Spanning Trees with neat diagram.
2. Explain the Prim’s algorithm to find minimum spanning tree with suitable
example.
7.6 Summary
A graph is a collection of nodes, called vertices, and line segments, called
arcs or edges, that connect pairs of nodes. Graph data structures are non-
10
1
3
6
1
2
4
18
2
4
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 224
hierarchical and therefore suitable for data sets where the individual elements are interconnected in complex ways. For example, a computer network can be simulated with a graph. In this context we discussed in this book the Overview of Graphs, Adjacency lists & Adjacency Matrix , Depth – First Traversal, Breadth – First Traversal, Spanning Trees. 7.7 Terminal Questions
1) A binary tree has 10 nodes. The preorder and inorder traversal of the tree are shown below. Draw the tree.
Preorder : J C B A D E F I G H Inorder : A B C E D F J G I H Hints: 1) The first node in the preorder sequence is the root.
2) Traverse Left to right in the preorder sequence, finding each node’s position (left or right) with respect to the previously-located node, in the Inorder Sequence.
Answer:
2) Give the in-order, postorder and breadth first traversal for the following tree:
B C D E F G H
J
I
C
B
D
G
H
E
F
A
A
Data Structures using ‘C’ Unit 7
Sikkim Manipal University Page No. 225
Answer: Inorder = D B H E A F C G Postorder = D H E B F G C A B First = A B C D E F G H
3) Show the BST and B tree after the insertion of the following elements according to their respective insertion algorithms – 43, 64, 80, 96, 128, 150 and 250.
Note: BST means Binary Search Tree; the B tree should be of order 4.
4) Given the BST below:
23 12 44 8 14 26 52 13
a) Write the algorithm to find the smallest value in the tree.
b) Draw the tree obtained after separately deleting from the original tree i) node 13 ii) node 14 iii) node 23
5) Construct the binary tree if the result of traversing it is as below:
Postorder : I E J F C G K L H D B A Inorder : E I C F J B G D K H L A Hints: 1) The last node in the postorder sequence is the root. 2) Traverse right to left in the postorder sequence, finding each node’s position (left or right) with respect to the previously-located node in the Inorder Sequence.
6) Suppose that keys 1, 2, 3, …, 19, 20 are inserted in that order into a B tree with m = 4. Show the B tree after each insertion. How many internal nodes does the final B tree have ?