java - 遍历由边表示的树

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)。由于您已经提到边缘是无向的，因此您实际上需要创建边缘数组的两个不同副本 - 一个是原始副本，另一个副本的边缘相反 - 并且应该对每个副本进行独立排序。事实上，DFS 沿途标记了访问过的节点，这意味着您不需要在这里进行任何额外的簿记来确定每一步应该走哪个方向，这不会改变总体时间复杂度，尽管它确实增加了空间使用情况。

或者，您可以使用基于哈希的解决方案。在进行 DFS 之前，遍历边并将它们转换为哈希表，其键是节点，其值是离开该节点的边的列表。这将花费预期时间 O(n)。然后，您只需进行哈希表查找即可找到有问题的边，从而非常有效地实现“针对每个边”步骤。这将时间减少到(预期)O(n)，但空间使用量也上升到 O(n)。由于边缘是无向的，因此在填充表格时，请确保在每个方向插入边缘。