遍历由其边表示的树

Question

我的树由它的边和根节点表示。边列表是无向.

char[][] edges =new char[][]{
    new char[]{'D','B'},
    new char[]{'A','C'},
    new char[]{'B','A'}             
};

char root='A';

这棵树是

  A
 B  C
D

如何对这棵树进行深度优先遍历？时间复杂度是多少？

我知道在链接节点上深度优先遍历的时间复杂度是 O(n)。但是如果用边来表示树，我感觉时间复杂度是O(n^2)。我错了吗？

感谢提供代码，虽然我知道它看起来像是家庭作业..

Answer 1

DFS 背后的通用模板如下所示：

 function DFS(node) {
     if (!node.visited) {
         node.visited = true;
         for (each edge {node, v}) {
             DFS(v);
         }
     }
 }

如果您将边表示为图中所有边的列表，那么您可以通过遍历图中的所有边来实现 for 循环，并且每次找到当前节点为它的源头，沿着边缘到达它的端点，然后运行从那里开始一个 DFS。如果你这样做，那么你将为图中的每个节点做 O(m) 工作（这里，m 是边的数量），所以运行时间将为 O(mn)，因为你最多做一次图中的每个节点。在一棵树中，边的数量总是 O(n)，所以对于一棵树来说，运行时间是 O(n²).

就是说，如果你有一棵树并且只有 n 条边，你可以通过多种方式加快速度。首先，您可以考虑执行 O(n log n) 预处理步骤来对边数组进行排序。然后，您可以通过进行二分搜索找到离开该节点的第一条边，然后从那里开始遍历所有边以找到离开该节点的边，从而找到离开给定节点的所有边。这大大改善了运行时间：您为二分查找的每个节点执行 O(log n) 工作，然后每条边只被访问一次。这意味着运行时间为 O(n log n)。由于您已经提到边缘是无向的，因此您实际上需要创建 edges 数组的两个不同副本 - 一个是原始副本，另一个是边缘反转 - 并且应该独立地对每个副本进行排序。 DFS 沿途标记访问过的节点这一事实意味着您不需要在这里做任何额外的簿记来确定每一步应该走哪个方向，并且这不会改变整体时间复杂度，尽管它确实增加了space 用法。

或者，您可以使用基于散列的解决方案。在进行 DFS 之前，遍历边并将它们转换为散列 table，其键是节点，其值是离开该节点的边的列表。这将花费预期的时间 O(n)。然后，您可以非常有效地执行 "for each edge" 步骤，只需执行散列 table 查找以找到有问题的边缘。这将时间减少到（预期的）O(n)，尽管 space 的使用量也增加到 O(n)。由于您的边是无向的，因此在填充 table 时，请务必在每个方向插入边。

遍历由其边表示的树

Traverse a tree represented by its edges

java

algorithm

tree

time-complexity

depth-first-search