基于Java的BFS路径查找：修改代码用Stack打印0到3的途经节点

Hey there! Let's tweak your BFS code to track the path from node 0 to node 3 using a stack. The core idea is to first use BFS to record each node's parent (the node we came from), then backtrack from the end node to the start, push those nodes into a stack, and finally pop them to get the forward path.

Key Changes Needed #

• Parent Tracking: We'll use a dictionary (or array) to keep track of each node's predecessor. This lets us trace our way back from the end to the start.
• Stack for Path: Since backtracking gives us the path in reverse order (end → start), pushing these nodes to a stack and popping them will give us the correct start → end sequence.
• Early Termination: Stop BFS as soon as we reach the end node to save computation.

Modified Code Example #

Here's a complete implementation using an adjacency list for the graph:

from collections import deque

def bfs_track_path_with_stack(graph, start, end):
    # Initialize BFS queue with the start node
    queue = deque([start])
    # Dictionary to store each node's parent (for path tracing)
    parent_map = {node: None for node in graph}
    visited = set([start])
    
    # Run BFS until queue is empty or we find the end node
    while queue:
        current = queue.popleft()
        
        # Exit early once we reach the target node
        if current == end:
            break
        
        # Explore all unvisited neighbors
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent_map[neighbor] = current
                queue.append(neighbor)
    
    # Handle case where no path exists
    if parent_map[end] is None and start != end:
        print(f"No path exists from node {start} to node {end}")
        return
    
    # Backtrack from end to start and push nodes to stack
    path_stack = []
    current_node = end
    while current_node is not None:
        path_stack.append(current_node)
        current_node = parent_map[current_node]
    
    # Print the path by popping from the stack (gives start → end order)
    print("Path from start to end (via stack):")
    while path_stack:
        node = path_stack.pop()
        # Add arrow except for the last node
        print(node, end=" -> " if path_stack else "\n")

# Example graph (adjust this to match your actual graph structure)
sample_graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# Execute the function
bfs_track_path_with_stack(sample_graph, 0, 3)

How It Works #

1. BFS Traversal: We start at node 0, mark nodes as visited, and record each neighbor's parent before adding them to the queue.
2. Path Backtracking: Once we hit node 3, we start from 3 and follow the parent_map back to 0, pushing each node into the stack.
3. Stack Output: Popping from the stack reverses the backtracked path, giving us the correct sequence from 0 to 3 (e.g., 0 -> 1 -> 3 or 0 -> 2 -> 3, depending on BFS order).

Notes #

• If your graph uses a different representation (like an adjacency matrix), you can adjust the neighbor exploration part accordingly.
• The code includes a check for missing paths—if there's no way to reach node 3 from 0, it will print a clear message.

内容的提问来源于stack exchange，提问作者Waseem Awashra