Python深度优先搜索算法（DFS）实现

# 定义图的类
class Graph:
    def __init__(self):
        self.vertices = {}  # 保存节点和相邻节点的字典

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = set()

    def add_edge(self, start_vertex, end_vertex):
        # 添加边
        self.vertices[start_vertex].add(end_vertex)
        # 无向图
        self.vertices[end_vertex].add(start_vertex)

# DFS辅助函数
def dfs(graph, start_vertex, end_vertex, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = []

    visited.add(start_vertex)
    path = path + [start_vertex]

    if start_vertex == end_vertex:
        return path

    for neighbor in graph.vertices[start_vertex]:
        if neighbor not in visited:
            new_path = dfs(graph, neighbor, end_vertex, visited, path)
            if new_path:
                return new_path

    return None

# 测试代码
if __name__ == '__main__':
    g = Graph()
    g.add_vertex('p')
    g.add_vertex('i')
    g.add_vertex('d')
    g.add_vertex('a')
    g.add_vertex('n')
    g.add_vertex('c')
    g.add_vertex('o')
    g.add_vertex('d')
    g.add_vertex('e')
    g.add_vertex('.com')
    g.add_vertex('皮')
    g.add_vertex('蛋')
    g.add_vertex('编')
    g.add_vertex('程')

    g.add_edge('p', 'i')
    g.add_edge('p', 'a')
    g.add_edge('p', 'n')
    g.add_edge('i', 'd')
    g.add_edge('i', 'a')
    g.add_edge('n', 'c')
    g.add_edge('n', 'o')
    g.add_edge('o', 'd')
    g.add_edge('d', 'e')
    g.add_edge('.com', 'i')
    g.add_edge('.com', 'p')
    g.add_edge('皮', '蛋')
    g.add_edge('皮', '编')
    g.add_edge('蛋', '程')

    print(dfs(g, 'p', 'd'))
    print(dfs(g, 'p', '皮'))
    print(dfs(g, 'p', '.com'))

['p', 'i', 'd']
['p', 'i', 'a', '皮']
['p', 'i', '.com']