最小生成树的预遍历

本文介绍了最小生成树的预遍历的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有什么方法可以打印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):

树是无环连接（无向）图。

一棵树基本上是一组节点，每个节点都有一个父节点（一个节点除外，称为 root 节点），每个节点的子节点列表是有序的。

A tree is an acyclic connected (undirected) graph.

A tree is basically a set of nodes, each one having a father (except one node, called the root node) and the list of sons for each node is ordered.

但是，您必须使用第二个定义来假设 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.