如何将已实现的BFS Python代码修改为DFS代码？

Great question! Switching from Breadth-First Search (BFS) to Depth-First Search (DFS) boils down to one core change: swapping the queue (FIFO - First In, First Out) used in BFS for a stack (LIFO - Last In, First Out). Here's a step-by-step breakdown of the modifications you need to make:

Key Modifications #

1. Replace the Queue Class with a Stack Class #

Your MyQUEUE class is built for FIFO behavior. We'll rewrite it as a stack, where we add elements to the end and remove from the end (instead of the start):

class MySTACK:  # Renamed from MyQUEUE for clarity
    def __init__(self):
        self.holder = []
    
    def push(self, val):  # Renamed from enqueue (stack-specific terminology)
        self.holder.append(val)
    
    def pop(self):  # Replaced dequeue with pop to get LIFO behavior
        val = None
        try:
            val = self.holder.pop()  # Pop the LAST element instead of the first
        except:
            pass
        return val
    
    def IsEmpty(self):
        return len(self.holder) == 0  # Simplified the empty check for readability

2. Rewrite the BFS Function to DFS #

The core logic of tracking paths stays almost identical—only the way we retrieve paths from the stack changes. Here's the updated DFS function:

def DFS(graph, start, end):
    s = MySTACK()
    s.push([start])  # Push the initial starting path onto the stack
    
    while not s.IsEmpty():
        path = s.pop()  # Pop the LAST path added (LIFO behavior)
        last_node = path[-1]  # Simplified way to grab the final node in the path
        print(path)
        
        if last_node == end:
            print("VALID_PATH : ", path)
        
        for link_node in graph[last_node]:
            if link_node not in path:
                new_path = path + [link_node]
                s.push(new_path)  # Push new paths onto the stack to explore next

Why This Works #

• BFS explores all nodes at the current depth level before moving to the next, which requires a queue to preserve the order of discovered nodes.
• DFS dives as far down a single path as possible before backtracking. A stack ensures we always pick the most recently discovered path to explore next, enabling this deep-first behavior.

Optional: Simplify with Built-in Python Lists #

You don't even need a custom stack class—Python lists natively support stack operations with append() and pop():

def DFS(graph, start, end):
    stack = [[start]]
    
    while stack:
        path = stack.pop()
        last_node = path[-1]
        print(path)
        
        if last_node == end:
            print("VALID_PATH : ", path)
        
        for link_node in graph[last_node]:
            if link_node not in path:
                new_path = path + [link_node]
                stack.append(new_path)

This version does the exact same thing but cuts out the custom class boilerplate for a cleaner implementation.

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