data-structures - 树是有向图还是无向图？

Question

我读过树是图的特例。图可以是有向的或无向的。但是，如果我们将树视为一种数据结构，它是有向图还是无向图？

Answer 1

除非另有限定，否则数学或图论中​​的树通常被假定为无向的，但在计算机科学或编程或数据结构中，通常假定树是有向的和有根的。

您需要了解讨论的上下文。

Answer 2

参见维基百科上的树：

树是无向图。

Answer 3

两者都可以接受。在某些情况下，您可能希望能够从一片叶子上升然后再下降（通常在另一个分支中），或者您可能只希望能够下降。

Answer 4

树是连接的无环图。这意味着您应该能够从任何节点u遍历到任何节点v。如果我们说树是有向的，那么可能不可能从每个节点u遍历到每个节点v。

在有根树的上下文中，方向只是告诉树的哪个节点被视为根（起点）或显示节点之间的父子关系，这就是它所说的......这个方向并不限制图形或连接的连通性在树的任何节点 u 到节点 v 之间。^[1]

---

^[1]如果我们将根中的方向视为可以在树中遍历以从节点 u 到节点 v 的实际路径，那么连接将被破坏，并且该图将不再是树。