最小生成树的先序遍历

Question

有没有办法打印MST（使用Kruskal或Prim算法）给出的输出的前序遍历。我有些困惑，因为输出不一定总是二叉树。那么，在这里如何进行先序遍历呢？普通的DFS能完成这个任务吗？

- user6811152

Answer 1

处理这种问题的主要问题是算法问题中“树”的歧义性。有两个主要定义（实际上可能略有不同）：

1. 树是一个无环连通（无向）图。 2. 树基本上是一组节点，每个节点都有一个父节点（除了一个称为“根”节点的节点），对于每个节点的儿子列表都是有序的。

然而，您必须使用第二个定义来假设“先序遍历”的概念是明确定义的（即唯一的）。

然而，生成树只是第一个含义中的树。特别地，您必须选择一个根节点和一些儿子的顺序。之后，DFS确实会给出一个先序遍历。

- md5