2. breadth first search (worth 30 points) Implement function breadth_first follo

Question

2. breadth first search (worth 30 points) Implement function breadth_first following this pseudo code. Don't forget to import math to allow use of math.inf def breadth first (graph, start_vertex): Initialize three dictionaries named color, parent, and distance to empty dictionaries. Set the color and distance of the start vertex to grey and 0. Add the start_vertex to an empty queue. Repeat until the queue is empty: u : queue.pop() # off end of queue for v in graph .get(u, []): # for each vertex v in the adjacency list of vertex uvertices If v is not in the color dictionary: Set v's color to grey, its distance to 1+u's distance, and its parent to u. Insert vertex v into the queue Set the color of vertex u to black, showing we have finished with that vertex. Return the color, parent, and distance dictionaries.

Explanation / Answer

A standard BFS implementation puts each vertex of the graph into one of two categories:

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The algorithm works as follows:

The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph

-----------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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