如何将基于队列的BFS代码改用栈实现DFS与UCS？

Alright, let's adapt your BFS code to implement Depth-First Search (DFS) using a stack, and Uniform Cost Search (UCS) (which uses a priority queue—think of it as a "smart stack" that prioritizes lower-cost paths). First, let's fix a small readability issue in your original code: using extend(vertex) for single-character nodes works, but append(vertex) is cleaner for tracking paths as lists of nodes.

Depth-First Search (DFS) with Stack #

DFS replaces BFS's FIFO queue behavior with a stack's LIFO (Last-In-First-Out) logic. Instead of pulling from the front of the queue, we pop from the end of the stack to prioritize the most recently added nodes. Here's the modified code:

from collections import deque

graph = {
    'a': set(['b','c']),
    'b': set(['a','d']),
    'c': set(['a','d','f']),
    'd': set(['b','c','e','s']),
    'e': set(['d','h','s','r']),
    'f': set(['G','c','r']),
    'G': set(['f']),
    'h': set(['e','p','q']),
    'p': set(['s','q','h']),
    'q': set(['p','h']),
    'r': set(['e','f']),
    's': set(['d','e','p'])
}

def dfs(graph, start, goal):
    visited = []
    path = []
    # Use a list as a stack (LIFO behavior)
    stack = [start]
    
    while stack:
        # Pop the last element (top of the stack) instead of the first
        vertex = stack.pop()
        
        if vertex not in path:
            path.append(vertex)
            visited.append(vertex)
            # Add neighbors to the stack - reverse if you want matching recursive DFS order
            stack.extend(list(graph[vertex]))
        
        if goal in path:
            return (path, visited)
    
    # Handle unreachable nodes (same logic as original BFS)
    checker = 1
    for a in graph:
        for b in graph[a]:
            checker *= 1 if b in path else 0
        if checker > 0 and a not in visited:
            visited.append(a)
    
    return (path, visited)

# Test DFS
dfs_result = dfs(graph, 's', 'G')
print("DFS Path:", dfs_result[0])
print("DFS Visited Nodes:", dfs_result[1])

Key Changes: #

• Replaced the deque queue with a standard list acting as a stack
• Swapped queue.popleft() with stack.pop() to get the most recent node
• Used append() instead of extend() for path/visited lists to keep node entries intact
• Note: If you want the traversal order to match a recursive DFS, reverse the neighbor list before adding to the stack (e.g., stack.extend(reversed(list(graph[vertex])))).

Uniform Cost Search (UCS) #

UCS isn't a simple stack swap—it requires prioritizing nodes by the cumulative cost to reach them. We'll use a priority queue (implemented with heapq) instead of a basic stack, since we always need to select the node with the lowest current cost. We'll also track path costs explicitly:

import heapq

# Updated graph with edge costs (we'll use 1 for all edges here, but UCS works with any weights)
graph_with_costs = {
    'a': {'b': 1, 'c': 1},
    'b': {'a': 1, 'd': 1},
    'c': {'a': 1, 'd': 1, 'f': 1},
    'd': {'b': 1, 'c': 1, 'e': 1, 's': 1},
    'e': {'d': 1, 'h': 1, 's': 1, 'r': 1},
    'f': {'G': 1, 'c': 1, 'r': 1},
    'G': {'f': 1},
    'h': {'e': 1, 'p': 1, 'q': 1},
    'p': {'s': 1, 'q': 1, 'h': 1},
    'q': {'p': 1, 'h': 1},
    'r': {'e': 1, 'f': 1},
    's': {'d': 1, 'e': 1, 'p': 1}
}

def ucs(graph, start, goal):
    # Priority queue stores tuples: (total_cost, current_node, path_taken)
    priority_queue = []
    heapq.heappush(priority_queue, (0, start, [start]))
    visited = set()
    
    while priority_queue:
        current_cost, vertex, path = heapq.heappop(priority_queue)
        
        # If we've reached the goal, return results immediately
        if vertex == goal:
            return (path, list(visited), current_cost)
        
        if vertex not in visited:
            visited.add(vertex)
            # Explore all neighbors and push them to the queue with updated cost
            for neighbor, edge_cost in graph[vertex].items():
                if neighbor not in visited:
                    new_total_cost = current_cost + edge_cost
                    new_path = path + [neighbor]
                    heapq.heappush(priority_queue, (new_total_cost, neighbor, new_path))
    
    # If goal is unreachable
    return (None, list(visited), float('inf'))

# Test UCS
ucs_result = ucs(graph_with_costs, 's', 'G')
print("UCS Path:", ucs_result[0])
print("UCS Visited Nodes:", ucs_result[1])
print("Total Cost to Goal:", ucs_result[2])

Key Changes: #

• Switched to a weighted graph to demonstrate UCS's cost-handling (if all costs are 1, UCS behaves exactly like BFS)
• Used heapq to implement a priority queue that always selects the cheapest path first
• Tracked cumulative cost and full path for each node in the queue
• Used a visited set to avoid reprocessing nodes via more expensive paths

内容的提问来源于stack exchange，提问作者Sheikh Muhammad Umar