有什么方法可以打印MST给出的输出的预遍历(使用Kruskal或Prim的算法)。我很困惑,因为输出可能始终是二叉树。那么,在这里如何进行遍历?普通的DFS可以完成任务吗?
Is there any way to print the pre-order traversal of the output given by MST (using Kruskal or Prim's algorithm). I have a confusion because the output may be or not a binary tree always. So, how the pre-order traversal is possible here? Can a normal DFS do the task?
推荐答案处理此类问题时的主要问题是单词 tree 中的算法问题。主要定义有两个(实际上可能稍有不同):
The main issue when working with this kind of problem is the ambiguity of the word tree in algorithmic problems. There are two main definitions (those may in fact differ slightly):
但是,您必须使用第二个定义来假设 preoder遍历的概念很好定义(即唯一)。
However, you have to work with the second definition to assume that the concept of preoder traversal is well-defined (i.e. unique).
但是,生成树只是第一个含义的树。特别是,您必须挑选一个根节点并为儿子选择一些顺序。然后,DFS确实会给您带来掠食性遍历。
A spanning tree, though, is only a tree in the first meaning. In particular, you have to pick out a root node and some order for the sons. Afterwards, a DFS will give you a preoder traversal indeed.
更多推荐
最小生成树的预遍历
发布评论