简介
在之前的文章里我讨论过计算图里最短路径的几种方法,一个是Dijkstra's algorithm,一个是Bellman-Ford Algorithm。它们都是针对一个比较通用形式的图来进行计算处理的。在实际的应用中,有些比较特殊的图,在计算它们的最短路径的应用中往往还有一些更加简单的方法。
问题描述
Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.
问题分析
这个问题的描述里既说到了图也提到了树。从概念上来说,树是图的一个特殊的形式,对于一个连通的无环图来说,它就是一棵树。而要计算一棵树或者图的直径,我们需要计算图里面最长的路径。在不考虑树这种特殊的结构的情况下,我们可以直接运用Dijkstra's algorithm或者Bellman-Ford algorithm。不过这两种算法的时间复杂度都不是单纯的线性时间。
所以到这里我们就知道,不能直接用前面的算法来生搬硬套。看来能优化的地方就在于树这个前提了。以下图的树为例:
我们要求一个节点到其他节点的距离或者最长最短距离,它们都有一个比较有意思的特性。从一个节点到另外一个节点只有一条且唯一的一条路径。这里基于一个不重复访问原有节点的情况下。 所以我们要计算一个节点到其他所有节点的距离,只需要采用一种方式遍历树就可以了。
这个树的关键特性在于从给定的一个任意起点来说,它到其他节点都不可能构成环。所以它就不可能在通过其他的路径再访问到它访问过的节点。这样就不存在有我后面会访问到之前遍历过的节点。
现在假设给定了一个点,我们计算出来了它到所有其他节点的距离。然后呢?这一步对于问题的解决有什么作用呢?假设在上图的示例中,我们选定了最初始的节点7:
从它作为起始点开始,假定我们选择BFS作为遍历计算的方法。我们最终找到距离它最远的节点9:
这一步找到了距离7最远的节点9。这一步有什么作用呢?在最简化的情况,假设这个最远的节点和源节点分别在根节点的两个子树中。那么这个目标节点相对于根节点来说一定是在这个子树中距离最长的点。如果要求树的直径的话,这边就相当于找到了一个点。
对于另外一种情况呢?假设这个最远的节点和源节点都在根节点的一个子树中。那么它们构成的这个最长路径肯定是从源节点到一个它们的最近公共父节点,然后再往叶节点方向到另外一个节点。在这种情况下,这个最长距离节点和源节点到它们公共父节点的距离之和肯定是当前最大的。假定以这个最近公共父节点作为一个树的根,那么这个问题就可以概括成上一个情况。
对于树来说,从一个非根节点到另外一个节点的最长距离很可能是通过根节点并到达另外一个子树的叶节点的长度。其实这一步相当于间接的求出来了从根节点到其他节点的最大距离。而下一步则需要根据当前这个节点9计算它到所有其他节点的距离。如果找到了所有距离值最大的那个,就找到了图的直径。
实现考虑
基于前面的讨论,概括起来就是两个广度优先遍历的方式可以找到这个树的直径。在一般的BFS实现里,我们只是用一个boolean数组来表示访问过元素的标记。这里需要一个额外的数组int[] dist,用来记录从源节点到目标节点的距离。每次遍历的时候碰到新的节点就计算它到源节点的距离。然后在遍历完之后查找距离最远的节点,作为直径的一个节点。
剩下的事情就是根据这个节点再次重复上面的过程找距离最长的点,这样就找到了直径节点和值了。
其实这部分的代码比较简单,这里就不详细列出来了。
总结
树是一种特殊的图,所以求树的直径可以用一种更加高效的办法,而不需要直接搬用传统的Dijkstra's 算法或者Bellman-Ford算法。这里为什么随意给定一个节点找到它距离最远的点就是直径的一个点的问题还有一些小的地方没有深入分析。需要进一步思考。
相关推荐
leetcode 2 和 c Golang常用算法 这个仓库包含了一些 golang 中常用的算法 排序 1. BubbleSort ...(https://www.geeksforgeeks.org/avl-tree-set-1-insertion/) ...Diameter of a Tree (https://www.geeksforgeeks.org/d
Previous research found that the pupil diameter (PD) can be an indication of affective state, but this approach to the detection of the affective state of a computer user has not been investigated ...
Diameter Quality of Service Application
Hint: diameter of a circle is twice its radius. Hint: area of a circle is 3.14 multiplied by the square of the radius. Create a class called TestCircle. java whose main method declares 2 Circle ...
Quality of Service Attributes for Diameter
a binary tree 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. Note: The length of path between two nodes is represented by the number of edges between them. 执行 :...
二叉树的直径(diameter-of-binary-tree) 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 ...
java diameter 协议栈,实现diameter协议组定义的基本方法和接口-java diameter protocol stacks, protocol definition diameter realize the basic methods and interface
Diameter协议族包括基础协议(Diameter Base Protocol)和各种应用协议。本文介绍的基础协议提供了作为一个AAA协议的最低需求,是Diameter网络节点都必须实现的功能,包括节点间能力的协商、Diameter消息的接收及...
Seagull diameter Guide. Seagull is a multi-protocol traffic generator. 内容包含diameter协议和Seagull详解
The RESEARCH OF WAVELET TRANSFORAMTION USING IN THE TESTING PILE OF THE DIAMETER-EXTENDED PILES,叶伟,凡友华,Abstract... The FE models of diameter-extended piles and integrated piles with a hard soil l
diameter基本常用术语 可以了解一些基本的术语定义 进一步理解请看diameter基础协议
Diameter协议-rfc3588 Diameter Base Protocol The Diameter base protocol is intended to provide an Authentication, Authorization and Accounting (AAA) framework for applications such as network access ...
ims sip核心网中的diameter的java源码实现
通信技术diameter协议介绍,具体描述了diameter协议站及标志位解释及未来发展方向
This paper presents the measurement of wool diameter by the technology image processing and CCD, and the offers the theory behind measuring, methods, steps, and error analysis. This device has the ...
Diameter协议实现源码,可以学习怎么去实现协议
diameter协议 rfc3855
pulse current and delay time on the intensity of a discharge pumped Ne-like Ar soft X-ray laser operating at 46.9 nm by employing an alumina capillary having an inner diameter of 4.8 mm. Specifically,...
29272-f80 diameter.docx(4G LTE的MME和HSS通信标准diameter协议中英文对照)