如何在非二叉有向树中查找最短路径？以G到D为例

我拥有一棵非二叉的有向树，需要查找从Team "G"到Team "D"的最短路径，可采用以下几种方法：

广度优先搜索（BFS） #

• 这是无权图（默认边权相同）中查找最短路径的经典方法。从起点Team "G"出发，按层遍历所有可达的相邻节点，一旦首次访问到Team "D"，此时的路径就是最短路径——因为BFS是按路径长度递增的顺序遍历节点，第一次抵达目标的路径必然是最短的。
• 实现时需记录每个节点的父节点，找到Team "D"后，通过回溯父节点即可还原完整的最短路径。

深度优先搜索（DFS） #

• 在有向树这种无环结构中，可通过DFS遍历所有从Team "G"到Team "D"的路径，记录每条路径的长度，最终选取长度最小的那条。不过这种方法效率低于BFS，尤其当树的规模较大时，需要遍历更多节点。

基于树结构的路径预处理 #

• 如果该有向树是有根树，且节点间的有向祖先-后代关系明确，可以提前预处理每个节点的路径信息：比如记录每个节点到根节点的路径，或是每个节点的所有可达祖先/后代。之后找到Team "G"到Team "D"的有向路径中经过的公共节点，计算各可能路径的长度，取最短的一条即可。

迭代加深搜索（IDS） #

• 结合BFS和DFS的优势，从深度1开始逐步增加搜索深度，用DFS在限定深度内查找Team "D"。首次找到目标时的搜索深度即为最短路径长度，对应的路径就是最短路径。这种方法适合内存资源有限的场景，无需像BFS那样存储大量待遍历节点。

内容的提问来源于stack exchange，提问作者Junior Chang