设图G顶点数据的类型是整型，边上权值的数据类型是浮点型，编写一个算法，不使用最小堆实现Prim算法，从顶点v开始构造带权有向图的最小生成树.

设图G是一个有向图，设顶点值为字符型，边上权值为浮点型，其十字链表的存储表示定义如下：

(1)实现图的构造函数Graphmu1.输人-系列顶点和边，建立带权有向图的十字链表。

(2)编写一个算法，基丁图G的十字链表表示求该图的强连通分量，试分析算法的时间复杂度。

(3)以图846为例，画出它的十字链表，第一次深度优先搜索得到的finished数组及最后得到的强连通分量。

点到某一指定顶点v的最短路径，例如，对于图8-47(a)所示的带权有向图，用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.

关于最短路径的读法以顶点0为例，在从顶点0到顶点2的最短路径上，顶点0的后继为顶点1(即path[0]=1)，顶点1的后继为顶点3(即path[1]=3)，顶点3的后继顶点为2(即path[3]=2).

编写一个算法，求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char，边上权值的数据类型为float。

A.最小生成树的代价唯一。

B.所有权值最小的边一定会出现在所有的最小生成树中。

C.使用普里姆（Prim）算法从不同顶点开始得到的生成树一定相同。

D.使用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树可能不相同。

E.连通无向网的最小生成树中，顶点数恰好比边数多1。

F.若图中出现权值相同的边时，则该图的最小生成树必定不唯一。

G.若图中边上的权值各不相同，则该图的最小生成树是唯一的。

H.最小生成树的代价不一定比该图其他任何一棵生成的代价小。

A.最小生成树的代价唯一。

B.所有权值最小的边一定会出现在所有的最小生成树中。

C.使用普里姆（Prim）算法从不同顶点开始得到的生成树一定相同。

D.使用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树可能不相同。

E.连通无向网的最小生成树中，顶点数恰好比边数多1。

F.若图中出现权值相同的边时，则该图的最小生成树必定不唯一。

G.若图中边上的权值各不相同，则该图的最小生成树是唯一的。

H.最小生成树的代价不一定比该图其他任何一棵生成的代价小。

在以下假设下，重写Djkstra算法：

(1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点vertex，边上的权值length和边链表的链接指针link

(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合)，利用链表来表示集合T。

试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。

A.G的边数一定大于n-1

B.G的权值最小的边一定有多条

C.G的最小生成树的代价不一定相等

D.以上选项都不对

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

A.生成树中一定含有权值最小的e条边。

B.生成树中一定可能含有权值最小的n+1条边。

C.生成树中一定含有权值最小的n条边。

D.生成树中一定可能含有权值最小的n-1条边。

A.只要无向连通图中没有权值相同的边，则其最小生成树唯一

B.只要无向图中有权值相同的边，则其最小生成树一定不唯一

C.从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树

D.设连通图G含有n个顶点，则含有n个顶点、n-1条边的子图一定是G的生成树

成树中，从顶点v₁到顶点v₆的路径为(②)。

A、1，3，6

B、1，4，6

C、1，5，4，6

D、1，4，3，6