题目
(15)下面的( )方法可以判断出一个有向图[1]是否有环A.求最小生成树[2]B.拓扑[3]排序C.求最短路径D.求关键路径[4]
(15)下面的( )方法可以判断出一个有向图[1]是否有环
A.求最小生成树[2]
B.拓扑[3]排序
C.求最短路径
D.求关键路径[4]
题目解答
答案
答案为B，解析如下：
判断有向图是否有环,可以通过以下算法:
A. 求最小生成树 - 针对无向图[5],不能判断有向图环。
B. 拓扑排序 - 如果存在环,不能完成拓扑排序,可判断有环。
C. 求最短路径 - 仅求解最短路径,不能判断环。
D. 求关键路径 - 用于AOE网[6],不适用。
拓扑排序需要按节点顺序进行,如果存在环,排序会失败。
因此,拓扑排序可以判断有向图是否存在环。
所以本题的答案是B。
解析
步骤 1：分析选项A
求最小生成树的方法适用于无向图，不能用于判断有向图中是否存在环。
步骤 2：分析选项B
拓扑排序是一种线性排序方法，适用于有向无环图。如果在拓扑排序过程中发现无法完成排序，说明图中存在环。
步骤 3：分析选项C
求最短路径的方法，如Dijkstra算法或Floyd算法，主要用于计算图中两点之间的最短路径，不能用于判断图中是否存在环。
步骤 4：分析选项D
求关键路径的方法适用于AOE网（活动网络），用于计算完成整个工程的最短时间，不能用于判断有向图中是否存在环。
求最小生成树的方法适用于无向图，不能用于判断有向图中是否存在环。
步骤 2：分析选项B
拓扑排序是一种线性排序方法，适用于有向无环图。如果在拓扑排序过程中发现无法完成排序，说明图中存在环。
步骤 3：分析选项C
求最短路径的方法，如Dijkstra算法或Floyd算法，主要用于计算图中两点之间的最短路径，不能用于判断图中是否存在环。
步骤 4：分析选项D
求关键路径的方法适用于AOE网（活动网络），用于计算完成整个工程的最短时间，不能用于判断有向图中是否存在环。