尝试使用拓扑排序算法来判断一棵树是否有效

Question

你有一个从 0 到 n - 1 标记的 n 个节点的图。给定一个整数 n 和一个边列表，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间存在无向边在图中。

如果给定图的边构成一棵有效的树，则返回 true，否则返回 false。

我之前使用过拓扑排序，基本上我尝试打印出图的拓扑排序并确定是否存在循环。在第二个例子中有一个循环，但是，我仍然能够按拓扑顺序打印它（见下文）：

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

Test Case: n = 5, edges = [[0,1],[0,2],[0,3],[1,4],[1,3]]

Result: top_order = [2, 3, 4, 1, 0] (returning true, but i'm expecting false)

Answer 1

您当前的代码似乎使用 BFS 实现拓扑排序，这是确定有向图是否为有效 DAG（有向无环图）的有效方法。但是，给定的问题陈述要求确定给定的图是否是有效的树，这有一些额外的约束：

• 树是无向图，意味着每条边都是双向的，而目前的实现只考虑有向边。

• 树是连通图，而当前的实现不检查连通性。

• 树是无环图，而当前的实现不检查循环。

因此，您当前的代码没有解决给定问题陈述的所有要求，并且它可能无法为某些测试用例产生正确的结果。

但是下面的代码应该可以工作：

from typing import List

class Solution:
    def validTree(n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n-1:
            return False
        
        # Build adjacency list
        adj_list = {i: [] for i in range(n)}
        for u, v in edges:
            adj_list[u].append(v)
            adj_list[v].append(u)
        
        # Check if the graph is connected using DFS
        visited = set()
        stack = [0]
        while stack:
            node = stack.pop()
            visited.add(node)
            for neighbor in adj_list[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
        if len(visited) != n:
            return False
        
        # Check if the graph has no cycles using DFS
        def has_cycle(node, parent):
            visited.add(node)
            for neighbor in adj_list[node]:
                if neighbor != parent:
                    if neighbor in visited or has_cycle(neighbor, node):
                        return True
            return False
        
        visited = set()
        if has_cycle(0, -1):
            return False
        
        return True

Answer 2

您可以使用子字典的字典来组装树结构，并验证在所有子项都被放置在其父项下后，它最终只有一个根：

def validTree(edges):
    tree = { v:{} for ab in edges for v in ab}
    for k,v in reversed(edges):
        try:    tree[k][v] = tree.pop(v)  # move node under its parent
        except: return False              # if child referenced more than once
    return len(tree) == 1                 # collapsed tree only has one root

输出：

print(validTree([[0,1],[0,2],[0,3],[1,4],[1,3]])) # False

print(validTree([[0,1],[0,2],[0,3],[1,4],[1,5]])) # True

注意：边缘循环假定它们处于正确的引用顺序（父母在被引用为孩子之前出现）。如果没有，请使用

for k,v in sorted(edges,reverse=True)