Question

Show that a breadth-first spanning tree contains the shortest paths be- tween the root to every other vertex.

Answer 1

Let us Consider the Following weighted graph

Let us consider a is the Root then BFS of a graph is as follows

BFS: Step 1:                                                

Output:  a b

Step 2:               

                  

Output: a b e

Step 3:               

              

Output: a b e g

Step 4:     

Output: a b e g c

Step 5:             

                           

Output: a b e g c f

Step 6 :      

Output: a b e g c f d   

Step 7:       

Output: a b e g c f d h

The BFS of a graph starting at vertex a is a b e g c f d h

BFS Tree as follows

Kruskal’s Algorithm to find the Minimum Cost Spanning Tree (MCST) of a graph G as follows:

Here consider those edges in each step which are minimum and doesnot form Loops

Edge: Cost:

a - e 1   

a - b 2

a - g 3

b - c 3

b - e 3

e - f 4

e - g 4

f - h 5

c - f 7

c - e 8

c - d 9

d - f 11

Step 1:

Step 2:

  

Step 3:

Step 4:

  

Step 5:

Step 6 :

  

Step 7:

For n- Vertices we get (n-1) Edges in MCST. Here in graph having 8 Vertices so we get 7 Edges

Which is Required MCST of a graph using Kruskal’s Algorithm

Note:

From the above Minimum Cost Spanning Tree (MCST) of a graph obtained in Kruskal’s Algorithm and Breadth First Search (BFS) Algoritm both are same
so we can say that breadth-first spanning tree contains the shortest paths be- tween the root to every other vertex.