Build your intuition. Fill in the missing part by typing it in.
DFS traversal visits all the vertices in the graph in a ___-first manner. It can be used to explore all connected components of a graph and detect ___.
Another common graph traversal algorithm is Breadth-First Search (BFS), which explores all the vertices at the current level before moving to the next level. It is implemented using a ___.
Here's an example of implementing BFS in Python:
1if __name__ == '__main__':
2 from collections import deque
3
4 class Graph:
5 def __init__(self, num_vertices):
6 self.num_vertices = num_vertices
7 self.adj_list = [[] for _ in range(num_vertices)]
8
9 def add_edge(self, source, destination):
10 self.adj_list[source].append(destination)
11 self.adj_list[destination].append(source)
12
13 def bfs(self, start_vertex):
14 queue = deque([start_vertex])
15 visited = [False] * self.num_vertices
16
17 while queue:
18 vertex = queue.popleft()
19
20 if not visited[vertex]:
21 print(vertex)
22 visited[vertex] = True
23
24 for adj_vertex in self.adj_list[vertex]:
25 if not visited[adj_vertex]:
26 queue.append(adj_vertex)
27
28 # Create a graph with 5 vertices
29 g = Graph(5)
30
31 # Add edges to the graph
32 g.add_edge(0, 1)
33 g.add_edge(0, 4)
34 g.add_edge(1, 2)
35 g.add_edge(1, 3)
36 g.add_edge(1, 4)
37 g.add_edge(2, 3)
38 g.add_edge(3, 4)
39
40 # Perform BFS starting from vertex 0
41 print('BFS traversal:')
42 g.bfs(0)In this code, we define a similar Graph class, and the bfs method performs the BFS traversal starting from a given vertex. It uses a queue to keep track of the vertices to visit and the visited list to mark visited vertices.
BFS traversal visits all the vertices in the graph in a ___-first manner. It can be used to find the shortest path between two vertices as well as to explore all the vertices in the graph.
Write the missing line below.