At 3. Let Graph G be connected. Combine DFS and BFS in the following way: Start

Question

At 3. Let Graph G be connected. Combine DFS and BFS in the following way: Start at a vertex, u, find a neighbor, v, that refers the minimum weight on the edge that links these two vertices. Then move to the new vertex (v) and put this edge in a bucket. When you reach the vertex that is visited you will return to the entering vertex, and so on. If you have visited all vertices, the edges in the bucket will form a spanning tree. (1) Is this tree a minimum spanning tree? Verify your answer (2) This method is called the Best Search in Al. The strategy used is called the greedy algorithm. What does your finding in (1) mean? (If you could not answer this question, you can write code for finding the Minimum Spanning Tree.)

Explanation / Answer

Solution:

1)

True, following these steps of the algorithm will form a set of edges collected in the bucket which will represent minimum cost spanning tree for the given graph.

But how?

2)

As I concluded above, this is Prim's algorithm.

Findings:

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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