BFS (Breadth First Search) Algorithm For Graph Traversal

In this article, we’ll explore the Breadth-First Search (BFS) algorithm in graph traversal. We’ll break down a Python code example step-by-step to help beginners understand how it works and how each part of the code contributes to the overall functionality.

What is BFS?

Breadth First Search (BFS) is a fundamental algorithm used to explore nodes and edges of a graph. The BFS algorithm starts at a given node (referred to as the source node) and explores all its neighboring nodes at the present depth before moving on to nodes at the next depth level. It’s like exploring one level at a time, layer by layer.

The Story of BFS

Imagine you are a detective exploring a network of connected suspects (nodes). Each connection (edge) represents a direct relationship between suspects. You start with one suspect and systematically visit all directly connected suspects before moving on to their connections. This ensures you don’t miss any potential leads by diving too deep into one connection before exploring others.

The Python Code for BFS

Here is the Python code we’ll be dissecting:

def bfs(arr, source):
    q = []
    isVisited = [False] * len(arr)

    q.append(source)
    isVisited[source] = True

    while len(q) != 0:
        node = q.pop(0)
        print("Visited Node: ", node)

        for index in range(len(arr)):
            if arr[node][index] == 1 and isVisited[index] == False:
                q.append(index)
                isVisited[index] = True

if __name__ == "__main__":

    arr = [
            [0,1,1,1,0],
            [1,0,0,1,1],
            [1,0,0,1,0],
            [1,1,1,0,1],
            [0,1,0,1,0]
          ]

    print("BFS of the given graph : ")
    bfs(arr, 0)

Let’s walk through this code step-by-step.

Step-by-Step Explanation

1. Function Definition: def bfs(arr, source): We define a function named bfs that takes two parameters: arr, which represents the adjacency matrix of the graph, and source, which is the starting node for the BFS traversal.
2. Initialization: q = [] isVisited = [False] * len(arr) We initialize an empty list q to use as our queue for BFS and a list isVisited to keep track of visited nodes, initially setting all values to False.
3. Starting Point: q.append(source) isVisited[source] = True We append the source node to our queue and mark it as visited in the isVisited list.
4. BFS Loop: while len(q) != 0: We enter a while loop that runs as long as there are nodes in the queue.
5. Visit Node: node = q.pop(0) print("Visited Node: ", node) We dequeue the first node from the queue and print it as the visited node.
6. Explore Neighbors:
   python for index in range(len(arr)): if arr[node][index] == 1 and isVisited[index] == False: q.append(index) isVisited[index] = True
   We iterate through all possible nodes (using their indices). If there is an edge between the current node (node) and the neighbor node (index) and the neighbor hasn’t been visited yet, we enqueue the neighbor and mark it as visited.

Example Walkthrough

Let’s take a closer look at the given adjacency matrix and the BFS traversal starting from node 0:

arr = [
    [0,1,1,1,0],
    [1,0,0,1,1],
    [1,0,0,1,0],
    [1,1,1,0,1],
    [0,1,0,1,0]
]

• Step 1: Start at node 0.
  • Queue: [0]
  • Visited: [True, False, False, False, False]
• Step 2: Visit node 0 and explore its neighbors (1, 2, 3).
  • Queue: [1, 2, 3]
  • Visited: [True, True, True, True, False]
• Step 3: Visit node 1 and explore its neighbors (3, 4). Node 3 is already visited, so we only add node 4.
  • Queue: [2, 3, 4]
  • Visited: [True, True, True, True, True]
• Step 4: Visit node 2, but its only neighbor (3) is already visited.
  • Queue: [3, 4]
  • Visited: [True, True, True, True, True]
• Step 5: Visit node 3, but all its neighbors are already visited.
  • Queue: [4]
  • Visited: [True, True, True, True, True]
• Step 6: Visit node 4, but all its neighbors are already visited.
  • Queue: []
  • Visited: [True, True, True, True, True]

The BFS traversal order for this graph starting from node 0 is: 0, 1, 2, 3, 4.

Conclusion

BFS is a powerful algorithm for traversing or searching tree or graph data structures. It explores all nodes at the present depth level before moving on to the nodes at the next depth level. Understanding BFS helps in solving many practical problems in computer science, such as finding the shortest path in unweighted graphs, searching in AI, and more.

By following the steps and understanding each part of the code, beginners can implement BFS in their own projects and explore the fascinating world of graph theory.