We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Breadth First Search: Shortest Reach
  5. Discussions

Breadth First Search: Shortest Reach

  • MahmoudAI
     + 0 comments
    Simple BFS solution (explained)

    1. Intuition behind the solution:

      • The problem requires finding the shortest distance from a given starting node to all other nodes in an undirected graph.
      • The breadth-first search (BFS) algorithm is well-suited for this task as it explores the nodes level by level, guaranteeing that the shortest path is found when a node is visited.
      • By initializing the distances to all nodes as -1, except the starting node with a distance of 0, and using a queue to keep track of nodes to visit, we can gradually update the distances as we explore the graph.

    2. Approach of the solution:

      • Create a graph representation using a defaultdict of lists to store the adjacency list for each node.
      • Initialize a distances list with -1 for all nodes, except the starting node which is set to 0.
      • Use a deque (double-ended queue) to implement the BFS traversal.
      • Start from the given starting node and enqueue it.
      • While the queue is not empty, dequeue a node and explore its neighbors.
      • For each unvisited neighbor, update its distance if it is -1 (indicating unvisited) and enqueue it.
      • Repeat the process until all nodes have been visited.
      • Remove the distance to the starting node from the distances list.
      • Return the distances list.

    3. Time complexity:

      • Constructing the graph takes O(m) time, where m is the number of edges.
      • The BFS traversal visits each node and edge once, resulting in a time complexity of O(n + m), where n is the number of nodes.
      • Overall, the time complexity is O(n + m).

    4. Space complexity:

      • The space complexity is determined by the graph representation and the queue used in BFS.
      • The graph representation requires O(n + m) space to store the adjacency lists.
      • The queue can have a maximum size of n (in case all nodes are connected), resulting in O(n) space.
      • Additionally, the distances list requires O(n) space.
      • Overall, the space complexity is O(n + m).
    from collections import defaultdict, deque

def bfs(n, edges, s):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    distances = [-1] * n
    distances[s-1] = 0

    queue = deque([s])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if distances[neighbor-1] == -1:
                distances[neighbor-1] = distances[node-1] + 6
                queue.append(neighbor)

    distances.pop(s-1)
    return distances