如果一张图使用邻接矩阵表示，做一次dfs的时间复杂度为O(n^2)，n为节点数。要是获取所有的连通分量，那总的复杂度是O(n^3)吗？
1条回答 默认 最新
MangataTS 2022-08-23 11:38关注可以用并查集来获取所有的联通分量，考虑到你是用邻接矩阵来存图的，那么也就是要遍历n^2条边，并不断统计祖先结点的个数（这里的祖先结点其实就是每一个联通分量的一个点），当并查集构造完成后也就得到了所有的联通分量，复杂度即为 n^2
评论 打赏解决 2无用举报
分享
- 2022-12-25 15:45回答 3 已采纳 class Graph: def __init__(self, num_vertices): self.num_vertices = num_vertices
- 2023-04-09 22:26回答 2 已采纳 强连通分量是指在有向图中，任意两点之间都存在一条从一个点到另一个点的有向路径，并且从另一个点也能到达第一个点的点集。所以有3个，最左边一个，中间4个，右边1个一个顶点自然是一个连通分量。因为它不需要任
- 2017-08-11 16:40回答 1 已采纳 http://blog.csdn.net/keyboardmagician/article/details/53005003
- 2022-08-29 00:05csuzhucong的博客 目录 一，无向连通图 1，无向连通图 2，割点、割边 3，双连通图 二，有向连通图 1，强连通图 2，半连通图 3，基图 4，弱连通图 5，线状图 6，收缩生成图 三，连通分量 1，连通分量 2，连通分量分割 3，无向连通分量...
- 2022-04-05 02:09回答 1 已采纳 联通分量分为强连通和弱连通，如果是弱连通，这里就不需要分了。
- 2016-12-12 11:10回答 1 已采纳 http://www.cppblog.com/Ylemzy/archive/2011/04/02/143310.html
- 2016-10-18 15:48回答 1 已采纳 http://www.cnblogs.com/codeyuan/p/4385330.html
- 2023-09-01 17:57神经骚栋的博客 然后, 我们就需要使用深度优先搜索DFS, 对邻接表中的每一个子数组进行深度递归搜索, 一边搜索同时需要一边记录已经搜索过的节点. 直到把这条边上的所有点都搜索完成即可....图中已连接分量的数目。
- 2017-11-25 11:55回答 2 已采纳 保证，重点是要保证连通，最坏情况下
- 2021-06-06 18:49回答 1 已采纳 不是非要直接相连，有路径就行
- 2021-12-11 23:42回答 2 已采纳 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);
- 2023-05-26 22:47WitheredSakura_的博客 解题关键在于将元素序列抽象为图，这样我们就只需要判断需要交换的节点是否在同一强连通分量之中。
- 2022-05-20 13:30回答 1 已采纳 可以参考一下 基于C++的带权无向图的实现 （五）- 连通图和连通分量_-盛航的博客-CSDN博客_c++ 连通图 图的连通图，连通分量的分
- 2021-01-04 15:38weekness的博客 ai aj 适定性问题 数学术语适定性问题来自于哈达玛所给出的定义。他认为物理现象中的数学模型应该具备下述性质： 存在着解 解是惟一的 解连续地取决于初边值条件 适定性问题的原型范例包括对于拉普拉斯方程的...
- 2023-05-29 09:05暴躁老哥在线刷题的博客 给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。...返回图中 完全连通分量 的数量。
- 没有解决我的问题, 去提问
问题事件
创建了问题
8月21日
悬赏问题
- ¥15 c程序不知道为什么得不到结果
- ¥40 复杂的限制性的商函数处理
- ¥15 程序不包含适用于入口点的静态Main方法
- ¥15 素材场景中光线烘焙后灯光失效
- ¥15 请教一下各位，为什么我这个没有实现模拟点击
- ¥15 执行 virtuoso 命令后，界面没有，cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置