若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是()。
A.存在,且唯一
B.存在,且不唯一
C.存在,可能不唯一
D.无法确定是否存在
参考答案:C.
对角线以下元素均为零,表明只有顶点i到顶点j(i<j)可能有边,而顶点j到顶点i一定没有边,即有向图是一个无环图,因此一定存在拓扑序列。对于拓扑序列是否唯一,试举一例:设有向图的邻接矩阵,则存在两个拓扑序列,因此该图存在可能不唯一的拓扑序列。
结论:对于任一有向图,如果它的邻接矩阵中对角线以下(或以上)的元素均为零,则存在拓扑序列(可能不唯一)。反正,若图存在拓扑序列,却不一定能满足邻接矩阵中主对角线以下的元素均为零,但是可以通过适当地调整结点编号,使其邻接矩阵满足前述性质。
老师的讲解很有侧重点,听着不会累
请写出以下代码执行输出:(构造函数、静态块执行顺序)
多线程中sleep()和wait()方法的区别
使用js实现数组的冒泡排序
怎么理解产品经理与技术研发之间的关系?
老师的讲解很有侧重点,听着不会累