遍历由其边缘表示的树-Java 学习之路

我的树由其边和根节点表示 . 边列表是 undirected .

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） . 我错了吗？

给予代码表示赞赏，虽然我知道它看起来像家庭作业..

1 回答

3
DFS背后的一般模板如下所示：
```
function DFS(node) {
     if (!node.visited) {
         node.visited = true;
         for (each edge {node, v}) {
             DFS(v);
         }
     }
 }
```
如果将边缘表示为图形中所有边的列表，则可以通过迭代图中的所有边来实现for循环，并且每次找到以当前节点为源的边时，遵循边缘到其 endpoints 并从那里运行DFS . 如果您这样做，那么您最多只能在图中的每个节点执行一次此操作 . 在树中，边数始终为O（n），因此对于树，运行时为O（n2） .

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

或者，您可以使用基于散列的解决方案 . 在执行DFS之前，迭代边缘并将它们转换为哈希表，其密钥是节点，其值是离开该节点的边的列表 . 这将花费预期时间O（n） . 然后，您可以通过执行哈希表查找来查找有问题的边缘，从而非常有效地实现“for each edge”步骤 . 这减少了（预期）O（n）的时间，尽管空间使用也达到了O（n） . 由于边缘是无向的，因此在填充表格时，请务必在每个方向插入边缘 .
回复于 2024-04-26T07:02:20+08:00

遍历由其边缘表示的树

1 回答

相关问题