拓扑排序验证无向图为有效树的问题排查

问题背景 #

给定一个包含n个节点（标签0到n-1）的无向图，已知整数n和边列表edges，其中edges[i] = [ai, bi]表示节点ai和bi之间存在一条无向边。需要判断该图的边是否构成一棵有效树，是则返回true，否则返回false。

遇到的问题 #

我尝试用拓扑排序算法判断图中是否存在环，但在某个测试用例中，明明图存在环，却输出了完整的拓扑排序序列，导致错误返回true。

我的代码 #

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        indegree = [0]*(n)
        
        graph = {i:[] for i in range(n)}
        
        for child,parent in edges:
            indegree[child]+=1
            graph[parent].append(child)
            
        
        q = deque([])
        
        for i in range(len(indegree)):
            if indegree[i] == 0:
                q.append(i)
                
        top_order = []

        while q:
            node = q.popleft()
            top_order.append(node)
            for child in graph[node]:
                indegree[child]-=1
                if indegree[child]==0:
                    q.append(child)
        print(top_order)    
        return len(top_order)==n

测试用例情况 #

• 输入：n = 5，edges = [[0,1],[0,2],[0,3],[1,4],[1,3]]
• 运行结果：top_order = [2, 3, 4, 1, 0]，返回true，但预期应为false（图中0-1-3-0构成环）

问题原因 #

拓扑排序是针对有向图的算法，你处理无向图时的邻接表和入度统计完全错误：

• 无向边[a,b]等价于双向有向边a→b和b→a，但你只把每条边当成单向的child→parent，导致入度统计严重偏差。比如测试用例中的边[0,3]，你只给3的入度加1，却没给0的入度加1，环中的节点入度没有被正确统计，最终拓扑排序能遍历所有节点，误判无环。

正确解决方案 #

判断无向图是否为有效树，必须同时满足两个条件：无环且所有节点连通（树的边数固定为n-1，先通过这个条件快速过滤不符合的情况）。

方法一：适配无向图的BFS（类拓扑排序思路） #

把无向边当成双向边处理，用父节点记录避免走回头路，同时判断环和连通性：

from collections import deque
from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # 树的边数必须是n-1，直接过滤不符合的情况
        if len(edges) != n - 1:
            return False
        
        # 构建无向邻接表
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        visited = [False] * n
        q = deque([0])
        visited[0] = True
        parent = [-1] * n  # 记录父节点，防止回走
        
        while q:
            node = q.popleft()
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    parent[neighbor] = node
                    q.append(neighbor)
                elif parent[node] != neighbor:
                    # 遇到已访问节点且不是父节点，说明存在环
                    return False
        
        # 检查所有节点是否都被访问（确保连通）
        return all(visited)

方法二：并查集（Union-Find） #

并查集是判断无向图环和连通性的高效方法：

from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        parent = list(range(n))
        
        def find(x):
            # 路径压缩
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            fx, fy = find(x), find(y)
            if fx == fy:
                return False  # 两个节点已连通，存在环
            parent[fy] = fx
            return True
        
        for a, b in edges:
            if not union(a, b):
                return False
        
        return True

内容的提问来源于stack exchange，提问作者ndnchapathi69