2021-09-06

这几天复习数据结构,发现在复习Prim算法时,有点迷惑:对于已经松弛好的路径<u,v>,长度为a,是否存在另一个新的顶点(暂时定为x),使得源点u通过连接这个顶点x,再通过x连接v而使得u到v的路径长度缩短到b,即b<a.
这里给出我自己的思考过程,先给出答案:不存在!可利用反证法证明:

假设存在x使得: light(<u,v>)   大于  light(<u,x>)+light(<x,v>),其中:

	light(<u,v>)=a
	
	light(<u,x>)+light(<x,v>)=b

即(注意图中连线并不代表直接相连,而是代表两点之间的路径)2021-09-06
a>b,即a>(m+n=b),也就是说m,n一定要小于a才行,可问题是,如果m<a,那么按照prim算法扩展新边时,应该是至少也要选择x并入到V,而不是v并入到V,所以m不可能比a小,假设不成立,证毕。

上一篇:命令模式的理解和示例


下一篇:基于 Light 介绍安卓 8.0 HAL 变化