当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 图的连通分量（利用邻接表存储信息）

图的连通分量（利用邻接表存储信息）

2020年04月03日  | 移动技术网IT编程  | 我要评论

列布妮斯卡雅,枫叶的作文,加夫兰西奇

用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
*/

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网