Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Python

Solution: Breadth-First Graph Traversal

In this review, we will learn how to write code for the breadth-first traversal of a graph.

We'll cover the following...

Solution:

bfs
graph.py
def bfs(my_graph, source):
    """
    Function to print a BFS of graph
    :param graph: The graph
    :param source: starting vertex
    :return:
    """
    
    # Mark all the vertices as not visited
    visited = [False] * (len(my_graph.graph))
    # Create a queue for BFS
    queue = []
    # Result string
    result = ""
    # Mark the source node as
    # visited and enqueue it
    queue.append(source)
    visited[source] = True
    
    while queue:
        # Dequeue a vertex from
        # queue and print it
        source = queue.pop(0)
        result += str(source)
        temp=my_graph.graph[source] # original graph will not be affected
        # Get all adjacent vertices of the
        # dequeued vertex source. If a adjacent
        # has not been visited, then mark it
        # visited and enqueue it
        while temp is not None:
            data = temp.vertex
            if not visited[data]:
                queue.append(data)
                visited[data] = True
            temp=temp.next
    return result
# Main to test the above program
if __name__ == "__main__":
    
    V = 5
    g = Graph(V)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 3)
    g.add_edge(1, 4)
    print(bfs(g, 0))

Explanation

In this algorithm, we begin from a selected node (it can be a root node) and traverse the graph layerwise (one level at a time). All neighbor nodes (those connected to the source node) are explored, then, we move to the next level of neighbor nodes.

Simply, as the name breadth-first suggests, we traverse the graph by moving horizontally, visiting all the nodes of the current layer, and moving to the next layer.

Avoid visiting the same nodes again

A graph may contain cycles, which will lead to visiting the same node again and again, while we traverse the graph. To avoid processing the same node again, we can use a boolean array that marks visited arrays.

To make this process easy, use a queue to store the node and mark it as visited until all its neighbors (vertices that are directly connected to it) are marked.

The queue follows the First In First Out (FIFO) queuing method. Therefore, neighbors of the node will be visited in the order in which they were inserted in the queue, i.e. the node that was inserted first will be visited first and so on.

Remember to mark all ∣V∣|V| vertices as not-visited before running the algorithm.

Time complexity

The time complexity of BFS can be computed as the total number of iterations performed by the while loop in the code above.

Let EE be the set of all edges in the connected component visited by the algorithm. For each edge u,v{u, v} in EE the algorithm makes two while loop iteration steps: one time when the algorithm visits the neighbors of uu and one time when it visits the neighbors of vv.

Hence, the time complexity is OO(∣V∣|V| ++ ∣E∣|E|).