校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 关键路径
题目

关键路径是事件结点网络中()

A.从源点到汇点的最长路径

B.从源点到汇点的最短路径

C.最长回路

D.最短回路

解答

正确答案是 A

拓扑排序:
一个工程是否能顺利进行问题
表示工程的有向图,顶点表示活动,弧表示活动之间的优先关系,AOV网(Activity On Vertex Network)
排序算法:从AOV网中选择入度为0的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧,重复直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
采用的图的数据结构:邻接表,加一个存储入度的空间
关键路径:
工程完成所需要最短时间问题
从源点到汇点的最长路径,对应关键活动
(在实际应用中被当做“参考路径”,即deadline 长度最长的路径)
采用的图的数据结构:邻接表,加一个存储入度的空间
定义几个参数:
= 1 \* GB3 ①顶点vk的最早发生时间:etv
= 2 \* GB3 ②顶点vk的最晚发生时间:ltv
= 3 \* GB3 ③弧ak的最早发生时间:ete
= 4 \* GB3 ④弧ak的最晚发生时间:lte
由12推出34,根据ete[k]和lte[k]的是否相等,来判断ak是否是关键活动

C 3条回复 评论
落地成盒

解析蛮清楚的

发表于 2018-10-13 14:15:46
0 0
小可爱

Mark

发表于 2018-10-13 14:15:03
0 0
碧海问舟

关键路径在实际应用中被当做“参考路径”,即deadline 长度最长的路径

发表于 2018-10-13 14:14:54
0 0