algorithm - 如何查找图是否为树及其中心

给定一个通用图结构G=(V,E)，没有父节点，叶节点和子节点的概念，而只有邻居关系，是否有一种算法(或一系列算法)可以找到:

1)如果G它是否是一棵树(检查|V| = |E|+1是否足够？)

2)如果图实际上是一棵树，它的叶子和中心是什么？ (即，图的节点可最大程度地减少树的深度)

谢谢

最佳答案

如果将树的“中心”定义为“使树深度最小的图的节点”，则找到直径的方法比找到直径的方法更简单。

d[] = degrees of all nodes
que = { leaves, i.e  i that d[i]==1}
while len(que) > 1:
  i=que.pop_front
  d[i]--
  for j in neighbors[i]:
    if d[j] > 0:
      d[j]--
      if d[j] == 1 :
        que.push_back(j)

que中剩下的最后一个是中心。

您可以通过考虑直径路径来证明这一点。
为简化起见，我们假设直径路径的长度为奇数，因此路径的中间节点是唯一的，我们称该节点为M，

我们可以看到:

M不会被推到que的后面，直到其他每个节点都在
直径路径已插入que

如果还​​有另一个节点N
在M已被插入que之后被推，则N必须
比直径路径的路径更长。因此，N不存在。 M必须是最后一个
在que

中将节点插入(并向左移)

关于algorithm - 如何查找图是否为树及其中心，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13113430/