qq_37109173
2017-11-25 11:55关于有向图的连通问题
有n个顶点的有向图,至少需要多少条弧才能保证是连通的。我看了有个学长写的答案是n,我觉得n不可能正确。我的想法是要保证连通,得是n-1个点构成一个有向图的强连通图,那么弧数就是(n-1)*(n-2) 再将剩下的那个节点与这个强连通图相连,那么问题来了,这个时候是该加一条有向弧,还是该加两条有向弧呢?
- 点赞
- 回答
- 收藏
- 复制链接分享
2条回答
为你推荐
- 求无向不带权图某点C到各点的最短路径dai'ma
- c语言
- 1个回答
- 有算法能够遍历无向图中所有连通顶点的组合的算法么
- 数据结构
- 0个回答
- C语言的数据结构的连通图的问题,用C语言怎么编写代码去实现?
- r语言
- Golang
- erlang
- 1个回答
- 关于有向图的连通问题
- 有向图
- 图
- 连通
- 算法
- 数据结构
- 2个回答
- K个联通块
- 联通
- 数据
- 1个回答
换一换