Implementing BFS (Breadth First Search) for Graph Traversal in Python

thumbnail

BFS is one of the basic algorithm for graph traversal. BFS uses a queue to keep track of visited nodes. The basic idea behind the BFS is to visit the adjacent nodes of the starting node, keep them in the queue and mark them as visisted. Then pick up the next node from the queue and continue the process until the queue is empty.

Here is an youtube video which explains the BFS with a nice visual example:

Breadth First Search Algorithm

BFS is useful to find the shortest path in a graph between two nodes. It can also be used to find out if a graph is connected or not.

Inspite of those benefits, BFS cannot be used for larger graphs because the time complexity is O(# of nodes + # of edges) which gets exponential as the graph size increases.

Source: Wikimedia

Here is an example implementation of BFS in python:

def bfs(graph, start):
    visited = []
    queue = [start]

    while len(queue) > 0:
        current = queue.pop(0)
        if current in visited:
            continue

        visited.append(current)
        for node in graph[current]:
            if node in visited:
                continue
            queue.append(node)

    return visited

if __name__ == '__main__':
    graph = {
        1: [1, 2, 5],
        2: [3, 5],
        3: [2, 4],
        4: [3, 5, 6],
        5: [1, 2, 4],
        6: [4]
    }

    paths = bfs(graph, 1)

    print(paths)

So, now as we learned how to code a BFS, when to use it or it's other counter part DFS? Here is a good discussion about some practical cases regarding when to use BFS or DFS:
https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Back To Top