mediumGraphsPattern: DFS/BFS
Minimum Edges to Reach Target Solution
Problem Statement
Given a directed graph represented by an adjacency list where `graph[i]` contains a list of nodes reachable from node `i`, and two integers `startNode` and `targetNode`, find the minimum number of edges required to traverse from `startNode` to `targetNode`. If `targetNode` is unreachable from `startNode`, return -1.
Examples
Example 1:
Input:{"graph":{"0":["1","2"],"1":["3"],"2":["3"],"3":[]},"startNode":"0","targetNode":"3"}
Output:2
Explanation: From node '0', we can go to '1' (1 edge) and then to '3' (1 edge), total 2 edges. Alternatively, from '0' to '2' (1 edge) and then to '3' (1 edge), also 2 edges. The minimum is 2.
Example 2:
Input:{"graph":{"A":["B","C"],"B":["D"],"C":["E"],"D":[],"E":["F"],"F":[]},"startNode":"A","targetNode":"F"}
Output:3
Explanation: The path A -> C -> E -> F requires 3 edges, which is the minimum.
Example 3:
Input:{"graph":{"X":["Y"],"Y":[],"Z":["X"]},"startNode":"Z","targetNode":"Y"}
Output:2
Explanation: The path Z -> X -> Y requires 2 edges.
Constraints
- The number of nodes in the graph is between 0 and 1000.
- The number of edges is between 0 and 5000.
- Node identifiers are strings or integers.
- The graph may contain cycles.
- startNode and targetNode are valid node identifiers present in the graph.
Time: O(V + E) Space: O(V)
The most efficient approach is Breadth-First Search (BFS). BFS explores the graph level by level, guaranteeing that the first time the target node is encountered, it is via the shortest path in terms of the number of edges. We use a queue to manage nodes to visit and a map to store the minimum distance from the start node to each visited node.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from collections import deque
def min_edges_to_reach_target(graph, start_node, target_node):
if start_node == target_node:
return 0
queue = deque([(start_node, 0)]) # (node, distance)
visited = {start_node}
while queue:
current_node, distance = queue.popleft()
if current_node in graph:
for neighbor in graph[current_node]:
if neighbor == target_node:
return distance + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
return -1