Python 中的深度优先搜索

Fariba Laiq 2023年1月30日 2022年5月17日
  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 为空。

Author: 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