如何在无向图中定义祖先和后代？
How are ancestors and descendants defined in an undirected graph?
我找到了 this definition of an ancestor and this definition 的后代。
它们看起来很有意义，但不幸的是只对有根树有效。
我还找到了一个非正式的。
但是，我感兴趣的是无向图的祖先和后代的正式定义。
在无向图中，您没有祖先或后代。
由于边没有方向，您无法区分某个节点“之前”（祖先）和“之后”（后代）节点。
让我们比较一下有向图和无向图。
这是一个DAG（一种特殊类型的有向图）
在这个有向图中，边有一个方向。由于它是 DAG，因此这些方向会导致排序。换句话说，边可以让你说“某个节点出现在另一个节点之前”。例如，节点 B 在节点 A 之后，因为有一条边从 A 指向 B。类似地，您可以说 A 在节点 D 之前，因为 B 在 D 之前，A 在 B 之前。这等同于说 A是 B 和 D 的祖先。反过来说，D 是 A（也是 B）的后代。
这里是去掉了方向的相同结构，即无向图。
正如您在此图中看到的那样，边缘没有方向。因为没有方向，所以无法说“节点 X 在节点 Y 之前”。虽然您可以说节点 A 在 B 之前，但您也可以说节点 B 在节点 A 之前。边缘不会产生顺序，因为它们没有方向。
如其他答案所述，您可以在无向图中定义顺序。例如选择一些节点，例如 D，然后在为您访问的边分配方向的同时行走。但是，这只会出现，因为您开始为边缘分配方向。这不在图表本身中。
但是，在无向图中，您所拥有的是 connected components。
一个连通分量包含图中通过路径连接的所有节点。
在上面的无向图中，(A, B, C, D, E) 是一个连通分量，(F, G) 是另一个连通分量。
- 将图形拆分为 1 个或多个连通分量。
- Select每个组件中的任意一个节点作为根。
- 生成从根到其他顶点的最短路径。
- 一个节点的祖先是路径上从根开始的节点
- 节点的后代是从根开始的路径上继承它的顶点。
我无法想象这个概念会产生什么非常有用的东西，但它确实存在。问题是根的任意选择。
我发现了一个有趣的post，它从不同的角度揭示了问题。
引述：
“我们可以认为无向图等同于在节点之间具有双向边的有向图。
当我们追踪一个节点的所有祖先时，我们是在递归地收集沿路径的节点到该节点。如果我们继续递归地收集无向图的双向表示中的节点，那么我们最终将收集图的连通分量中的所有节点，这些节点连接到我们要求祖先的节点。同样的论点也适用于后代。"
考虑到这一点，我们可以确定：
- "祖先：具有到图 G 中节点的路径的所有节点。"
- "descendants: 所有从图 G 中的节点有路径的节点。"
我找到了 this definition of an ancestor and this definition 的后代。 它们看起来很有意义，但不幸的是只对有根树有效。
我还找到了一个非正式的
但是，我感兴趣的是无向图的祖先和后代的正式定义。
在无向图中，您没有祖先或后代。 由于边没有方向，您无法区分某个节点“之前”（祖先）和“之后”（后代）节点。
让我们比较一下有向图和无向图。 这是一个DAG（一种特殊类型的有向图）
在这个有向图中，边有一个方向。由于它是 DAG，因此这些方向会导致排序。换句话说，边可以让你说“某个节点出现在另一个节点之前”。例如，节点 B 在节点 A 之后，因为有一条边从 A 指向 B。类似地，您可以说 A 在节点 D 之前，因为 B 在 D 之前，A 在 B 之前。这等同于说 A是 B 和 D 的祖先。反过来说，D 是 A（也是 B）的后代。
这里是去掉了方向的相同结构，即无向图。
正如您在此图中看到的那样，边缘没有方向。因为没有方向，所以无法说“节点 X 在节点 Y 之前”。虽然您可以说节点 A 在 B 之前，但您也可以说节点 B 在节点 A 之前。边缘不会产生顺序，因为它们没有方向。
如其他答案所述，您可以在无向图中定义顺序。例如选择一些节点，例如 D，然后在为您访问的边分配方向的同时行走。但是，这只会出现，因为您开始为边缘分配方向。这不在图表本身中。
但是，在无向图中，您所拥有的是 connected components。 一个连通分量包含图中通过路径连接的所有节点。 在上面的无向图中，(A, B, C, D, E) 是一个连通分量，(F, G) 是另一个连通分量。
- 将图形拆分为 1 个或多个连通分量。
- Select每个组件中的任意一个节点作为根。
- 生成从根到其他顶点的最短路径。
- 一个节点的祖先是路径上从根开始的节点
- 节点的后代是从根开始的路径上继承它的顶点。
我无法想象这个概念会产生什么非常有用的东西，但它确实存在。问题是根的任意选择。
我发现了一个有趣的post，它从不同的角度揭示了问题。
引述： “我们可以认为无向图等同于在节点之间具有双向边的有向图。 当我们追踪一个节点的所有祖先时，我们是在递归地收集沿路径的节点到该节点。如果我们继续递归地收集无向图的双向表示中的节点，那么我们最终将收集图的连通分量中的所有节点，这些节点连接到我们要求祖先的节点。同样的论点也适用于后代。"
考虑到这一点，我们可以确定：
- "祖先：具有到图 G 中节点的路径的所有节点。"
- "descendants: 所有从图 G 中的节点有路径的节点。"