求遍历图的最短路径问题

来源：6-5 BFS和图的最短路径 Perfect Squares

慕工程2559728

2018-09-07

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

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

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

写回答

1回答

liuyubobobo

2018-09-07

已采纳

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

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

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

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

加油！：）

liuyubobobo

慕工程2559728

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

2018-09-07

共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 2

回答 2

回答 1

回答 1