求无向图连通分支_dfs实现.cpp

求无向图连通分支_dfs实现,很好用

#include <iostream>
#include <cstring>
using namespace std;
void dfs(int u, int path[][128], int *mark, int n, int &num, int x[]); //深度优先搜索
void output(int x[], int c);    //输出打印函数；
int main()
{
	int path[128][128];              //邻接矩阵；
	int mark[128], x[128];            //mark[]标记定点是否已走过，x[]存路径；
	int n, m, u, v;
	printf("input the vetrix number and the edge number\n");   
	while(scanf("%d %d", &n, &m) == 2)           //n代表顶点个数，m代表边个数；
	{
		memset(path, 0 , sizeof(path));           //初始化；
		memset(mark, 0, sizeof(mark));
		printf("input the edge's vetrix\n");
		for(int i = 0; i < m; i++)                //输入m条边；
		{
			scanf("%d %d", &u, &v);
			path[u][v] = 1;
			path[v][u] = 1;
		}
		for(int i = 0; i < n; i++)
		{
			if(mark[i] == 0)                       //对于每个未扫描节点深搜；
				{
					int num = 0;
					dfs(i, path, mark, n, num, x);     //深搜一次求出顶点i的连通分支；
					printf("linked subgraph %d: ", i+1);     
					output(x, num);                    //打印该连通分支；
			}
		}
		printf("input the vetrix number and the edge number\n");
	}
}
void dfs(int u, int path[][128], int *mark, int n, int &num, int x[])
{
	mark[u] = 1;                                       //更新标记；
	x[num++] = u;                                      //保存路径；
	for(int i = 0; i < n; i++)
	{
		if(path[u][i] == 1 && mark[i] == 0)dfs(i, path, mark, n, num, x);  //枚举每个邻接顶点，如果未访问过则访问；
	}
}
void output(int x[], int c)             //打印连通分支；
{
	for(int i = 0; i < c; i++)
	{
		printf("%d ", x[i]);
	}
	putchar('\n');
}