Can you implement a Breadth-First Search on a graph?

Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts from a selected node (source or root) and traverses the graph layerwise, exploring the neighbour nodes (ie, nodes which are directly connected to source node). It then moves towards the next-level neighbors.

Here’s a Python algorithm for BFS:

def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)

    while queue:

        # Dequeue a vertex from queue
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        # If not visited, marked it as visited and enqueue it
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

The ‘bfs‘ function takes in a graph and a starting node (root) as parameters. The graph is a dictionary of lists where the dictionary keys are the graph vertices, and the list in each key contains the vertices that are adjacent to the key.

Here is an example of using BFS in a graph:

# Construct the graph
graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

bfs(graph, 'A')  # Output: A B C D E F

In the above example, we start traversing from ’A’. ’A’ has two adjacent nodes: ’B’ and ’C’. After visiting them, we visit the neighbours of ’B’ which are ’D’ and ’E’. ’D’ does not have any neighbors and ’E’ has one neighbor ’F’. Finally, we visit ’F’.

The time complexity of BFS can be obtained by following reasoning:

- Each vertex is processed once as BFS ensures that a vertex is not processed more than once.

- Each edge is also processed once.

Thus, the overall time complexity is O(V + E), where:

- V is the number of vertices

- E is the number of edges in the graph.

The space complexity of BFS is O(V), as it needs to store the vertices in the queue. Here, V is the number of vertices in a graph.