如何判断一个图是否为树并找出其中心

Question

是否存在一个算法（或一系列算法），可以在没有父节点、叶节点和子节点的概念，只有邻居关系的情况下找到给定通用图结构 G=(V,E)：

1）确定 G 是否是一棵树（仅检查 |V| = |E|+1 是否足够吗？）

2）如果该图实际上是一棵树，则确定其叶节点和中心节点（即使树深度最小的节点）。

谢谢

- linello

Answer 1

如果将树的“中心”定义为“最小化树深度的图节点”，那么找到它的方法比找到直径更容易。

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)

最后一个在队列中的节点是中心节点。

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

我们可以看到：

1. 只有在直径路径上的每个节点都被推入队列之前，M才会被推到队列的末尾
2. 如果有另一个节点N在M已经被推入队列之后被推入队列，那么N必须在比直径路径更长的路径上。因此N不存在。M必须是队列中最后一个被推入（并保留）的节点

- lavin

---

你的算法就是我一直在努力理解的！我已经用C++实现了它，使用std::list作为队列。 - linello

如何查找树中是否存在多个中心？ - piyukr

Answer 2

1. 不，这还不够——一棵树是一个连通图，它有 n-1 条边。在一个非连通图中可能有 n-1 条边，但它不是一棵树。
   你可以运行 BFS 查找图是否连通，然后计算边的数量，这将为您提供足够的信息以确定该图是否为一棵树。

2. 叶子节点是具有节点度数 d(v) = 1 的节点 v（只与一个相邻顶点相连接）。

---

(1) 此答案假定为非定向图。
(2) 在此，n 表示顶点的数量。

- amit

Answer 3

对于（1），你只需要验证|V|=|E|+1并且图形是完全连接的。

对于（2），您需要找到最大直径，然后选择直径路径中间的一个节点。我依稀记得对于树，有一种简单的方法可以做到这一点。

您从任意节点a开始，然后找到距离a最远的节点，称之为b。然后您从b开始搜索，并找到距离b最远的节点，称之为c。从b到c的路径是最大直径。

也有其他更方便的方法可以实现，例如这个。还可以查看Google。

- NovaDenizen