成树中,从顶点v1到顶点v6的路径为(②)。
A、1,3,6
B、1,4,6
C、1,5,4,6
D、1,4,3,6
设有一个带权有向图G=(V,E),w是G的一个顶点,w的偏心距定义为:max(从u到w的最短路径长度其中的路径长度指的是路径上各边权值的和,将G中偏心距最小的顶点称为G的中心,试设计一个函数返回带权有向图的中心(如有多个中心,可任取其中之
参数表中的引用型参数biasdist返回最小偏心距的值,函数返回该中心的顶点号。
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法:
将每个顶点视作一棵树,并将所有边按权重非降排序;
依次考查各边,只要其端点分属不同的树,则引入该边,并将端点所分别归属的树合二为一;
如此迭代,直至累计已引入n-1条边时,即得到一棵极小支撑树。
试证明:
a)算法过程中所引入的每一条边,都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻,由已引入的边所构成的森林,必是某棵极小支撑树的子图;