breadth first search design and analysis of algorithm

bfs

1. Breadth First Search (BFS)

2. Breadth First Search (BFS) Breadth-First Search (BFS) is a fundamental algorithm used in data structures for traversing or searching tree or graph data structures. It starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores all the neighboring nodes before moving to the next level of nodes. The BFS algorithm uses a queue to manage the nodes to be visited. It follows these steps: Visit the adjacent unvisited vertex, mark it as visited, display it, and insert it into the queue. If no adjacent vertex is found, remove the first vertex from the queue

3. algorithm BFS(G,s) let Q be a queue Q.enqueue (s) mark s as visited while Q is not empty v= Q.dequeue () for all neighbors w of v in Graph G if w is not visited Q.enqueue (w) mark w as visited

4. Code for bfs using namespace std; int V = adj.size (); int s = 0; int res; enqueue it visited[s] = true; q.push (s); while (! q.empty ()) { int curr = q.front (); q.pop (); res.push_back ( curr ); for (int x : adj [ curr ]) { if (!visited[x]) { visited[x] = true; q.push (x); } } } return res; }

5. A H B F E D C G Task: Conduct a breadth-first search of the graph starting with node D Breadth-first search starts with given node Step 1

6. A H B F E D C G Nodes visited: D Breadth-first search starts with given node Then visits nodes adjacent in some specified order Step 2

7. A H B F E D C G Step 3 Nodes visited: D, C

8. A H B F E D C G Step 4 Nodes visited: D, C, E

9. A H B F E D C G Step 5 Nodes visited: D, C, E, F

10. A H B F E D C G Step 6 Nodes visited: D, C, E, F, G When all nodes in ripple are visited, visit nodes in next ripples

11. A H B F E D C G Step 7 Nodes visited: D, C, E, F, G, H When all nodes in ripple are visited, visit nodes in next ripples

12. A H B F E D C G Step 8 Nodes visited: D, C, E, F, G, H, A When all nodes in ripple are visited, visit nodes in next ripples

13. A H B F E D C G Step 9 Nodes visited: D, C, E, F, G, H, A, B

14. Analysis of bfs Time Complexity: O(V + E), BFS explores all the vertices and edges in the graph. In the worst case, it visits every vertex and edge once. Therefore, the time complexity of BFS is O(V + E), where V and E are the number of vertices and edges in the given graph. Auxiliary Space: O(V), BFS uses a queue to keep track of the vertices that need to be visited. In the worst case, the queue can contain all the vertices in the graph. Therefore, the space complexity of BFS is O(V).