Question

4. Consider the following graph: 2 . Starting from node B, please copy the above picture as many times as needed and, for each approach to building a spanning tree below, (a) draw the tree and (b) Show (by writing a number next to each node) the order in which nodes are added to the tree during its construction: a. Dijkstra's spanning tree (2 points) b. Prim's spanning tree (2 points) c. Depth-first tree (2 points) d. Breadth-first tree (2 points)

Answer 1

a) Dijkstra’s shortest-path algorithm to compute the shortest path from “B” to all network nodes is as follows

Step | D(B) P(B) Vertex / Node D(A)P(A) D(C) P(C) D(D)PD) D(E) P(E) D(F) P(F) D(G)P(G) D(H)P(H) D(1) P(1) ТВ 0,B oo 2,B 2,B(min) 1,B(min) 1,B F E 2,B 1,B 5(4+1),F 5,F 5,F 5,F(min) 2,B 2,B VOLAWN 0,B 0,B 0,B 0, B 0, B 0,B 0,B 0,B 5,B 5,B 5,B(min) 5,B 5,B 5,B 5,B 5, B 6 5,B 7 7 7(5+2), E 7,E ,E ,E 7,E(min) 7,E 7,E 5 6(4+2), E 6,E 6,E 6,E(min) 6,E ,E 6,E 5(4+1),F 5,F 5,F(min) 5,F 5,F 5,F 5,F 5,F 5,F 1,B 1,B 1,B 1,B 1,B 1,B 6 2,B 2,B 2,B D 12(7+5), 12(6+6),D 12,D(min) 12,D 7 A 5,F 5,F 5,F 2,B

Explanation:
D(A): cost of the least-cost path from the source Vertex to destination A as of this iteration of the algorithm.
P(A): previous Vertex (neighbor of b) along the current least-cost path from the source to A.
N' : subset of Vertexes; A is in N' if the least-cost path from the source to A is definitively known.

Step 0: Initially we take B as a minimum Weight and highlight that value
Step 1: In this we consider the minimum weight other than Node B that is at Node F we have minimum weight so highlight that value
Step 2: In this we consider the minimum weight other than Nodes B & F that is at Node E we have minimum weight so highlight that value
Step 3: In this we consider the minimum weight other than Node B,E & F that is at Node C we have minimum weight so highlight that value
Step 4: In this we consider the minimum weight other than Node B,C,E & F that is at Node G we have minimum weight so highlight that value
Step 5: In this we consider the minimum weight other than Node B,C,E,F & G that is at Node I we have minimum weight so highlight that value

Step 6: In this we consider the minimum weight other than Node B,C,E,F,G & I that is at Node D we have minimum weight so highlight that value

Step 7: In this we consider the minimum weight other than Node B,C,D,E,F,G & I that is at Node A we have minimum weight so highlight that value

Step 8: In this we consider the minimum weight other than Node A,B,C,D,E,F,G & I that is at Node H we have minimum weight so highlight that value

Edge	B - A	B - C	B - D	B - E	B - F	B - G	B - H	B - I
Cost	7	5	6	2	1	5	12	5

The shortest path tree from the above routing table.

$1587876956009_blob.png$

b) Prim’s Algorithm to find the minimum cost spanning tree of a graph starting at Node (B) as follows

Step 1: All the Nodes connected to (B) will be considered

Edge	Cost	$1587877879500_blob.png$
B-C	5
B-E	2
B-F	1(min)

Step 2: All the Nodes connected to (B) & (F) will be considered

Edge	Cost	$1587877879483_blob.png$
B-C	5
B-E	2(min)
F-E	2
F-G	4
F-I	4

Step 3: All the Nodes connected to (B), (E) & (F) will be considered

.Edge	Cost	$1587877879575_blob.png$
B-C	5
F-E	2(min but form Loop)
F-G	4
F-I	4
E-A	5
E-D	4(min)
E-I	5

Step 4: All the Nodes connected to (B), (D), (E) & (F) will be considered

Edge	Cost	$1587877879656_blob.png$
B-C	5
F-G	4
F-I	4
E-A	5
E-I	5
D-A	3(min)
D-H	6

Step 5: All the Nodes connected to (A), (B), (D) , (E) & (F) will be considered

Edge	Cost	$1587877879504_blob.png$
B-C	5
F-G	4(min)
F-I	4
E-A	5
E-I	5
D-H	6

Step 6: All the Nodes connected to (A), (B), (D) , (E) , (F) & (G) will be considered

Edge	Cost	$1587877879646_blob.png$
B-C	5
F-I	4
E-A	5
E-I	5
G-C	2(min)
G-I	6
D-H	6

Step 7: All the Nodes connected to to (A), (B), (C), (D) , (E) , (F) & (G) will be considered

Edge	Cost	$1587877879638_blob.png$
B-C	5
F-I	4(min)
E-A	5
E-I	5
G-I	6
D-H	6

Step 8: All the Nodes connected to to (A), (B), (C), (D) , (E) , (F),(G) & (I) will be considered

Edge	Cost	* -) 6)
B-C	5(min but form Loop)
E-A	5(min but form Loop)
E-I	5(min but form Loop)
G-I	6(min but form Loop)
I-H	7
D-H	6(min)

c) Deapth First Search(DFS)

DFS: Step 1:                                        

E

Output: B C

Step 2:                                 

E

Output: B C G

Step 3:                            

E

Output: B C G I

Step 4:               

E

Output: B C G I H

Step 5:                                        

E

Output: B C G I H D

Step 6 :                                 

$1587878121511_blob.png$

Output: B C G I H D A

Step 7:                             

$1587878142547_blob.png$

Output: B C G I H D A E

Step 8:   

1) ค

Output: B C G I H D A E F

The DFS of a graph starting at Node B is B C G I H D A E F

DFS Tree as follows

CO N

Breadth First Search(bFS)

BFS: Step 1:                                        

EI

Output: B C

Step 2:                                 

$1587878243030_blob.png$

Output: B C E

Step 3:                            

2®

Output: B C E F

Step 4:               

28

Output: B C E F G

Step 5:                                        

26 E

Output: B C E F G A

Step 6 :                                 

$1587878325230_blob.png$

Output: B C E F G A D

Step 7:                             

$1587878357432_blob.png$

Output: B C E F G A D I

Step 8:   

$1587878371907_blob.png$

Output: B C E F G A D I H

The BFS of a graph starting at Node B is B C E F G A D I H

BFS Tree as follows

$1587878479031_blob.png$