求助求助一下，强连通图不是一定有环吗？

求助一下，强连通图不是一定有环吗？有环就没有拓扑序列了，那为什么第九题不选B？

我也刚学，不知道理解的对不对，你可以当作参考。强连通图就是有向的连通图。连通图是可以没有环的，说的是路径联通即可，打个比方就是V1—V2—V3，但是V1和V3没有边（有向图的话就是弧）连接，但是也可以说V1和V3是连通的，因为有路径（就是V1到V2再到V3这条路经）。这也就是“无环路的连通图是树”这句话是对的原因（之一）。回到强连通图就是有向的连通图，按照无向图中连通图的理解，就可以知道强连通图是可以无环路的。这只是对“强连通图不是一定有环吗”这句话做解答，这道题我不会。。我盲猜选D，AC感觉是对的，B不知道为啥不对，不过你说这题不选B的话就排除了，所以我选D

不感兴趣

开通SVIP免广告

有环不一定强联通啊，强联通图是任意两点都有路径，没有拓扑排序只能说明有环

回复2楼楼中楼吧友 @王中炫zed ：强连通图不一定有环。强连通图是指任意两个顶点之间都存在一条路径，即从起点到终点或者从终点到起点的路径是双向的。在有向图中，如果任意两个顶点之间都有一条双向路径，那么这个图就是强连通图。强连通图不一定有环。例如，一个有向图中有两个顶点，它们之间有一条双向路径，其他顶点之间都没有边，这样的图是强连通图，但是没有环。因此，选项 D 是正确的。

不能排成拓扑序列说明有环，但有环不一定就是强联通图，比如仅有一个点的情况也可以看作是强连通图，但是没有环，只有在顶点数大于2的强连通图才会有环

我举个B的反例吧：A1 --> A2 <--> A3。这个有向图不能排成一个拓扑序列（ A2 <--> A3是个环），但是这个图不是个强联通图，因为A1和A2（或者A3）不是强联通的。所以一个有向图的顶点不能排成一个拓扑序列只能说明该有向图里面包含环，即含有顶点数大于1的强联通分量。

一个点的时候就没有环了

有环不一定全部都是强连通的啊，局部有环就行了

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

12回复贴，共1页

<<返回数据结构吧

分享到:

日	一	二	三	四	五	六