王道数据结构第六章图能否否成拓扑序列

Question

为什么这个不可以选B呀 按理说强连通图肯定是有环的的那肯定也不能成拓扑序列呀

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这个问题是关于有向图的拓扑排序。首先，我们需要理解拓扑排序的概念和强连通图的定义。

拓扑排序是针对有向无环图（DAG）的顶点的一种排序，它使得对于每一条有向边(u, v)，顶点u在排序后的序列中都出现在v之前。这意味着在拓扑排序中，不能存在环。

强连通图是指图中任意两个顶点都是相互可达的，即从任一顶点出发都可以通过路径到达另一顶点。在强连通图中，必然存在环，因为每个顶点都可以到达其他顶点并且可以回到自身。

现在来看选项：

A. 含有多个出度为0的顶点 - 这个描述并不直接关系到图是否可以进行拓扑排序。一个有向无环图可能有多个出度为0的顶点，但这不是必要条件。

B. 是个强连通图 - 这个选项是错误的。如果一个图是强连通的，那么它一定包含至少一个环，因此不能进行拓扑排序。

C. 含有多个入度为0的顶点 - 在拓扑排序中，通常至少有一个入度为0的顶点作为起点，但并不是说图一定有多个入度为0的顶点。

D. 含有顶点数大于1的强连通分量 - 这个描述也与能否进行拓扑排序无直接关系。一个有向无环图可能包含多个强连通分量，但这些分量之间没有循环依赖。

根据以上分析，选项B“是个强连通图”肯定是错误的，因为强连通图意味着图中存在环，而存在环的图是不能进行拓扑排序的。所以，如果一个有向图的顶点能排成一个拓扑序列，那么这个图肯定不是强连通图。这就是为什么不能选B的原因。