给定的图是一棵树吗？比下面的方法更快 -
Is the given Graph a tree? Faster than below approach -
我在面试中被问到一个问题，虽然最后我的回答被接受了，但他们想要一个更快的方法，而我一片空白..
问题：
给定一个无向图，你能看出它是不是一棵树吗？如果是，return 为真，否则为假。
一棵树：
A - B
|
C - D
不是树：
A
/ \
B - C
/
D
您将获得两个参数：n 表示节点数，以及多维边数组，例如：[[1, 2], [2, 3]]，每对代表由边缘.
注意：预期 space 复杂度：O(|V|)
数组边可以为空
这是我的代码：105ms
def is_graph_tree(n, edges):
nodes = [None] * (n + 1)
for i in range(1, n+1):
nodes[i] = i
for i in range(len(edges)):
start_edge = edges[i][0]
dest_edge = edges[i][1]
if nodes[start_edge] != start_edge:
start_edge = nodes[start_edge]
if nodes[dest_edge] != dest_edge:
dest_edge = nodes[dest_edge]
if start_edge == dest_edge:
return False
nodes[start_edge] = dest_edge
return len(edges) <= n - 1
你甚至不需要知道有多少条边：
def is_graph_tree(n, edges):
seen = set()
for a,b in edges:
b = max(a,b)
if b in seen:
return False
seen.add(b)
return True
a = [[1,2],[2,3],[3,4]]
print(is_graph_tree(0,a))
b = [[1,2],[1,3],[2,3],[2,4]]
print(is_graph_tree(0,b))
现在，这不会捕获断开连接的子树的情况，但这不在问题描述中...
Tim Roberts 发布了一个候选解决方案，但这适用于断开连接的子树的情况：
import queue
def is_graph_tree(n, edges):
# A tree with n nodes has n - 1 edges.
if len(edges) != n - 1:
return False
# Construct graph.
graph = [[] for _ in range(n)]
for first_vertex, second_vertex in edges:
graph[first_vertex].append(second_vertex)
graph[second_vertex].append(first_vertex)
# BFS to find edges that create cycles.
# The graph is undirected, so we can root the tree wherever we want.
visited = set()
q = queue.Queue()
q.put((0, None))
while not q.empty():
current_node, previous_node = q.get()
if current_node in visited:
return False
visited.add(current_node)
for neighbor in graph[current_node]:
if neighbor != previous_node:
q.put((neighbor, current_node))
# Only return true if the graph has only one connected component.
return len(visited) == n
这会在 O(n + len(edges)) 时间内运行。
你可以从树叶的角度来看待这个问题。树中的每个叶节点都只有一条边与之相连。因此，如果您计算每个节点的边数，您可以获得叶子列表（即只有一个边的叶子）。
然后，从这些叶子中取出 linked 节点并将它们的边数减少一个（就好像您要从树中删除所有叶子一样。这将为您提供一组新的叶子对应于parents 个原始叶子。重复此过程，直到没有更多叶子。
[EDIT] 检查边缘数是否为 N-1 消除了进行 multi-root 检查的需要，因为还会有另一个差异（例如双 link，图中缺少节点）如果有多个 'roots' 或断开的子树
如果图是一棵树，这个过程应该从节点计数中消除所有节点（即它们将在某个点被标记为叶子）。
使用计数器 class（来自集合）将使这相对容易实现：
from collections import Counter
def isTree(N,E):
if N==1 and not E: return True # root only is a tree
if len(E) != N-1: return False # a tree has N-1 edges
counts = Counter(n for ab in E for n in ab) # edge counts per node
if len(counts) != N : return False # unlinked nodes
while True:
leaves = {n for n,c in counts.items() if c==1} # new leaves
if not leaves:break
for a,b in E: # subtract leaf counts
if counts[a]>1 and b in leaves: counts[a] -= 1
if counts[b]>1 and a in leaves: counts[b] -= 1
for n in leaves: counts[n] = -1 # flag leaves in counts
return all(c==-1 for c in counts.values()) # all must become leaves
输出：
G = [[1,2],[1,3],[4,5],[4,6]]
print(isTree(6,G)) # False (disconnected sub-tree)
G = [[1,2],[1,3],[1,4],[2,3],[5,6]]
print(isTree(6,G)) # False (doubly linked node 3)
G = [[1,2],[2,6],[3,4],[5,1],[2,3]]
print(isTree(6,G)) # True
G = [[1,2],[2,3]]
print(isTree(3,G)) # True
G = [[1,2],[2,3],[3,4]]
print(isTree(4,G)) # True
G = [[1,2],[1,3],[2,5],[2,4]]
print(isTree(6,G)) # False (missing node)
Space 复杂度为 O(N)，因为计数字典的每个节点（顶点）都有一个条目，其中一个整数作为值。时间复杂度为 O(ExL)，其中 E 是边数，L 是树中的层数。对于所有 parents 只有一个 child 节点的树，麦芽汁情况时间为 O(E^2)。然而，由于初始条件是 E 小于 V，最坏的情况实际上是 O(V^2)
请注意，此算法不假设边顺序或节点编号之间的数值关系。此算法找到的根（最后一个节点成为叶子）不一定是唯一可能的根，除非节点具有隐式基数关系（或边具有顺序），否则可能存在模棱两可的情况：
[1,2],[2,3],[2,4] could be:
1 2 3
|_2 OR |_1 OR |_2
|_3 |_3 |_1
|_4 |_4 |_4
如果可以依赖节点编号之间的基数关系或边的顺序，则算法可能会更高效（因为我们可以轻松确定哪个节点是根节点并从那里）。
[EDIT2] 使用组的替代方法。
当边数为N-1时，如果图是树，则所有节点都应该可以从任何其他节点到达。这意味着，如果我们为每个节点形成一组可达节点，并根据边将它们合并在一起，那么在遍历所有边后，我们应该最终得到一个组。
这是基于该方法修改后的函数：
def isTree(N,E):
if N==1 and not E: return True # root only is a tree
if len(E) != N-1: return False # a tree has N-1 edges
groups = {n:[n] for ab in E for n in ab} # each node in its own group
if len(groups) != N : return False # unlinked nodes
for a,b in E:
groups[a].extend(groups[b]) # merge groups
for n in groups[b]: groups[n] = groups[a] # update nodes' groups
return len(set(map(id,groups.values()))) == 1 # only one group when done
鉴于我们开始时边数少于节点数，并且组合并最多消耗组大小的 2 倍（因此也 < N），space 复杂度将保持为 O(五）。对于麦芽汁情况
，时间复杂度也将是 O(V^2)
这是一种使用不相交集合联合/联合查找数据结构的方法：
def is_graph_tree(n, edges):
parent = list(range(n+1))
size = [1] * (n + 1)
for x, y in edges:
# find x (path splitting)
while parent[x] != x:
x, parent[x] = parent[x], parent[parent[x]]
# find y
while parent[y] != y:
y, parent[y] = parent[y], parent[parent[y]]
if x == y:
# Already connected
return False
# Union (by size)
if size[x] < size[y]:
x, y = y, x
parent[y] = x
size[x] += size[y]
return True
assert not is_graph_tree(4, [(1, 2), (2, 3), (3, 4), (4, 2)])
assert is_graph_tree(6, [(1, 2), (2, 3), (3, 4), (3, 5), (1, 6)])
运行时间是O(V + E*InverseAckermannFunction(V))，比O(V + E * log(log V))好，所以基本上是O(V + E)。
我在面试中被问到一个问题，虽然最后我的回答被接受了，但他们想要一个更快的方法，而我一片空白..
问题：
给定一个无向图，你能看出它是不是一棵树吗？如果是，return 为真，否则为假。
一棵树：
A - B
|
C - D
不是树：
A
/ \
B - C
/
D
您将获得两个参数：n 表示节点数，以及多维边数组，例如：[[1, 2], [2, 3]]，每对代表由边缘.
注意：预期 space 复杂度：O(|V|) 数组边可以为空
这是我的代码：105ms
def is_graph_tree(n, edges):
nodes = [None] * (n + 1)
for i in range(1, n+1):
nodes[i] = i
for i in range(len(edges)):
start_edge = edges[i][0]
dest_edge = edges[i][1]
if nodes[start_edge] != start_edge:
start_edge = nodes[start_edge]
if nodes[dest_edge] != dest_edge:
dest_edge = nodes[dest_edge]
if start_edge == dest_edge:
return False
nodes[start_edge] = dest_edge
return len(edges) <= n - 1
你甚至不需要知道有多少条边：
def is_graph_tree(n, edges):
seen = set()
for a,b in edges:
b = max(a,b)
if b in seen:
return False
seen.add(b)
return True
a = [[1,2],[2,3],[3,4]]
print(is_graph_tree(0,a))
b = [[1,2],[1,3],[2,3],[2,4]]
print(is_graph_tree(0,b))
现在，这不会捕获断开连接的子树的情况，但这不在问题描述中...
Tim Roberts 发布了一个候选解决方案，但这适用于断开连接的子树的情况：
import queue
def is_graph_tree(n, edges):
# A tree with n nodes has n - 1 edges.
if len(edges) != n - 1:
return False
# Construct graph.
graph = [[] for _ in range(n)]
for first_vertex, second_vertex in edges:
graph[first_vertex].append(second_vertex)
graph[second_vertex].append(first_vertex)
# BFS to find edges that create cycles.
# The graph is undirected, so we can root the tree wherever we want.
visited = set()
q = queue.Queue()
q.put((0, None))
while not q.empty():
current_node, previous_node = q.get()
if current_node in visited:
return False
visited.add(current_node)
for neighbor in graph[current_node]:
if neighbor != previous_node:
q.put((neighbor, current_node))
# Only return true if the graph has only one connected component.
return len(visited) == n
这会在 O(n + len(edges)) 时间内运行。
你可以从树叶的角度来看待这个问题。树中的每个叶节点都只有一条边与之相连。因此，如果您计算每个节点的边数，您可以获得叶子列表（即只有一个边的叶子）。
然后，从这些叶子中取出 linked 节点并将它们的边数减少一个（就好像您要从树中删除所有叶子一样。这将为您提供一组新的叶子对应于parents 个原始叶子。重复此过程，直到没有更多叶子。
[EDIT] 检查边缘数是否为 N-1 消除了进行 multi-root 检查的需要，因为还会有另一个差异（例如双 link，图中缺少节点）如果有多个 'roots' 或断开的子树
如果图是一棵树，这个过程应该从节点计数中消除所有节点（即它们将在某个点被标记为叶子）。
使用计数器 class（来自集合）将使这相对容易实现：
from collections import Counter
def isTree(N,E):
if N==1 and not E: return True # root only is a tree
if len(E) != N-1: return False # a tree has N-1 edges
counts = Counter(n for ab in E for n in ab) # edge counts per node
if len(counts) != N : return False # unlinked nodes
while True:
leaves = {n for n,c in counts.items() if c==1} # new leaves
if not leaves:break
for a,b in E: # subtract leaf counts
if counts[a]>1 and b in leaves: counts[a] -= 1
if counts[b]>1 and a in leaves: counts[b] -= 1
for n in leaves: counts[n] = -1 # flag leaves in counts
return all(c==-1 for c in counts.values()) # all must become leaves
输出：
G = [[1,2],[1,3],[4,5],[4,6]]
print(isTree(6,G)) # False (disconnected sub-tree)
G = [[1,2],[1,3],[1,4],[2,3],[5,6]]
print(isTree(6,G)) # False (doubly linked node 3)
G = [[1,2],[2,6],[3,4],[5,1],[2,3]]
print(isTree(6,G)) # True
G = [[1,2],[2,3]]
print(isTree(3,G)) # True
G = [[1,2],[2,3],[3,4]]
print(isTree(4,G)) # True
G = [[1,2],[1,3],[2,5],[2,4]]
print(isTree(6,G)) # False (missing node)
Space 复杂度为 O(N)，因为计数字典的每个节点（顶点）都有一个条目，其中一个整数作为值。时间复杂度为 O(ExL)，其中 E 是边数，L 是树中的层数。对于所有 parents 只有一个 child 节点的树，麦芽汁情况时间为 O(E^2)。然而，由于初始条件是 E 小于 V，最坏的情况实际上是 O(V^2)
请注意，此算法不假设边顺序或节点编号之间的数值关系。此算法找到的根（最后一个节点成为叶子）不一定是唯一可能的根，除非节点具有隐式基数关系（或边具有顺序），否则可能存在模棱两可的情况：
[1,2],[2,3],[2,4] could be:
1 2 3
|_2 OR |_1 OR |_2
|_3 |_3 |_1
|_4 |_4 |_4
如果可以依赖节点编号之间的基数关系或边的顺序，则算法可能会更高效（因为我们可以轻松确定哪个节点是根节点并从那里）。
[EDIT2] 使用组的替代方法。
当边数为N-1时，如果图是树，则所有节点都应该可以从任何其他节点到达。这意味着，如果我们为每个节点形成一组可达节点，并根据边将它们合并在一起，那么在遍历所有边后，我们应该最终得到一个组。
这是基于该方法修改后的函数：
def isTree(N,E):
if N==1 and not E: return True # root only is a tree
if len(E) != N-1: return False # a tree has N-1 edges
groups = {n:[n] for ab in E for n in ab} # each node in its own group
if len(groups) != N : return False # unlinked nodes
for a,b in E:
groups[a].extend(groups[b]) # merge groups
for n in groups[b]: groups[n] = groups[a] # update nodes' groups
return len(set(map(id,groups.values()))) == 1 # only one group when done
鉴于我们开始时边数少于节点数，并且组合并最多消耗组大小的 2 倍（因此也 < N），space 复杂度将保持为 O(五）。对于麦芽汁情况
，时间复杂度也将是 O(V^2)这是一种使用不相交集合联合/联合查找数据结构的方法：
def is_graph_tree(n, edges):
parent = list(range(n+1))
size = [1] * (n + 1)
for x, y in edges:
# find x (path splitting)
while parent[x] != x:
x, parent[x] = parent[x], parent[parent[x]]
# find y
while parent[y] != y:
y, parent[y] = parent[y], parent[parent[y]]
if x == y:
# Already connected
return False
# Union (by size)
if size[x] < size[y]:
x, y = y, x
parent[y] = x
size[x] += size[y]
return True
assert not is_graph_tree(4, [(1, 2), (2, 3), (3, 4), (4, 2)])
assert is_graph_tree(6, [(1, 2), (2, 3), (3, 4), (3, 5), (1, 6)])
运行时间是O(V + E*InverseAckermannFunction(V))，比O(V + E * log(log V))好，所以基本上是O(V + E)。