题目内容
(请给出正确答案)
[主观题]
设一个具有10个顶点的带权有向图采用邻接知阵存储,若使用Dijkstra算法求从某源顶点到其他各目
标顶点的最短路径时所用的计算时间约为10ms,那么当图中有40个顶点时计算时间约为()ms。
查看答案
如果结果不匹配,请 联系老师 获取答案
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
从大到小的次序链接的,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
点到某一指定顶点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。
● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 (矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该矩阵的元素数目为 (60) ,其中非零元素数目为 (61) 。
A、1,2,3,4,5
B、1,2,3,5,4
C、1,2,4,5,3
D、1,2,5,3,4
(60)
A.N
B.E
C.2E
D.N+E
A.N
B.E
C.2E
D.N+E
具有n个顶点e条边的无向图的邻接表,其边表结点总数为(50)。
A.n
B.e
C.2e
D.n+e