首页 > 试题广场 >

图中的强连通分量的个数为()个。

[填空题]
图中的强连通分量的个数为1个。


查看正确选项
添加回答
牛客9224906号头像 牛客9224906号

有向图强连通分量在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

如下面的图，虽然不是强连通图，但是有3个强连通分量，都用红色框标注。

发表于 2017-07-10 11:12:12 回复(0)
士心不改头像 士心不改
这个图  连通分量如何求！！！！！！！
发表于 2018-12-20 21:41:14 回复(1)
sgbs头像 sgbs
三个强连通分量如何得到？
发表于 2017-07-09 08:24:11 回复(0)
黏黏糖头像 黏黏糖
中间四个顶点为一个强连通分量，左右两个顶点各为一个强连通分量
发表于 2017-05-24 20:27:24 回复(0)
牛客247437083号头像 牛客247437083号
强连通分量的定义楼上已经给出来了，答案是有3个。中间四个顶点之间是任意点都可以互相到达的，不要忘了还要算上最左边一个顶点，以及最右边一个顶点，它们也属于连通分量。

不理解的可以看清华大学那本《数据结构》数的7.1节内容，图中的一个例子贴图如下。

发表于 2021-02-23 11:49:24 回复(0)
我没见过啊头像 我没见过啊
3个，一个顶点只有出度没有入度构成一个强联通分量，左右两边各一个，中间四个是一个

发表于 2022-11-15 20:41:41 回复(0)
提交观点

问题信息

图
上传者：Letitia
难度：
6条回答 10656浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号