Python中使用深度优先搜索(DFS)遍历图(Graph)

2023-04-11 00:00:00 遍历 深度 优先

下面是一个使用Python实现DFS遍历图的简单示例代码：

graph = {
    'pidancode.com': ['google.com', 'facebook.com'],
    'google.com': ['pidancode.com', 'microsoft.com'],
    'facebook.com': ['pidancode.com', 'microsoft.com'],
    'microsoft.com': ['google.com', 'facebook.com', 'apple.com'],
    'apple.com': ['microsoft.com']
}

visited = set()

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

dfs('pidancode.com')

这段代码定义了一个简单的图，其中每个节点都代表一个网站，将每个网站和一些相邻网站连接起来，从而构成图。在遍历该图时，使用了深度优先搜索算法（DFS）。深度优先搜索的基本思想是：从起点开始，尽可能深地访问每个节点，直到无法访问为止，然后回溯到上一个节点，继续访问其他未访问的节点，直到所有节点都被访问过为止。

在上述代码中，dfs()函数定义了一个递归算法，用于遍历整个图。在每次调用时，该函数首先检查当前节点是否已经访问过（即是否在visited集合中），如果没有，则输出该节点，并将其添加到visited集合中。然后，该函数遍历与该节点相邻的节点，并递归调用dfs()函数来访问这些节点。这个递归过程重复进行，直到所有节点都被访问为止。

最后，我们调用dfs()函数，并将起点节点（即'pidancode.com'）作为参数传递给它。这将启动整个遍历过程，并输出每个节点的名称，直到所有节点都被访问。

相关文章