![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
5 |
GRAPH A graph G = (V, E) consists of a set of vertices, V and set of edges E. Vertics are referred to as nodes and the arc between the nodes are referred to as Edges.
Each edge is a pair (v, w) where u, w
Fig. 5.1.1 Here V1, V2, V3, V4 are the vertices and (V1, V2), (V2, V3), (V3, V4), (V4, V1), (V2, V4), (V1, V3) are edges. 5.1 BASIC TERMINOLOGIES Directed Graph (or) Digraph Directed graph is a graph which consists of directed edges, where each edge in E is unidirectional. It is also referred as Digraph. If (v, w) is a directed edge then (v, w) # (w, v)
(V1, V2)
Fig. 5.1.2 Undirected Graph An undirected graph is a graph, which consists of undirected edges. If (v, w) is an undirected edge then (v,w) = (w, v)
(V1, V2) = (V2, V1)
Fig. 5.1.3 Weighted Graph A graph is said to be weighted graph if every edge in the graph is assigned a weight or value. It
can be directed or undirected graph.
| ||||
| |||||
Data Structures 5.1 | |||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
1 |
1 | |||||||||
1 2 | ||||||||||
2 |
1 | |||||||||
| ||||||||||
Fig. 5.1.4 (a) Fig. 5.1.4(b) Complete Graph A complete graph is a graph in which there is an edge between every pair of vertics. A complete graph with n vertices will have n (n - 1)/2 edges.
Fig. 5.1.5 Fig. 5.1.5 (a) Vertices of a graph In fig. 5.1.5 Number of vertics is 4 Number of edges is 6 (i.e) There is a path from every vertex to every other vertex. A complete digraph is a strongly connected graph. Strongly Connected Graph If there is a path from every vertex to every other vertex in a directed graph then it is said to be strongly connected graph. Otherwise, it is said to be weakly connected graph.
Fig. 5.1.6 Strongly Connected Graph Fig. 5.1.7 Weakly Connected Graph Path A path in a graph is a sequence of vertices 1
Data Structures 5.2 |
![]() |
![]() |
![]() |
Length The length of the path is the number of edges on the path, which is equal to N-1, where N represents the number of vertices. The length of the above path V1 to V3 is 2. (i.e) (V1, V2), (V2, V3). If there is a path from a vertex to itself, with no edges, then the path length is 0. Loop If the graph contains an edge (v, v) from a vertex to itself, then the path is referred to as a loop. Simple Path A simple path is a path such that all vertices on the path, except possibly the first and the last are distinct. A simple cycle is the simple path of length atleast one that begins and ends at the same vertex. Cycle A cycle in a graph is a path in which first and last vertex are the same.
Fig. 5.1.8 A graph which has cycles is referred to as cyclic graph. Degree The number of edges incident on a vertex determines its degree. The degree of the vertex V is written as degree (V). The indegree of the vertex V, is the number of edges entering into the vertex V. Similarly the out degree of the vertex V is the number of edges exiting from that vertex V.
Fig. 5.1.9 In fig. 5.1.9 Indegree (V1) = 2
| ||
| ||
Data Structures 5.3 | ||
![]() |
![]() |
![]() |
Outdegree (V1) = 1 ACyclic Graph A directed graph which has no cycles is referred to as acyclic graph. It is abbreviated as DAG. DAG - Directed Acyclic Graph.
Fig. 5.1.10 5.2 Representation of Graph Graph can be represented by Adjacency Matrix and Adjacency list. One simple way to represents a graph is Adjacency Matrix. The adjacency Matrix A for a graph G = (V, E) with n vertices is an n x n matrix, such that Aij = 1, if there is an edge
Vi to Vj
Adjacency Matrix For Directed Graph
Fig. 5.2.1 Fig. 5.2.2
Example V1,2 = 1 Since there is an edge V1 to V2 Similarly V1,3 = 1, there is an edge V1 to V3 V1,1 &
V1,4 = 0, there is no edge.
| ||
| ||
Data Structures 5.4 | ||
![]() |
![]() |
![]() |
Adjacency Matrix For Undirected Graph
Fig. 5.2.3 Fig. 5.2.4 Adjacency Matrix For Weighted Graph To solve some graph problems, Adjacency matrix can be constructed as Aij = Cij, if there exists an edge from Vi to Vj Aij = 0, if there is no edge & i = j If there is no arc from i to j, Assume C[i, j] =
Fig. 5.2.5 Fig. 5.2.6 Advantage * Simple to implement. Disadvantage * Takes O(n2) space to represents the graph * It takes O(n2) time to solve the most of the problems. Adjacency List Representation In this representation, we store a graph as a linked structure. We store all vertices in a list and then for each vertex, we have a linked list of its adjacency vertices
Fig. 5.2.7
Data Structures 5.5 | ||
![]() |
![]() |
![]() |
Adjacency List
Fig. 5.2.8 Disadvantage * It takes 0(n) time to determine whether there is an arc from vertex i to vertex j. Since there can be 0(n) vertices on the adjacency list for vertex i. 5.3 Topological Sort A topological sort is a linear ordering of vertices in a directed acyclic graph such that if there is a path from Vi to Vj, then Vj appears after Vi in the linear ordering. Topological ordering is not possible. If the graph has a cycle, since for two vertices v and w on the cycle, v precedes w and w precedes v. To implement the topological sort, perform the following steps. Step 1 : - Find the indegree for every vertex. Step 2 : - Place the vertices whose indegree is `0' on the empty queue. Step 3 : - Dequeue the vertex V and decrement the indegree's of all its adjacent vertices. Step 4 : - Enqueue the vertex on the queue, if its indegree falls to zero. Step 5 : - Repeat from step 3 until the queue becomes empty. Step 6 : - The topological ordering is the order in which the vertices dequeued. Routine to perform Topological Sort
/* Assume that the graph is read into an adjacency matrix and that the indegrees are computed for every vertices and placed in an array (i.e. Indegree [ ] ) */ | ||
| ||
Data Structures 5.6 | ||
![]() |
![]() |
![]() |
void Topsort (Graph G) { Queue Q ; int counter = 0; Vertex V, W ; Q = CreateQueue (NumVertex); Makeempty (Q); for each vertex V if (indegree [V] = = 0) Enqueue (V, Q); while (! IsEmpty (Q)) { V = Dequeue (Q); TopNum [V] = + + counter; for each W adjacent to V if (--Indegree [W] = = 0) Enqueue (W, Q); } if (counter ! = NumVertex) Error (" Graph has a cycle"); DisposeQueue (Q); /* Free the Memory */ }
Note : Enqueue (V, Q) implies to insert a vertex V into the queue Q. Dequeue (Q) implies to delete a vertex from the queue Q. TopNum [V] indicates an array to place the topological numbering. | ||
Data Structures 5.7 | ||
![]() |
![]() |
![]() |
Illustration
Fig. 5.3.1 Adjacency Matrix Step 1 Number of 1's present in each column of adjacency matrix represents the indegree of the corresponding vertex. In fig 5.3.1 Indegree [a] = 0 Indegree [b] = 1 Indegree [c] = 2 Indegree [d] = 2 Step 2 Enqueue the vertex, whose indegree is `0' In fig 5.3.1 vertex `a' is 0, so place it on the queue. Step 3 Dequeue the vertex `a' from the queue and decrement the indegree's of its adjacent vertex `b' & `c' Hence, Indegree [b] = 0 & Indegree [c] = 1 Now, Enqueue the vertex `b' as its indegree becomes zero. Step 4 Dequeue the vertex `b' from Q and decrement the indegree's of its adjacent vertex `c' and `d'. Hence, Indegree [c] = 0 & Indegree [d] = 1 Now, Enqueue the vertex `c' as its indegree falls to zero. Step 5 Dequeue the vertex `c' from Q and decrement the indegree's of its adjacent vertex `d'. Hence, Indegree [d] = 0 Now, Enqueue the vertex `d' as its indegree falls to zero. Step 6 Dequeue the vertex `d'.
| ||
| ||
Data Structures 5.8 | ||
![]() |
![]() |
![]() |
Step 7 As the queue becomes empty, topological ordering is performed, which is nothing but, the order in which the vertices are dequeued. VERTEX 1 2 3 4 a 0 0 0 0 b 1 0 0 0 c 2 1 0 0 d 2 2 1 0 ENQUEUE a b c d DEQUEUE a b c d RESULT OF APPLYING TOPOLOGICAL SORT TO THE GRAPH IN FIG. 5.3.1 Example
Adjacency Matrix :- V1 V2 V3 V4 V5 V6 V7 V1 0 1 1 1 0 0 0 V2 0 0 0 1 1 0 0 V3 0 0 0 0 0 1 0 V4 0 0 1 0 0 1 1 V5 0 0 0 1 0 0 1 V6 0 0 0 0 0 0 0 V7 0 0 0 0 0 1 0 INDEGREE 0 1 2 3 1 3 2 Indegree [V1] = 0 Indegree [V2] = 1 Indegree [V3] = 2 Indegree [V4] = 3 Indegree [V5] = 1 Indegree [V6] = 3 Indegree [V7] = 2 | ||
| ||
Data Structures 5.9 | ||
![]() |
![]() |
![]() |
| ||
INDEGREE BEFORE DEQUEUE # VERTEX 1 2 3 4 5 6 7 V1 0 0 0 0 0 0 0 V2 1 0 0 0 0 0 0 V3 2 1 1 1 0 0 0 V4 3 2 1 0 0 0 0 V5 1 1 0 0 0 0 0 V6 3 3 3 3 2 1 0 V7 2 2 2 1 0 0 0 ENQUEUE V1 V2 V5 V4 V3,V7 V6 DEQUEUE V1 V2 V5 V4 V3 V7 V6 RESULT OF APPLYING TOPOLOGICAL SORT TO THE GRAPH IN FIG. The topological order is V1, V2, V5, V4, V3, V7, V6 Analysis The running time of this algorithm is 5.4 Shortest Path Algorithm The Shortest path algorithm determines the minimum cost of the path from source to every other vertex. The cost of the path
V1, V2, --VN is Two types of shortest path problems, exist namely, 1. The single source shortest path problem 2. The all pairs shortest path problem The single source shortest path algorithm finds the minimum cost from single source vertex to all other vertices. Dijkstra's algorithm is used to solve this problem which follows the greedy technique. All pairs shortest path problem finds the shortest distance from each vertex to all other vertices. To solve this problem dynamic programming technique known as floyd's algorithm is used. These algorithms are applicable to both directed and undirected weighted graphs provided that they do not contain a cycle of negative length. | ||
| ||
Data Structures 5.10 | ||
![]() |
![]() |
![]() |
Single Source Shortest Path Given an input graph G = (V, E) and a distinguished vertex S, find the shortest path from S to every other vertex in G. This problem could be applied to both weighted and unweighted graph. 5.4.1 Unweighted Shortest Path In unweighted shortest path all the edges are assigned a weight of "1" for each vertex, The following three pieces of information is maintained. Algorithm for unweighted graph known Specifies whether the vertex is processed or not. It is set to `1' after it is processed, otherwise `0'. Initially all vertices are marked unknown. (i.e) `0'. dv Specifies the distance from the source `s', initially all vertices are unreachable except for s, whose path length is `0'. Pv Specifies the bookkeeping variable which will allow us to print. The actual path. (i.e) The vertex which makes the changes in dv. To implement the unweighted shortest path, perform the following steps : Step 1 : - Assign the source node as `s' and Enqueue `s'. Step 2 : - Dequeue the vertex `s' from queue and assign the value of that vertex to be known and then find its adjacency vertices. Step 3 :- If the distance of the adjacent vertices is equal to infinity then change the distance of that vertex as the distance of its source vertex increment by `1' and Enqueue the vertex. Step 4 :- Repeat from step 2, until the queue becomes empty. ROUTINE FOR UNWEIGHTED SHORTEST PATH void Unweighted (Table T) { Queue Q; Vertex V, W ; Q = CreateQueue (NumVertex); MakeEmpty (Q); /* Enqueue the start vertex s */ Enqueue (s, Q); while (! IsEmpty (Q)) { V = Dequeue (Q); | ||
| ||
Data Structures 5.11 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||||
|
V = Dequeue (Q); T[V]. Known = True; /* Not needed anymore*/ for each W adjacent to V if (T[W]. Dist = = INFINITY) { T[W] . Dist = T[V] . Dist + 1 ; T[W] . path = V; Enqueue (W, Q); } } DisposeQueue (Q) ; /* Free the memory */ } Illustrations Source vertex `a' is initially assigned a path length `0'.
V KNOWN dv Pv a 0 0 0 b 0 c 0 d 0 Queue a INITIAL CONFIGURATION After finding all vertices whose path length from `a' is 1. `a' is Dequeued V KNOWN dv Pv a 1 0 0 b 0 1 a c 0 1 a d 0 Queue b, c Fig. 5.4.1(a) 0 |
Fig. 5.4.1(b) | ||||||||||||||
0 |
1 | |||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
1 | ||||||||||||||||
Fig. 5.4.1(c) |
| |||||||||||||||
| ||||||||||||||||
Data Structures 5.12 | ||||||||||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||
1 |
0 |
| ||||||||||
| ||||||||||||
1 |
2 | |||||||||||
Fig. 5.4.1(d) |
| |||||||||||
After finding all vertices whose path length from `a' is 2.
`b' is dequeued V KNOWN dv Pv a 1 0 0 b 1 1 a c 0 1 a d 0 2 b Queue c,d `c' is Dequeued V KNOWN dv Pv a 1 0 0 b 1 1 a c 0 1 a d 0 2 b Queue d `d' is Dequeued V KNOWN dv Pv a 1 0 0 b 1 1 a c 1 1 a d 1 2 b Queue empty Shortest path from source a vertex `a' to other vertices are a a a 1 0 | ||||||||||||
| ||||||||||||
Data Structures 5.13 | ||||||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||||||||||
|
|
0 |
1 |
|
0 | ||||||||||||
1 |
1 |
2 |
0 | ||||||||||||||
2 | |||||||||||||||||
1 | |||||||||||||||||
|
Data Structures 5.14 | ||||||||||||||||
Illustrations 2
Figure 5.4.2 (a) An unweighed directed graph G V3 is taken as a source node and its path length is initialized to `0'
Fig. 5.4.2 (b) Graph after marking the start node as reachable in zero edges
Fig. 5.4. 2 (c) Graph after finding all vertices whose path length from source vertex is `1'
Fig. 5.4. 2 (d) Graph after finding all vertices whose path length from source vertex is `1'
0 1
1 1 2
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||||||
1 |
2 |
2 |
3 | ||||||||||
1 3 |
0 | ||||||||||||
Fig. 5.4. 2 (e) Final shortest path
V Known dv pv V1 0 V2 0 V3 0 0 0 V4 0 V5 0 V6 0 V7 0 Intial configuration of table used in Unweighted Shortest path computation Initial State V3 Dequeued V1 Dequeued V known dv Pv known dv Pv known dv Pv V1 0 V2 0 V3 0 0 0 1 0 0 1 0 0 V4 0 V5 0 V6 0 V7 0 Qi V3 V1, V6 V6, V2, V4 1 2 |
| ||||||||||||
Data Structures 5.15 |
![]() |
![]() |
![]() |
| ||
In general when the vertex `V' is dequeued and the distance of its adjacency vertex `w' is infinitive then distance and path of `w' is calculated as follows
T [W]. Dist = T[V]. Dist + 1 T[W]. path = V
When V3 is dequeued, known is set to 1 for that vertex the distance of its adjacent vertices V1 and V6 are updated if INFINITY. Path length of V1 is calculated as T [V1]. Dist = T [V3]. Dist + 1 = 0 + 1 = 1 and its actual path is also calculated as T [V1] . path = V3 lllly T [V6]. Dist = T[V3]. Dist + 1 = 1 T [V6]. Path = V3 Similarly, when the other vertices are dequeued, the table is updated as above.
V6 Dequeued V2 Dequeued V4 Dequeued V known dv Pv known dv Pv known dv Pv V1 1 1 V3 1 1 V3 1 1 V3 V2 0 2 V1 1 2 V1 1 2 V1 V3 1 0 0 1 0 0 1 0 0 V4 0 2 V1 0 2 V1 1 2 V1 V5 0 V6 1 1 V3 1 1 V3 1 1 V3 V7 0 Q : V2, V4 V4, V5 V5, V7
| ||
| ||
Data Structures 5.16 | ||
![]() |
![]() |
![]() |
| ||
V5 Dequeued V7 Dequeued V known dv Pv known dv Pv V1 1 1 V3 1 1 V3 V2 1 2 V1 1 2 V1 V3 1 0 0 1 0 0 V4 1 2 V1 1 2 V1 V5 1 3 V2 1 3 V2 V6 1 1 V3 1 1 V3 V7 0 3 V4 1 3 V4 Q : V7 empty Data changes during the unweighted shortest path algorithm. The shortest distance from the source vertex V3 to all other vertex is listed below : V3 V3 V3 V3 V3 V3 Note The running time of this algorithm is 5.4.2 Dijkstra's Algorithm The general method to solve the single source shortest path problem is known as Dijkstra's algorithm. This is applied to the weighted graph G. Dijkstra's algorithm is the prime example of Greedy technique, which generally solve a problem in stages by doing what appears to be the best thing at each stage. This algorithm proceeds in stages, just like the unweighted shortest path algorithm. At each stage, it selects a vertex v, which has the smallest dv among all the unknown vertices, and declares that as the shortest path from S to V and mark it to be known. We should set dw = dv + Cvw, if the new value for dw would be an improvement. | ||
| ||
Data Structures 5.17 | ||
![]() |
![]() |
![]() |
ROUTINE FOR ALGORITHM Void Dijkstra (Graph G, Table T) { int i ; vertex V, W; Read Graph (G, T) /* Read graph from adjacency list */ /* Table Initialization */ for (i = 0; i < Numvertex; i++) { T [i]. known = False; T [i]. Dist = Infinity; T [i]. path = NotA vertex; } T [start]. dist = 0; for ( ; ;) { V = Smallest unknown distance vertex; if (V = = Not A vertex) break ; T[V]. known = True; for each W adjacent to V if ( ! T[W]. known) { T [W]. Dist = Min [T[W]. Dist, T[V]. Dist + CVW] T[W]. path = V; } } } | ||
| ||
Data Structures 5.18 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||
| ||||||||
Example 1 :
Figure 5.4.3 The directed graph G. V known dv Pv a 0 0 0 b 0 c 0 d 0 Fig. 5.4.3 (a) Initial Configuration Vertex `a' is choose `n' as source and is declared as known vertex. Then the adjacent vertices of `a' is found and its distance are updated as follows : T [b] . Dist = Min [T[b]. Dist, T[a] . Dist + Ca,b] = Min [ = 2 T [d] . Dist = Min [T[d]. Dist, T[a] . Dist + Ca,d] = Min [ = 1
V known dv Pv a 1 0 0 b 0 2 a c 0 d 0 1 a After a is declared known Fig. 5.4.3(b) 2 * 2 0 1 Data Structures 5.19 | ||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||||||
* |
0 |
|
2 | ||||||||||
* |
1 |
2 | |||||||||||
Now, select the vertex with minimum distance, which is not known and mark that vertex as visited. Here `d' is the next minimum distance vertex. The adjacent vertext to `d' is `c', therefore, the distance of c is updated a follows, T[c]. Dist = Min [T[c]. Dist, T[d]. Dist + Cd, c] = Min [, 1 + 1] = 2 V known dv Pv a 1 0 0 b 0 2 a c 0 2 d d 1 1 a After d is declared known Fig. 5.4.3 (c) The next minimum vertex is b and mark it as visited. Since the adjacent vertex d is already visited, select the next minimum vertex `c' and mark it as visited. V known dv Pv a 1 0 0 b 1 2 a c 0 2 d d 1 1 a After b is declared known Fig. 5.4.3 (d)
V known dv Pv a 1 0 0 b 1 2 a c 1 2 d d 1 1 a After c is declared known and algorithm terminates Fig. 5.4.3 (e) * 0 * 1 * * 2 0 * 2 * * 2 0 * * 2 2 | |||||||||||||
| |||||||||||||
Data Structures 5.20 |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
Example : 2
Fig. 5.4.4 The directed Graph G
V known dv Pv V1 0 0 0
V2 0
V3 0
V4 0
V5 0 Fig. 5.44
(a) V6 0
V7 0 INITIAL CONFIGURATION V1 is taken as source vertex, and is marked known. Then the dv and Pv of its adjacent vertices are updated.
V known dv Pv V1 1 0 0 V2 0 2 V1
V3 0 V4 0 1 V1
V5 0 Fig.
5.4.4(b) V6 0
V7 0 After V1 is declared known 0 | ||||||||||
* 0 2 1 | ||||||||||
| ||||||||||
| ||||||||||
Data Structures 5.21 | ||||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
||||||||||||||
3 |
* |
0 |
2 |
|
V known dv Pv V1 1 0 0 V2 0 2 V1 V3 0 3 V4 V4 1 1 V1 V5 0 3 V4 Fig. 5.4.4(c) V6 0 9 V4 V7 0 5 V4 After V4 is declared known
V known dv Pv V1 1 0 0 V2 1 2 V1 V3 0 3 V4 V4 1 1 V1 V5 0 3 V4 Fig. 5.4.4 (d) V6 0 9 V4 V7 0 5 V4 After V2 is declared known V known dv Pv V1 1 0 0 V2 1 2 V1 V3 0 3 V4 V4 1 1 V1 V5 1 3 V4 Fig. 5.4.4(e) V6 0 9 V4 V7 0 5 V4 After V5 is declared known * 0 2 * 1 |
3 | |||||||||||||||||
9 |
5 | ||||||||||||||||||||||
* |
* |
0 |
2 |
* |
1 |
3 | |||||||||||||||||
3 | |||||||||||||||||||||||
* * 0 2 * 1 9 5 | |||||||||||||||||||||||
* |
* | ||||||||||||||||||||||
0 |
2 |
* |
* |
1 |
3 |
3 |
* * 0 2 * * 1 9 5 | ||||||||||||||||
| |||||||||||||||||||||||
Data Structures 5.22 | |||||||||||||||||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||||||||||||||||||||
* |
* |
2 |
0 |
| ||||||||||||||||||||||||||||||||||||
* |
* |
* | ||||||||||||||||||||||||||||||||||||||
1 |
3 | |||||||||||||||||||||||||||||||||||||||
3 | ||||||||||||||||||||||||||||||||||||||||
8 5 | ||||||||||||||||||||||||||||||||||||||||
|
V known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 3 V4 V4 1 1 V1 V5 1 3 V4 Fig. 5.4.4(f) V6 0 8 V3 V7 0 5 V4 After V3 is declared known V known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 3 V4 V4 1 1 V1 V5 1 3 V4 Fig. 5.4.4(g) V6 0 6 V7 V7 1 5 V4 After V7 is declared known V known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 3 V4 V4 1 1 V1 V5 1 3 V4 Fig. 5.4.4 (h) V6 1 6 V7 V7 1 5 V4 After V6 is declared known and algorithm terminates * * 2
2 * * |
0 | ||||||||||||||||||||||||||||||||||||||
* |
* |
* |
3 | |||||||||||||||||||||||||||||||||||||
3 | ||||||||||||||||||||||||||||||||||||||||
* |
* |
5 |
6 |
| ||||||||||||||||||||||||||||||||||||
Data Structures 5.23 |
![]() |
![]() |
![]() |
The shortest distance from the source vertex V1 to all other vertex is listed below : V1 V1 V1 Note :- The total running time of this algorithm is 5.5 Minimum Spanning Tree A spanning tree of a connected graph is its connected a cyclic subgraph that contains all the vertices of the graph. A minimum spanning tree of a weighted connected graph G is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges. The total number of edges in Minimum Spanning Tree (MST) is
Fig. 5.5.1 Connected Graph G
Cost = 7 Cost = 8 Cost = 9
Cost = 8 Cost = 5 Spanning Tree for the above Graph | ||
| ||
Data Structures 5.24 | ||
![]() |
![]() |
![]() |
Minimum Spanning Tree
Cost = 5 Spanning Tree with minimum cost is considered as Minimum Spanning Tree 5.5.1 Prim's Algorithm Prim's algorithm is one of the way to compute a minimum spanning tree which uses a greedy technique. This algorithm begins with a set U initialised to {1}. It this grows a spanning tree, one edge at a time. At each step, it finds a shortest edge (u,v) such that the cost of (u, v) is the smallest among all edges, where u is in Minimum Spanning Tree and V is not in Minimum Spanning Tree. SKETCH OF PRIM'S ALGORITHM void Prim (Graph G) { MSTTREE T; Vertex u, v; Set of vertices V; Set of tree vertices U; T = NULL; /* Initialization of Tree begins with the vertex `1' */ U = {1} while (U # V) { Let (u,v) be a lowest cost such that u is in U and v is in V - U; T = T U {(u, v)}; U = U U {V}; } }
| ||
| ||
Data Structures 5.25 | ||
![]() |
![]() |
![]() |
ROUTINE FOR PRIMS ALGORITHM void Prims (Table T) { vertex V, W; /* Table initialization */ for (i = 0; i < Numvertex ; i++) { T[i]. known = False; T[i]. Dist = Infinity; T[i]. path = 0; } for (; ;) { Let V be the start vertex with the smallest distance T[V]. dist = 0; T[V]. known = True; for each W adjacent to V If (! T[W] . Known) { T[W].Dist = Min (T[W]. Dist, CVW); T[W].path = V; } } } Example : -
Fig. 5.5.2 Undirected Graph G
| ||
| ||
Data Structures 5.26 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
|
2 |
| ||||||||
2 1 2
| ||||||||||
3 | ||||||||||
| ||||||||||
1 | ||||||||||
V known dv Pv a 0 0 0 b 0 c 0 d 0 Fig. 5.5.2 (a) INITIAL CONFIGURATION Here, `a' is taken as source vertex and marked as visited. Then the distance of its adjacent vertex is updated as follows : T[b].dist = Min [T[b].Dist, Ca,b] = Min ( = 2 T[b].dist = Min [T[d].Dist, Ca,b] = Min ( = 1 T[c].dist = Min [T[c].Dist, Ca,b] = Min ( = 3 V known dv Pv a 1 0 0 b 0 2 a c 0 3 a d 0 1 a Fig. 5.5.2 (b) After `a' is marked visited Next, vertex `d' with minimum distance is marked as visited and the distance of its unknown adjacent vertex is updated. T[b].Dist = Min [T[b].Dist, Cd,b] = Min (2, 2) = 2 T[c].dist = Min [T[c].Dist, Cd,c] = Min (3,1) = 1
Data Structures 5.27 |
![]() |
![]() |
![]() |
V known dv Pv a 1 0 0 b 0 2 a c 0 1 d d 1 1 a Fig. 5.5.2 (c) After the vertex `d' is marked visited. Next, the vertex with minimum cost `c' is marked as visited and the distance of its unknown adjacent vertex is updated. V known dv Pv a 1 0 0 b 0 2 a c 1 1 d d 1 1 a Fig. 5.5.2 (d) After `c' is marked visited Since, there is no unknown vertex adjacent to `c', there is no updation in the distance. Finally, the vertex `b' which is not visited is marked. V known dv Pv a 1 0 0 b 1 2 a c 1 1 d d 1 1 1 Fig. 5.5.2 (e) After `d' is marked visited, the algorithm terminates The minimum cost of this spanning
Tree is 4 [i.e Ca, b + Ca,d + Cc, d]
Fig. 5.5.2 (f) MINIMUM SPANNING TREE
* * *
2 * * * *
| ||
| ||
Data Structures 5.28 | ||
![]() |
![]() |
![]() |
|
Example 2 :
Undirected Graph G. V Known dv Pv V1 0 0 0
V2 0
V3 0
V4 0
V5 0
V6 0
V7 0 Initial Configuration of table used in prim's Algorithm
Consider V1 as source vertex and proceed from there.
Fig. 5.5.3 (a)
2 4 1
| |||
|
Data Structures 5.29 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
Vertex V1 is marked as visited and then the distance of its adjacent vertices are updated as follows. T[V2].dist = Min [T[V2].dist, Cv1, v2] = Min [ T[V4].dist = Min [T[V4].dist, Cv1, v4] = Min [ T[V3].dist = Min [T[V3].dist, Cv1, v3] = 4 V Known dv Pv V1 1 0 0 V2 0 2 V1 V3 0 4 V1 V4 0 1 V1
V5 0
V6 0
V7 0 Fig. 5.5.3 (b) The table after V1 is declared known. Vertex V4 is marked as visited and then the distance of its adjacent vertices are updated. V Known dv Pv V1 1 0 0 V2 0 2 V1 V3 0 2 V4 V4 1 1 V1 V5 0 7 V4 V6 0 8 V4 V7 0 4 V4 Fig. 5.5.3 (c) The table after V4 is declared known | ||||||
|
|
* 1 3 7 2 * 4 8 | ||||
| ||||||
Data Structures 5.30 | ||||||
![]() |
![]() |
![]() |
Vertex V2 is visited andits adjacent vertices distances were updated. T[V4].dist = Min [T[V4].dist, Cv2, v4] = Min [1, 3] = 1. T[V5].dist = Min [T[V5].dist, Cv2, v5] = Min [7, 10] = 7. V Known dv Pv V1 1 0 0 V2 1 2 V1 V3 0 2 V4 V4 1 1 V1 V5 0 7 V4 V6 0 8 V4 V7 0 4 V4 Fig. 5.5.3(e) The table after V2 is declared T[V6].dist = Min [T[V6].dist, Cv3, v6] = Min [8, 5] = 5. T[V6].dist = 5.
V Known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 2 V4 V4 1 1 V1 V5 0 7 V4 V6 0 5 V3 V7 0 4 V4 Fig. 5.5.3 (e) The table after V3 is declared known
* * * * * * * | ||
| ||
Data Structures 5.31 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||||||
T[V6].dist = Min [T[V6].dist, Cv7,v6] = Min [5, 1] = 1. T[V6].dist = Min [T[V6].dist, Cv7,v5] = Min (7, 6) = 6. V Known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 2 V4 V4 1 1 V1 V5 0 6 V7 V6 0 1 V7 V7 1 4 V4 Fig. 5.5.3 (f) The table after V7 is declared known V Known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 2 V4 V4 1 1 V1 V5 0 6 V7 V6 1 1 V7 V7 1 4 V4 Fig. 5.5.3 (h) The table after V6 is declared known *
| |||||||||||||
* | |||||||||||||
* |
* |
* |
* * * * * * * | ||||||||||
| |||||||||||||
Data Structures 5.32 | |||||||||||||
![]() |
![]() |
![]() |
V Known dv Pv V1 1 0 0 V2 1 2 V1 V3 1 2 V4 V4 1 1 V1 V5 1 6 V7 V6 1 1 V7 V7 1 4 V4 Fig. 5.5.3 (h) The table after V5 is declared known
The Minimum cost of this spanning tree is 16.
Fig. 5.5.3 (i) 5.6 Depth First Search Depth first works by selecting one vertex V of G as a start vertex ; V is marked visited. Then each unvisited vertex adjacent to V is searched in turn using depth first search recursively. This process continues until a dead end (i.e) a vertex with no adjacent unvisited vertices is encountered. At a deadend, the algorithm backsup one edge to the vertex it came from and tries to continue visiting unvisited vertices from there. The algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end. By then, all the vertices in the same connected component as the starting vertex have been visited. If unvisited vertices still remain, the depth first search must be restarted at any one of them. To implement the Depthfirst Search perform the following Steps : Step : 1 Choose any node in the graph. Designate it as the search node and mark it as visited. Step : 2 Using the adjacency matrix of the graph, find a node adjacent to the search node that has not been visited yet. Designate this as the new search node and mark it as visited. * * * * * * *
| ||
| ||
Data Structures 5.33 | ||
![]() |
![]() |
![]() |
Step : 3 Repeat step 2 using the new search node. If no nodes satisfying (2) can be found, return to the previous search node and continue from there. Step : 4 When a return to the previous search node in (3) is impossible, the search from the originally choosen search node is complete. Step : 5 If the graph still contains unvisited nodes, choose any node that has not been visited and repeat step (1) through (4). ROUTINE FOR DEPTH FIRST SEARCH Void DFS (Vertex V) { visited [V] = True; for each W adjacent to V if (! visited [W]) Dfs (W); } Example : -
Fig. 5.6
Adjacency Matrix A B C D A 0 1 1 1 B 1 0 0 1 C 1 0 0 1 D 1 1 1 0 Implementation 1. Let `A' be the source vertex. Mark it to be visited. 2. Find the immediate adjacent unvisited vertex `B' of `A' Mark it to be visited.
| ||
| ||
Data Structures 5.34 | ||
![]() |
![]() |
![]() |
3. From `B' the next adjacent vertex is `d' Mark it has visited. 4. From `D' the next unvisited vertex is `C' Mark it to be visited.
Depth First Spanning Tree Applications of Depth First Search 1. To check whether the undirected graph is connected or not. 2. To check whether the connected undirected graph is Bioconnected or not. 3. To check the a Acyclicity of the directed graph. 5.6.1 Undirected Graphs A undirected graph is `connected' if and only if a depth first search starting from any node visits every node.
An Undirected graph
| ||
| ||
Data Structures 5.35 | ||
![]() |
![]() |
![]() |
Adjacency Matrix A B C D E A 0 1 0 1 1 B 1 0 1 1 0 C 0 1 0 1 1 D 1 1 1 0 0 E 1 0 1 0 0 Implementation We start at vertex `A'. Then Mark A as visited and call DFS (B) recursively, Dfs (B) Marks B as visited and calls Dfs(c) recursively.
Fig. 5.6.1 (a) Dfs (c) marks C as visited and calls Dfs (D) recursively. No recursive calls are made to Dfs (B) since B is already visited.
Fig. 5.6.1(b) Dfs(D) marks D as visited. Dfs(D) sees A,B,C as marked so no recursive call is made there, and Dfs(D) returns back to Dfs(C). | ||
| ||
Data Structures 5.36 | ||
![]() |
![]() |
![]() |
Fig. 5.6.1 (c) Dfs(C) calls Dfs(E), where E is unseen adjacent vertex to C.
Fig. 5.6.1 (d) Since all the vertices starting from `A' are visited, the above graph is said to be connected. If the graph is not connected, then processing all nodes requires reversal calls to Dfs, and each generates a tree. This entire collection is a depth first spanning forest. 5.6.2 Biconnectivity A connected undirected graph is biconnected if there are no vertices whose removal disconnects the rest of the graph. Articulation Points The vertices whose removal would disconnect the graph are known as articulation points.
| ||
| ||
Data Structures 5.37 | ||
![]() |
![]() |
![]() |
Fig. 5.6.2 Connected Undirected Graph Here the removal of `C' vertex will disconnect G from the graph. lllly removal of `D' vertex will disconnect E & F from the graph. Therefore `C' & `D' are articulation points.
Fig. 5.6.2 (a) Removal of vertex `C'
| ||
| ||
Data Structures 5.38 | ||
![]() |
![]() |
![]() |
Fig. 5.6.2 (b) Removal of vertex `D' The graph is not biconnected, if it has articulation points. Depth first search provides a linear time algorithm to find all articulation points in a connected graph. Steps to find Articulation Points : Step 1 : Perform Depth first search, starting at any vertex Step 2 : Number the vertex as they are visited, as Num (v). Step 3 : Compute the lowest numbered vertex for every vertex v in the Depth first spanning tree, which we call as low (w), that is reachable from v by taking zero or more tree edges and then possibly one back edge. By definition, Low(v) is the minimum of (i) Num (v) (ii) The lowest Num (w) among all back edges (v, w) (iii) The lowest Low (w) among all tree edges (v, w) Step 4 : (i) The root is an articulation if and only if it has more than two children. (ii) Any vertex v other than root is an articulation point if and only if v has same child w such that Low (w) Num (v), The time taken to compute this algorithm an a graph is Note For any edge (v, w) we can tell whether it is a tree edge or back edge merely by checking Num (v) and Num (w). If Num (w) > Num (v) then the edge (v, w) is a back edge.
| ||
| ||
Data Structures 5.39 | ||
![]() |
![]() |
![]() |
Fig. 5.6.3 ROUTINE TO COMPUTE LOW AND TEST FOR ARTICULATION POINTS void AssignLow (Vertex V) { Vertex W; Low [V] = Num [V]; /* Rule 1 */ for each W adjacent to V { If (Num [W] > Num [V]) /* forward edge */ { Assign Low (W); If (Low [W]> = Num [V]) Printf ("% V is an articulation pt \n", V); Low[V] = Min (Low [V], Low[V]); /* Rule 3*/ } Else If (parent [V] ! = W) /* Back edge */ Low [V] = Min (Low [V], Num [W])); /* Rule 2*/ } }
| ||
| ||
Data Structures 5.40 | ||
![]() |
![]() |
![]() |
Fig. 5.6.4 Depth First Tree For Fig (5.6.2) With Num and Low. Low can be computed by performing a postorder traversal of the depth - first spanning tree. (ie) Low (F) = Min (Num (F), Num (D)) /* Since there is no tree edge & only one back edge */ = Min (6, 4) = 4 Low (F) = 4 Low (E) = Min (Num (E), Low (F)) /* there is no back edge */. = Min (5, 4) = 4 Low (D) = Min (Num (D), Low (E), Num (A)) = Min (4,4,1) = 1 Low (D) = 1 Low (G) = Min (Num (G)) = 7 /* Since there is no tree edge & back edge */ Low (C) = Min (Num (C), Low (D), Low (G)) = Min (3,1,7) = 1 Low (C) = 1 . lllly Low (B) = Min (Num (B), Low (C)) = Min (2,1) = 1 Low (A) = Min (Num (A), Low (B)) = Min (1, 1) = 1
| ||
| ||
Data Structures 5.41 | ||
![]() |
![]() |
![]() |
Low (A) = 1. From fig (5.8) it is clear that Low (G) > Num (C) (ie) 7 > 3 /* if Low (W) Num (V)*/ the `v' is an articulation pt Therefore `C' is an articulation point. lllly Low (E) = Num (D), Hence D is an articulation point. 5.7.2 NP - Complete Problems A decision problem D is said to be NP complete if 1. It belongs to class NP. 2. Every problem in NP is polynomially reducible to D. A problem P1 can be reduced to P2 as follows Provide a mapping so that any instance of P1 can be transformed to an instance of P2. Solve P2 and then map the answer back to the original. As an example, numbers are entered into a pocket calculator in decimal. The decimal numbers are converted to binary, and all calculations are performed in binary. Then the final answer is converted back to decimal for display. For P1 to be polynomially reducible to P2, all the work associated with the transformations must be performed in polynomial time. The reason that NP - complete problems are the hardest NP problems is that a problem that is NP - complete can essentially be used as a subroutine for any problem in NP, with only a polynomial amount of overhead. Suppose we have an NP - complete problem P1. Suppose P2 is known to be in NP. Suppose further that P1 polynomially reduces to P2, so that we can solve P1 by using P2 with only a polynomial time penalty. Since P1 is NP - complete, every problem in NP polynomially reduces to P1. By applying the closure property to polynomials, we see that every problem in NP is polynomially reducible to P2; we reduce the problem to P1 and then reduce P1 to P2. Thus, P2 is NP - Complete. Travelling salesman problem is NP - complete. It is easy to see that a solution can be checked in polynomial time, so it is certainly in NP. Hamilton cycle problem can be polynomially reduced to travelling salesman problem.
Hamilton Cycle Problem transformed to travelling salesman problem. Some of the examples of NP - complete problems are Hamilton circuit, Travelling salesman, knapsack, graph coloring, Bin packing and partition problem. | ||
| ||
Data Structures 5.42 | ||
![]() |
![]() |
![]() |
UNIT - V PART - A Questions 1. Define a graph 2. Compare directed graph and undirected graph 3. Define path, degree and cycle in a graph 4. What is an adjacency matrix? 5. Give the adjacency list for the following graph
6. Define Topological Sort 7. Define Shortest path problem. Give examples 8. Define Minimum Spanning Tree and write its properties. 9. What is DAG? Write its purpose 10. What are the different ways of traversing a graph? 11. What are the various applications of depth first search? 12. What is an articulation point? 13. When a graph is said to be binconnected? 14. Write down the recursive routine for depth first search. 15. Write a procedure to check the biconnectivity of the graph using DFS. 16. Define Class_NP 17. What is meant by NP_Complete problem?
| ||
| ||
Data Structures 5.43 | ||
![]() |
![]() |
![]() |
![]() |
![]() |
PART - B 1. What is Topological Sort? Write down the pseudocode to perform topological sort and apply the same to the following graph.
2. Explain the Dijkstra's algorithm and find the shortest path from A to all other vertices in the following graph.
3. Explain prim's algo/.. in detail and find the minimum spanning
tree for the following graph.
| ||||
| ||||
| ||||
Data Structures 5.44 | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
4. Find all the articulation points in the given graph. Show the depth_first spanning tree and the values of Num and Low for each vertex. | ||||
| ||||
| ||||
Data Structures 5.45 | ||||
![]() |
![]() |
![]() |
REFERENCE BOOKS
"Data Structures and Algorithm Analysis in C" by Mark Allen Weiss. "Data Structures and Algorithms "by Alfred Aho, John E.Hopcroft and Jeffery D.Ullman "Data Structures and Algorithms in C++ "by Adam Drozdek. "Introduction to Data Structures" by Bhagat Singh and Thomas L.Naps. "Computer Algorithms" by Sara Baase and Allen Van Golder. "Introduction to Design and Analysis" by Sara Baase and Allen Van Golder. "How to solve it by Computer" by Dromey. | ||
| ||
Data Structures | ||