dfs递归实现python

下面是 Python 中 DFS 递归实现的示例代码：

# 定义一个图的邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# DFS 递归实现
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

其中 `graph` 是一个字典，表示图的邻接表；`start` 是起始节点；`visited` 是一个集合，用于记录已经访问过的节点。首先将起始节点加入 `visited` 集合中，并输出该节点。然后遍历该节点的所有邻居节点，如果邻居节点没有被访问过，则递归调用 `dfs` 函数，将该邻居节点作为起始节点，同时将 `visited` 集合传递下去。这样就可以实现 DFS 的递归实现。

相关问题

python dfs递归实现迷宫问题

好的，下面是 Python 中 DFS 递归实现迷宫问题的代码示例：

# 定义迷宫地图，0 表示可走，1 表示障碍物
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
]

# 定义迷宫大小
n = len(maze)
m = len(maze[0])

# 定义标记数组，标记每个位置是否已经访问过
visited = [[False] * m for _ in range(n)]

# 定义终点位置
end = (4, 3)

# 定义方向数组，表示上下左右四个方向
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def dfs(x, y):
    # 如果当前位置就是终点位置，则直接返回 True
    if (x, y) == end:
        return True
    
    # 标记当前位置已经访问过
    visited[x][y] = True
    
    # 枚举四个方向
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        
        # 判断是否越界，是否已经访问过，是否是障碍物
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and maze[nx][ny] == 0:
            # 递归搜索下一个位置
            if dfs(nx, ny):
                return True
    
    # 如果四个方向都没找到终点，则返回 False
    return False


# 在起点位置开始搜索
start = (0, 0)
if dfs(start[0], start[1]):
    print("可以到达终点！")
else:
    print("无法到达终点！")

这段代码中，我们先定义了一个迷宫地图 `maze`，然后定义了迷宫的大小 `n` 和 `m`，以及标记数组 `visited` 和终点位置 `end`。

接着，我们定义了一个 DFS 函数 `dfs`，它的参数是当前位置的坐标 `(x, y)`，表示从这个位置开始搜索。

在 `dfs` 函数中，我们首先判断当前位置是否是终点位置，如果是，则直接返回 True。

然后，我们标记当前位置已经访问过，并枚举当前位置可以走的四个方向。对于每个方向，我们判断是否可以走，如果可以，则递归搜索下一个位置。如果在四个方向中找到了终点位置，则返回 True。

最后，在主函数中，我们从起点位置开始搜索，如果可以到达终点，则输出“可以到达终点！”；否则输出“无法到达终点！”。

Dfs算法的递归实现

以下是DFS算法的递归实现：

# 定义一个图的类
class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    # 添加节点
    def add_node(self, node):
        if node not in self.__graph_dict:
            self.__graph_dict[node] = []

    # 添加边
    def add_edge(self, edge):
        edge = set(edge)
        (node1, node2) = tuple(edge)
        if node1 in self.__graph_dict:
            self.__graph_dict[node1].append(node2)
        else:
            self.__graph_dict[node1] = [node2]

    # DFS算法的递归实现
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start)
        for next_node in self.__graph_dict[start]:
            if next_node not in visited:
                self.dfs(next_node, visited)
        return visited

# 创建一个图
graph = Graph()

# 添加节点
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')
graph.add_node('D')
graph.add_node('E')
graph.add_node('F')

# 添加边
graph.add_edge(('A', 'B'))
graph.add_edge(('A', 'C'))
graph.add_edge(('B', 'D'))
graph.add_edge(('B', 'E'))
graph.add_edge(('C', 'F'))

# 执行DFS算法
graph.dfs('A')