你有一个从 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)
您当前的代码似乎使用 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
您可以使用子字典的字典来组装树结构,并验证在所有子项都被放置在其父项下后,它最终只有一个根:
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)