设图G顶点数据的类型是整型,边上权值的数据类型是浮点型,编写一个算法,不使用最小堆实现Prim算法,从顶点v开始构造带权有向图的最小生成树.
已知带权连通无向图G=(V,E),其中V:{v1,v2,v3,v4,v5,v6,v7),E={(v1,v2)10,(v1,v3)2,(v3,v4)2,(v3,v6)11,(v2,v5)1,(v4,v5)4,(v4,v6)6,(v5,v7)7,(v6,v7)3}(注:顶点偶对括号外的数据表示边上的权值),从源点v1到顶点v7的最短路径上经过的顶点序列是()。
A.v1,v2,v5,v7
B.v1,v3,v4,v6,v7
C.v1,v2,v3,v4,v5,v7
D.v1,v2,v5,v4,v6,v6
在以下假设下,重写Djkstra算法:
(1)用邻接表表示有向带权图G,其中每个边结点有3个域:邻接顶点vertex,边上的权值length和边链表的链接指针link
(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合),利用链表来表示集合T。
试比较新算法与原来的算法,计算时间是快了还是慢了,给出定量的比较。
已知带权连通图G(V,E)如下:图的最小生成树(1);去掉图中的权值,图G用邻接矩阵存储。给出从顶点1出发的深度优先搜索序列(2)和广度优先搜索序列(3)。【南京理工大学2005二、6(3分)】
设有一个带权有向图G=(V,E),w是G的一个顶点,w的偏心距定义为:max(从u到w的最短路径长度其中的路径长度指的是路径上各边权值的和,将G中偏心距最小的顶点称为G的中心,试设计一个函数返回带权有向图的中心(如有多个中心,可任取其中之
参数表中的引用型参数biasdist返回最小偏心距的值,函数返回该中心的顶点号。
不相交的子集A和B=V-A,并且这两个子集具有下列性质:
(a)A中任何两个顶点在G中都不是相互邻接的;(b)B中任何两个顶点在G中都不是相互邻接的。例如,图8-34就是二部图。对V(G)的一个划分可能是A=(0,3,4,6)和B=(1,2,5,7).
(1)试编写一个算法,判断图G是否是二部图。如果图G是二部图,则你的算法应当把项点划分成为具有上述性质的两个互不相交的子集A和B。证明:当用邻接表表示图G时,这个算法的复杂度可以做到O(n+e)。其中n是图G的顶点个数,e是边数。
(2)证明:任何-棵树都是二部图
(3)证明:当且仅当图G不包含奇数条边的回路时.它是二部图。
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径,假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点“为初始顶点;②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;③重复步骤②,直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行,请证明之,否则,请举例说明。【2009年全国试题41(10分)】
设图G是具有8个顶点的无向简单图,图中有一个顶点的度数为2,删去这个2度点后,所得的主子图为7阶完全图K7。证明图G是哈密顿图。