educative.io

BFS solution not understand the part for visiting the remaining nodes

Courses
,
#1

I do not understand this part:

visit remaining nodes

for i in range(num_of_vertices):
    if not visited[i]:
        result_new, visited = bfs_traversal_helper(g, i, visited)
        result += result_new

Looks like all the nodes would be visited before this part of the code and no nodes would be left to be visited.

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5660403031867392

#2

Hi @Setarehalsadat_Chang !!
This code is responsible for visiting any remaining nodes that were not reached during the initial traversal from the source node.

The BFS (Breadth-First Search) algorithm starts from a source node and explores its neighbors before moving on to the next level of neighbors. It continues this process until all reachable nodes are visited.

However, there might be disconnected components in the graph that are not reachable from the source node. In such cases, those nodes will not be visited during the initial traversal. To ensure that all nodes are visited, the code includes the loop you mentioned.
For example, a graph with disconnected components:

     1 -- 2    4 -- 5
          |
     3 -- 6

In this example, we have two disconnected components: {1, 2, 6, 3} and {4, 5}. There is no edge connecting the nodes in the first component with the nodes in the second component.

When performing a BFS traversal starting from node 1 as the source, the initial traversal will only visit nodes 1, 2, and 6. Node 3 will be left unvisited because it is not reachable from the source node.

To ensure that all nodes are visited, the code provided includes the loop that iterates over all nodes and performs a BFS traversal for each unvisited node. In this example, it will perform a BFS traversal starting from node 3, which will visit node 3 and add it to the final traversal result.

The final BFS traversal result in this example would be “126345”, which includes all nodes in the graph.

I hope it helps. Happy Learning :blush:

1 Like