图的连通分量(利用邻接表存储信息)
2020-04-02 16:01:29来源:博客园 阅读 ()
图的连通分量(利用邻接表存储信息)
用vector实现邻接表
vector <int> G[100]; //表示有100个顶点的图的邻接表
G[u].push_back(v); //从顶点u 向顶点v 画边,即在相当于创建一个二维数组G[100][i]
//搜索与顶点u 相邻的顶点v
for( int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
.......
}
邻接表表示法的优点
只需与边数成正比的内存空间
邻接表表示法的缺点
(1)设u 的相邻顶点数量为n,那么在调查顶点u 与顶点v 的关系时,需要消耗O(n)来搜索邻接表。
(2)难以有效的删除边
#include<iostream> #include<vector> #include<stack> using namespace std; static const int MAX = 100000; static const int NIL = -1; int n; vector <int> G[MAX]; int color[MAX]; //深度优先遍历 void dfs(int r, int c) { stack <int> S; S.push(r); color[r] = c; while( !S.empty() ) { int u = S.top(); S.pop(); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(color[v] == NIL) { color[v] = c; S.push(v); } } } } void assignColor() { int id = 1; //设置初始值 for( int i = 0; i < n; i++ ) color[i] = NIL; //以未访问的u为起点进行深度优先搜索 for( int u = 0; u < n; u++ ) { if( color[u] == NIL ) dfs(u, id++); } } int main() { int s, t, m, q; // n为用户数(顶点数), m 为关系个数 cin >> n >> m; //建立邻接表 for(int i = 0; i < m; i++) { cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } //深度优先遍历,将可以连通的顶点的color设置成同一值 assignColor(); cin >> q; for(int i = 0; i < q; i++) { cin >> s >> t; if( color[s] == color[t] ) { cout << "yes" << endl; } else { cout << "no" << endl; } } return 0; } /* 10 9 0 1 0 2 3 4 5 7 5 6 6 7 6 8 7 8 8 9 3 0 1 5 9 1 3 */
原文链接:https://www.cnblogs.com/mr-wei977955490/p/12622116.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:排序算法之快速排序代码c++
下一篇:c++虚函数例子解析
- 二值图像连通域标记算法优化 2020-03-11
- 利用kindlegen实现txt格式小说转换为mobi格式小说(C++实现 2020-01-30
- 结题报告 2020-01-12
- 顺序栈的表示与实现 2019-10-25
- 利用Code::Blocks搭建64位C++开发平台 2019-10-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash