求遍历图的最短路径问题

Question

波波老师我遇到一个问题，请求您帮忙解一下，跟图的遍历有关。
问题描述：给定一张包含N个点、N-1条边的无相连通图，节点从1到N编号，每条边的长度均为1，假设从1出发遍历所有的节点，那么总路程至少是多少？

比如输入：
4
1 2
1 3
3 4
输出：
4

因为最短的遍历路径为1->2->1->3->4

Answer 1

liuyubobobo 2018-09-07 13:35:20

关键是N个点，N-1条边的连通图，其实是一棵树，也就是从1出发，走最少的路，遍历整棵树。

那么每次从某个节点出发，下面的任务都是遍历这个节点的子树，都应该从一个节点最小的子树出发遍历，最后遍历节点最大的子树。因为一个子树节点越多，遍历回来的路程越长。最后遍历节点最多的子树，可以不遍历完就结束整个过程，从而达到路程最短。

整个过程可以递归完成。可以先从1开始遍历一遍整棵树，求出所有节点为根的子树中节点个数。再按照上面的逻辑，在每个根节点排序所有子树大小。对于除了最大的子树，都只需要2倍的节点个数即可遍历并返回，对与最大的子树，单独递归处理（因为这棵子树遍历以后不需要返回：））

整体时间复杂度是O(n)的，n为树中的节点个数：）

加油！：）

• 提问者 慕工程2559728 #1

  非常感谢！

• 提问者 慕工程2559728 #2

  bobo老师我想我明白了你的意思，可以把这个图看成一棵树，
  问题1：那可不可以把它想成对一颗树进行DFS搜索
  问题2：这种树的数据类型该如何定义呢？

• liuyubobobo 回复 提问者 慕工程2559728 #3

  1）我说的方法就是dfs：）2）树本身就是一个特殊的图，不需要重新定义数据结构，在给定的图上操作就好了：）