最短路径算法原理_二叉树的度和节点公式「建议收藏」

倍增技术也叫指针跳跃技术，因为涉及到指针，所以特别适合处理链表或有向有根树之类的数据结构，在图论和涉及链表的算法中有广泛的应用。

每当循环调用倍增技术时，要处理的数据之间的距离就会逐步加倍，经过k次迭代就可以完成2^k数据的计算。

下面以最经典的表序问题和求森林的根问题来说明此技术。

1表序问题

问题描述

给定一个包含 n 个元素的链表，每个元素 i 到 i 所指元素的距离用数组 d [ i ] 表示，每个元素指向的下一个元素用数组 p [ i ] 表示，初始化链表从表头指向表尾，规定表尾元素指向自己，距离为 0，d [ n ] = 0；p [ n ] = n。求每个元素 i 到表尾的距离。

如下图，n=8，距离数组d = [6，10，12，4，8，1，4，0]，所指元素数组p = [2，3，4，5，6，7，8，8]。具体地，d [ 1 ] = 6表示元素 1 到所指元素的距离是 6，p [ 1 ] = 2表示元素 1 指向的下一个元素是 2。求所有元素到表尾元素 8 的距离。

思想描述

顾名思义，指针跳跃技术，每个元素不需要一步一步计算到表尾的距离，可以根据指针的指示跳过某些元素，直接跨好几步。当所指元素数组 p 全部更新为8时，表示所有元素都直接指向了表尾元素，且指针权值就是各元素到表尾元素的距离。

初始化
$$\begin{array}{rl}& d=[6,10,12,4,8,1,4,0]\\ & p=[2,3,4,5,6,7,8,8]\end{array}$$
步骤1：每一个元素 i 都顺着指针的指示 指向步骤1中元素 i 的下一个元素所指的元素，如因为元素1在步骤1中指向元素2，元素2在步骤1中指向元素3，所以元素1的下一个元素更新为3，距离更新为元素1到元素2的距离+元素2到元素3的距离，对每个元素重复该操作，得到更新后的数组：
$$\begin{array}{rl}& d=[16,22,16,12,9,5,4,0]\\ & p=[3,4,5,6,7,8,8,8]\end{array}$$
更新后的直观图：

步骤2：每一个元素 i 都顺着指针的指示 指向步骤2中元素 i 的下一个元素所指的元素，如因为元素1在步骤2中指向元素3，元素3在步骤2中指向元素5，所以元素1可以直接跳过元素4指向元素5，距离更新为元素1到元素3的距离+元素3到元素5的距离，对每个元素重复该操作，得到更新后的数组：
$$\begin{array}{rl}& d=[32,32,25,17,13,5,4,0]\\ & p=[5,6,7,8,8,8,8,8]\end{array}$$
更新后的直观图：

步骤3：每一个元素 i 都顺着指针的指示 指向步骤3中元素 i 的下一个元素所指的元素，如因为元素1在步骤3中指向元素5，元素5在步骤3中指向元素8，所以元素1可以直接跳过元素67指向元素8，距离更新为元素1到元素5的距离+元素5到元素8的距离，对每个元素重复该操作，得到更新后的数组：
$$\begin{array}{rl}& d=[45,37,29,17,13,5,4,0]\\ & p=[8,8,8,8,8,8,8,8]\end{array}$$
更新后的直观图：

至此，所有的元素都直接指向了表尾元素，指针的权值d就是元素到表尾元素的距离，算法结束。

伪代码

初始化d,p
while(数组p中存在非表尾元素的值)
	for all 元素i 并行do:
		 if (p[i] != p[p[i]])
		 	d[i] = d[i] + d[p[i]]
		 	p[i] = p[p[i]]
		 end if
	end for
end while
输出d

时间复杂度分析

整个算法只递归了3次就算出了规模为8的表序问题，如果不加倍增技术，时间复杂度需要 O( n )，加了倍增技术的时间复杂度只需要 O( log₂n )。

在遗传算法中，走n步可以搜索到2ⁿ的搜索空间，就是因为使用了倍增技术。
如果将每一步骤的操作用n个处理器同时并行计算这n个数据的更新，在主处理器串行计算各步骤，计算效率会大大减小，同时计算开销也会由于处理器的增多而增加。

2求森林的根问题

问题描述

给定由一组有根有向树构成的森林F，F包含n个结点，每个结点 i 从下向上指向自己的父结点 j，用 p [ i ] = j 表示，如果 i 是根节点，规定 p [ i ] = i ；求森林的根。

如下图，n=13，初始化数组p = [5，5，6，6，6，8，8，8，10，11，12，13，13]。具体地，p [ 1 ] = 5表示结点 1 的父结点是 5。求森林的根结点。

思想描述

解决该问题的思想与表序问题基本一致，流程如下：

步骤1：

p更新为
$$p=[6，6，8，8，8，8，8，8，11，12，13，13，13]$$
步骤2：

p更新为
$$p=[8，8，8，8，8，8，8，8，13，13，13，13，13]$$
至此，对于所有结点 i ，都有 p [ i ] = p [ p [ i ] ] ，算法结束，该森林的根为8和13。

今天的文章最短路径算法原理_二叉树的度和节点公式「建议收藏」分享到此就结束了，感谢您的阅读。