python划分不同连通域

在 Python 中，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来划分不同的连通域。

以下是一个使用 DFS 算法来划分连通域的示例代码：

def dfs(graph, visited, node, component):
    visited[node] = True
    component.append(node)
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, visited, neighbor, component)

def find_components(graph):
    components = []
    visited = {node: False for node in graph.keys()}
    for node in graph.keys():
        if not visited[node]:
            component = []
            dfs(graph, visited, node, component)
            components.append(component)
    return components

其中，`graph` 是一个字典，其中键是节点，值是该节点的所有邻居节点。`visited` 是一个字典，用于记录每个节点是否被访问过。`node` 是当前正在访问的节点。`component` 是当前正在构建的连通域。

`dfs` 函数使用递归来遍历图中的节点。它首先将当前节点标记为已访问，并将其添加到连通域中。然后，它遍历当前节点的所有未访问邻居节点，并对每个邻居节点递归调用 `dfs` 函数。

`find_components` 函数遍历图中的所有节点，对于每个未访问的节点，它调用 `dfs` 函数来构建一个连通域。最终，该函数返回一个列表，其中包含所有连通域的列表。

例如，假设有以下图：

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B'],
    'D': ['B', 'E'],
    'E': ['D']
}

调用 `find_components(graph)` 将返回以下列表：

[
    ['A', 'B', 'C'],
    ['D', 'E']
]

这表示该图包含两个连通域，一个包含节点 `A`、`B` 和 `C`，另一个包含节点 `D` 和 `E`。