Python栈的应用：DFS算法的实现

2023-04-11 00:00:00 python 算法 DFS

DFS算法是一种常见的图遍历算法，其基本思想是从一条路走到底，再返回来走另一条路。这种算法可以通过栈来实现。

具体实现过程如下：

  1. 创建一个栈，将起点节点压入栈中，并标记起点节点已经被访问过。

  2. 当栈不为空时，从栈顶取出一个节点，检查是否是终点节点。如果是，则返回结果。如果不是，则将其所有未被访问过的相邻节点都压入栈中，并标记它们已经被访问过。

  3. 重复步骤2，直到找到终点节点或栈为空。

下面是Python代码的实现，以字符串“pidancode.com”作为示例：

visited = set()  # 用集合记录已访问的节点
stack = ['p']    # 创建一个栈，并将起点 'p' 压入栈中
destination = 'c' # 终点为 'c'

# 这里使用邻接表来存储图中的节点和它们的相邻节点
graph = {
    'p': ['i', 'd'], 
    'i': ['d', 'a', 'n'], 
    'd': ['a', 'n', 'o', 'e'], 
    'a': ['n'], 
    'n': ['c', 'o', 'd'], 
    'c': [], 
    'o': ['d', 'e'], 
    'e': ['d', 'o']
}

while stack:
    node = stack.pop()  # 取出栈顶节点
    visited.add(node)  # 标记节点已被访问
    if node == destination:  # 判断是否为终点
        print('Found destination:', node)
        break
    for neighbor in graph[node]:  # 遍历相邻节点
        if neighbor not in visited:  # 如果未被访问过
            stack.append(neighbor)  # 将其压入栈中

运行结果：

Found destination: c

从结果可以看出，我们成功地利用栈实现了DFS算法，找到了起点 'p' 到终点 'c' 的一条路径。

相关文章