如何在Python中使用深度优先搜索算法进行查找

2023-04-16 00:00:00 算法 查找 深度

深度优先搜索算法可以用于图遍历、迷宫问题等，以下是在Python中使用深度优先搜索算法进行查找的示例代码。

假设有一个图的数据如下：

graph = {
        'pidancode.com': ['github.com', 'leetcode.com'],
        'github.com': ['gitlab.com', 'leetcode.com'],
        'leetcode.com': ['hackerrank.com'],
        'hackerrank.com': [],
        'gitlab.com': [],
        '皮蛋编程': ['pidancode.com'],
    }

我们需要用深度优先搜索算法找到从“pidancode.com”开始能够到达哪些节点。具体步骤如下：

  1. 定义一个空集合visited来存储已访问的节点。

  2. 编写一个递归函数dfs，用于遍历当前节点的所有邻居节点。遍历过程中，对于未访问过的邻居节点，将其加入visited中，并递归调用dfs函数继续遍历。

  3. 在主程序中调用dfs函数，从起点开始遍历。

代码示例：

graph = {
        'pidancode.com': ['github.com', 'leetcode.com'],
        'github.com': ['gitlab.com', 'leetcode.com'],
        'leetcode.com': ['hackerrank.com'],
        'hackerrank.com': [],
        'gitlab.com': [],
        '皮蛋编程': ['pidancode.com'],
    }

visited = set()

def dfs(graph, node):
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor)

dfs(graph, 'pidancode.com')

运行结果：

pidancode.com github.com gitlab.com leetcode.com hackerrank.com

这表示从“pidancode.com”开始，可以到达“github.com”、“gitlab.com”、“leetcode.com”、“hackerrank.com”这些节点。

对于字符串范例，我们可以使用类似的方法，将字符串拆分成字符列表来模拟图的数据结构，代码示例如下：

word = '皮蛋编程'

graph = {
    '皮': ['蛋'],
    '蛋': ['编', '程'],
    '编': ['程'],
    '程': [],
}

visited = set()

def dfs(graph, node):
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor)

dfs(graph, word[0])

运行结果：

皮 蛋 编 程

这表示从字母“皮”开始，可以到达所有字母，也就是整个字符串。

相关文章