数据结构-列出联通集
7-39 列出连通集 (25 分) 给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N?1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。 输入格式:输入第1行给出2个整数N(0 按照"{ v?1?? v?2?? ... v?k?? }"的格式,每行输出一个连通集。先输出DFS的结果,再输出BFS的结果。 输入样例:8 6 0 7 0 1 2 0 4 1 2 4 3 5 输出样例:{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 } 图的深搜与广搜。 #include #include #include #include #include using namespace std; int n,e; int mapp[21][21]; int vis[21]; void DFS(int i) { vis[i]=1; printf("%d ",i); for(int j=0;j if(!vis[j]&&mapp[i][j]) DFS(j); } void BFS(int i) { queue Q.push(i); vis[i]=1; while(!Q.empty()) { int cnt = Q.front(); printf("%d ",cnt); Q.pop(); for(int j=0;j { if(!vis[j]&&mapp[cnt][j]) { vis[j]=1; Q.push(j); } } } } int main() { scanf("%d %d",&n,&e); int x,y; for(int i=0;i { int x,y; scanf("%d%d",&x,&y); mapp[x][y]=mapp[y][x]=1; } for(int i=0;i { if(!vis[i]) { printf("{ "); DFS(i); printf("}n"); } } memset(vis,sizeof(vis)); for(int i=0;i { if(!vis[i]) { printf("{ "); BFS(i); printf("}n"); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |