通俗的讲解DFS算法（深度优先搜索）附代码示例_dfs深度优先遍历算法代码理解

深度优先搜索（Depth-First Search，简称DFS）是一种用于图形和树结构的遍历算法。该算法从起始节点开始，沿着一条路径尽可能深入地探索，直到无法继续或达到目标节点为止。如果遇到无法继续前进的节点，算法会回溯到上一个节点，然后探索其他路径。

DFS的过程可以用递归或栈来实现。下面是一个通俗的解释DFS的过程：

假设我们有一个迷宫，目标是从起始点找到迷宫的出口。我们可以使用DFS来解决这个问题。

1. 选择一个起始点作为当前位置。
2. 检查当前位置是否是目标位置，如果是，则找到了解决方案，算法结束。
3. 如果当前位置不是目标位置，我们将标记当前位置为已访问，并且探索与当前位置相邻的未访问过的节点。
4. 选择一个未访问过的相邻节点，将其作为新的当前位置，并重复步骤2-3。
5. 如果没有未访问的相邻节点，我们回溯到上一个节点，即退回到上一步选择的节点，并且选择另一个未访问过的相邻节点继续探索。
6. 重复步骤2-5，直到找到目标位置或者无法继续前进（即所有的节点都已访问）。

通过这种方式，DFS会尽可能沿着一条路径一直向下探索，直到无法继续为止，然后回溯并尝试其他路径。以下给出代码示例来计算深度优先搜索算法在给定图结构中从指定起始节点开始的遍历，并返回遍历结果。

Graph={
    'A':['B','C'],
    'B':['D','C','A'],
    'C':['A','B','D','E'],
    'D':['B','C','E','F'],
    'E':['D','C'],
    'F':['D']
}
 
def DFS(Graph, start):
    '''
    :param Graph: 图结构
    :param start: 开始结点
    :return: DFS遍历结果
    '''
    stack = []  # 创建一个空栈
    stack.append(start)  # 将起始结点压入栈中
    seen = []  # 创建一个空列表，用于记录已访问的结点
    result = []  # 创建一个空列表，用于存储DFS遍历结果
    seen.append(start)  # 标记起始结点为已访问
    while len(stack) > 0:  # 当栈不为空时循环
        vex = stack.pop()  # 弹出栈顶结点
        result.append(vex)  # 将弹出的结点添加到结果列表中
        for node in Graph[vex]:  # 遍历弹出结点的邻接结点
            if node not in seen:  # 检查邻接结点是否已被访问过
                stack.append(node)  # 将未访问过的邻接结点压入栈中
                seen.append(node)  # 标记邻接结点为已访问
    return result  # 返回DFS遍历结果
result = DFS(Graph, 'D')  # 调用DFS函数，传入图结构和起始结点
print(result)  # 打印DFS遍历结果
'
运行
运行