图的遍历及其连通分量个数

遍历及其连通分量个数"/>

图的遍历及其连通分量个数

问题描述】
 根据输入的图的邻接矩阵A，判断此图的连通分量的个数。

【输入形式】
 第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。

【输出形式】
 输出此图连通分量的个数。

【样例输入】
 5
 0 1 1 0 0
 1 0 1 0 0
 1 1 0 0 0
 0 0 0 0 1
 0 0 0 1 0

【样例输出】
 2

所以咱们这么构思一下

#include<iostream>
using namespace std;
#define Maxsize 1024      //定义全局变量 数组visit[]
int visit[Maxsize];
typedef struct Graph
{int a[64][64];        //建立邻接矩阵  Graph图类型
}Graph;               
void Creat(int n,Graph *s)
{int i, j;for ( i = 0; i < n; i++){for ( j = 0; j < n; j++)    //双循环 写入Graph s{cin >> s->a[i][j];}}
}
void Dfs(Graph *s,int visit[],int i,int n)  //此处传参i为行值 
{visit[i] = 1;      //设标记 已访问过for (int j = 0; j < n; j++)         //内部循环（列） 寻找是否和行点有通路{if (!visit[j]&&s->a[i][j]==1)//如果AB两点之间都没有被访问过 并且 A点和 A B C D点之间有连通{Dfs(s, visit, j, n);    //继续搜索}}
}           //此处Dfs搜索的意义在于：将访问过（可联通的）点做标记，通过调用外部一次性bfs的次数 判断连通分量的个数void Makevisit(Graph *s,int visit[],int n)
{int i, f = 0;for (i = 0; i < n; i++)visit[i] = 0;			//初始化辅助数列for (i = 0; i < n; i++)     //外部循环是从第一个点（行上的点）（若访问过则不再访问）{        // (确保所有的点都要访问，才能准确的判断连通分量个数)if (!visit[i])           //判断该点是否遍历过 若未遍历过 则进入{ f++;                  Dfs(s, visit, i, n);    //调用搜索的次数 即为连通分量的个数}}cout << f;
}int main()
{int n;  Graph *s=NULL;           //表s初始化为空s = new Graph[64];       //给表s赋值空间cin >> n;Creat(n,s);              //创建表Makevisit(s, visit, n);  //搜索return 0;
}