无向图的连通分量

分量"/>

无向图的连通分量

读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立无向图的生成森林。对于森林中的每一棵生成树，遍历所有顶点，并输出遍历顶点的顺序。

输入

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。

输出

每一行输出无向图中的一棵生成树，表示按照题目描述中的深度优先遍历算法遍历相应的连通分量的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

样例输入 复制

6
0 0 0 1 0 0
0 0 1 1 0 0
0 1 0 1 0 0
1 1 1 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0

样例输出 复制

0 3 1 2 
4 5 

代码如下：

#include<iostream>
using namespace std;

int n;//结点个数
int a[50][50];//邻接矩阵存储无向图
bool b[50] = { 0 };
int c[50];//已访问过的结点
int x = 0;//c的下标，同时记录访问的结点个数

void dfs(int k);
int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for (int j = 0;j < n;j++)
        {
            cin >> a[i][j];
        }
    dfs(0);//从0开始
    for (int i = 0;i < x;i++)
    {
        cout << c[i] << " ";
    }
    cout << endl;
    while (x!=n) {
        int m = x;
        int k = 0;
        for (int i = 0;i < n;i++)
            if (b[i] == 0){
                k = i; break;
            }
        dfs(k);
        for (int i = m;i < x;i++)
            cout << c[i] << " ";
        cout << endl;
    }
}
void dfs(int k)
{
    if (b[k] == 0)//k未访问过
    {
        b[k] = 1;
        c[x] = k;
        x++;
    }
    else
        return;
    for (int i = 0;i < n;i++)
    {
        if (b[i] == 0 && a[k][i] == 1)
            dfs(i);
    }     
}

运行结果：