Python 中的深度优先搜索

  1. 在 Python 中使用 Graph 的深度优先搜索示例
  2. 在 Python 中使用递归进行深度优先搜索
  3. 在 Python 中使用迭代进行深度优先搜索
Python 中的深度优先搜索

深度优先搜索是一种遍历的算法。在 DFS 中,遍历从根节点开始,越走越深。

当它到达叶节点时,它会执行回溯并向上。

深度优先搜索用于许多应用程序,例如:

  • 检测图中的循环
  • Path Finding
  • 旅行推销员问题

在 Python 中使用 Graph 的深度优先搜索示例

我们有六个顶点,1 是根顶点。我们将遍历 1,然后它有两个相邻的顶点 5 和 9,所以首先我们将遍历它的左顶点,然后我们将遍历 5 的相邻顶点。

当找到叶节点时,我们将回溯并重复相同的过程到最近未访问的节点。

Python 中的深度优先搜索

在这个例子中,绿色顶点是遍历的顶点,而红色是尚未遍历的顶点。

在 Python 中使用递归进行深度优先搜索

recursion 技术调用 DFS 函数。遍历所有图的顶点时,基本条件为

以下代码使用字典数据结构来表示邻接列表以将图形存储在内存中。

我们将声明一个集合来跟踪我们访问过的所有顶点。

如果顶点没有被遍历,我们首先通过打印它并将其添加到遍历集中来遍历它。

# Python 3.x
graph = {"1": ["5", "9"], "5": ["2", "4"], "9": ["8"], "2": ["4"], "4": ["2"], "8": []}
traversed = set()


def dfs(traversed, graph, vertex):
    if vertex not in traversed:
        print(vertex)
        traversed.add(vertex)
        for adjacent in graph[vertex]:
            dfs(traversed, graph, adjacent)


print("Depth First Search:")
dfs(traversed, graph, "1")

输出:

# python 3.x
Depth First Search:
1
5
2
4
9
8

我们必须通过遍历图的相邻顶点并执行 DFS 来越来越深入。

我们回溯,访问了最近未访问的顶点,并为该顶点执行了 DFS。

在驱动程序代码中,我们必须调用 dfs 函数并指定根顶点,在我们的例子中是 1

在 Python 中使用迭代进行深度优先搜索

使用循环遍历图的顶点。我们还将使用 stack 来跟踪 unvisited 顶点。

首先,我们将遍历根节点并将其推入堆栈。然后,当我们的堆栈不为空时,我们将从堆栈中窥视(读取最顶层的顶点而不删除它)一个顶点,如果没有遍历该顶点,我们将遍历它。

然后我们将读取刚刚遍历过的顶点的 adjacent vertex,如果我们之前没有遍历过它,将它压入堆栈。

# Python 3.x
def dfs(graph, root_node):
    traversed = [root_node]
    stack = [root_node]
    while stack:
        vertex = stack[-1]
        if vertex not in traversed:
            traversed.extend(vertex)
        pop = True
        for adjacent in graph[vertex]:
            if adjacent not in traversed:
                stack.extend(adjacent)
                pop = False
                break
        if pop:
            stack.pop()
    return traversed


graph = {"1": ["5", "9"], "5": ["2", "4"], "9": ["8"], "2": ["4"], "4": ["2"], "8": []}
print(dfs(graph, "1"))

输出:

#python 3.x
['1', '5', '2', '4', '9', '8']

我们必须越走越深,到达没有相邻顶点的叶节点。我们从 stack 中弹出 leaf nodes,因为不会执行 DFS,我们已经遍历了它。

所以,for 循环并没有被执行。我们将回溯。

控制再次进入 while 循环,并为堆栈的 peek 元素执行 DFS,直到 stack 为空。

Enjoying our tutorials? Subscribe to DelftStack on YouTube to support us in creating more high-quality video guides. Subscribe
作者: Fariba Laiq
Fariba Laiq avatar Fariba Laiq avatar

I am Fariba Laiq from Pakistan. An android app developer, technical content writer, and coding instructor. Writing has always been one of my passions. I love to learn, implement and convey my knowledge to others.

LinkedIn

相关文章 - Python Algorithm