Consider the following graph. With the indicated edge weights, start from vertex

Question

Consider the following graph. With the indicated edge weights, start from vertex x, use the Breadth First Search (BFS) algorithm (described in the textbook) to compute the BFS tree. Show intermediate results similar to the textbook example, and show the final BFS tree. In cases when several candidate vertices have the same minimal costs, choose a vertex according to its alphabetical order. Based on the same graph shown in A1, use the Kruskal's algorithm to compute the Minimum Spanning Tree (MST). Show intermediate results similar to the textbook example, and show the final MST.

Explanation / Answer

A1.
     The breadth first search tree formation is as follows:

     Add starting vertex to the queue. Take out from the queue and mark it current. While visiting current's adjacent nodes, add nodes to the queue and make
     their parent as current. Then take another element from the queue and repeat the same step.

     Step 1:
                          x

                   w       v       y

   Step 2:
                          x

                   w       v       y

               u        t

A2. Kruskal's algorithm:
               sort the edges
               Insret the edges in the sorted order without creating a cycle.

         wt    edge
         1     xw
         2     ut
         2     vy
         3     uv
         4     vw
         4     vt
         4     xy
         5     yt
         7     xv

   So the MST will consist of xw,ut,vy,uv,vw

                 

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.