前言
我是准备用多源最短路径来做的, 这样可以获取任意两点之间的最短路径, 然后就很简单地求出高度最短的树, 结果 330 多个点的时候就超时了, 而最大的点数为 $2 \times 10^2$.
呵呵~ (mmp)
官方方法
广度优先
首先这个图上可以找到一条最长的路径, 直觉告诉我们, 高度最低的树的根节点一定是在这条最长路径上的, 而且是靠中间.
所以我们要做的就是找到最长的那条路径, 然后, 如果路径上的节点为偶数个, 那么根节点可能有两个, 如果路径上的节点为奇数个, 那么, 根节点就是最中间的那个.
问题来了, 怎么求图中两个点的最长路径捏?
可以利用以下算法找到图中距离最远的两个节点与它们之间的路径:
- 以任意节点 $p$ 出发, 利用广度优先搜索或者深度优先搜索找到以 $p$ 为起点的最长路径的终点 $x$;
- 以节点 $x$ 出发, 找到以 $x$ 为起点的最长路径的终点 $y$;
- $x$ 到 $y$ 之间的路径即为图中的最长路径, 找到路径的中间节点即为根节点.
接下来的事情不用我教你了吧?
深度优先
广度优先的那个也可以换成深度优先.
拓扑排序
可以理解为剥洋葱, 一层一层
实际做法如下:
- 首先找到所有度为 11 的节点压入队列, 此时令节点剩余计数 $\textit{remainNodes} = n$;
- 同时将当前 $\textit{remainNodes}$ 计数减去出度为 $1$ 的节点数目, 将最外层的度为 $1$ 的叶子节点取出, 并将与之相邻的节点的度减少, 重复上述步骤将当前节点中度为 $1$ 的节点压入队列中;
- 重复上述步骤, 直到剩余的节点数组 $\textit{remainNodes} \le 2$ 时, 此时剩余的节点即为当前高度最小树的根节点.
文章评论