Python中使用DFS判断图(Graph)是否为森林(Forest)

2023-04-11 00:00:00 判断森林 DFS

首先，我们需要定义一个图的数据结构，这里我们可以使用邻接表来表示图。

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = {v: [] for v in vertices}

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

然后，我们可以定义一个 DFS 函数来遍历图，并判断它是否为森林。同时，我们需要记录哪些节点已经被访问过，以避免重复遍历。

def is_forest(graph):
    visited = {v: False for v in graph.vertices}

    def dfs(node, parent):
        visited[node] = True

        for neighbor in graph.adj_list[node]:
            if not visited[neighbor]:
                if not dfs(neighbor, node):
                    return False
            elif neighbor != parent:
                return False

        return True

    for node in graph.vertices:
        if not visited[node]:
            if not dfs(node, None):
                return False

    return True

这里的 DFS 函数中，我们使用了递归的方式进行遍历。具体来说，我们首先将当前节点标记为已访问，并依次遍历与之相邻的节点。如果某个相邻节点未被访问过，则递归调用 DFS 函数进行遍历，并检查返回值。如果返回值为 False，则说明发现了一条环路，因此整个图不是森林，直接返回 False。否则，如果某个相邻节点已经被访问过，并且不是当前节点的父节点，则说明存在两个不同的节点到达了同一个相邻节点，这也说明整个图不是森林，直接返回 False。最后，如果整个图都遍历完成而没有返回 False，则说明它是森林，返回 True。

我们可以使用以下代码来测试这个函数：

vertices = ['p', 'i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', 'm']
edges = [('p', 'i'), ('i', 'd'), ('i', 'c'), ('a', 'n'), ('n', 'd'), ('o', 'd')]

graph = Graph(vertices)
for u, v in edges:
    graph.add_edge(u, v)

print(is_forest(graph))  # True

graph.add_edge('p', 'c')
print(is_forest(graph))  # False

这里我们建立了一个包含 9 个节点和 6 条边的森林，执行后输出 True。然后我们添加了一条新的边 'p' -> 'c'，这样就会形成一个环路，执行后输出 False。

相关文章