在对一个有向无环图(DAG)进行拓扑排序时,如果图中存在多个拓扑排序序列,下列哪一项是导致这种现象出现的根本原因?

答案解析

拓扑排序是对有向无环图的顶点进行排序,使得对于图中每条有向边 (u, v),顶点 u 在排序中都出现在顶点 v 的前面。多个拓扑排序序列出现是因为图中存在多个入度为0的顶点,这些顶点可以作为拓扑排序的起始点,且选择不同起始点会得到不同序列。选项A正确,说明了存在多个入度为0的顶点是关键;选项B错误,出度为0的顶点不影响拓扑排序序列的唯一性;选项C错误,环路的存在会导致无法进行拓扑排序;选项D错误,图的存储方式不影响拓扑排序结果或序列的数量。
正确答案:A
随机推荐
开始刷题