给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E,分别是图的顶点数和边数。随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照"{ v1 v2 ... vk }"的格式,每行输出一个连通集。先输出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 <iostream> using namespace std; const int maxSize=15; int m,G[maxSize][maxSize]={0}; int visited[maxSize]={0}; void DFS(int V){ visited[V]=1; cout<<V<<' '; for(int i=0;i<m;i++){ if(G[V][i] && !visited[i]) DFS(i); } } void BFS(int V){ const int maxSize=100; int queue[maxSize],font=-1,rear=-1; queue[++rear]=V; visited[V]=1; while(font<rear){ int de=queue[++font]; cout<<de<<' '; for(int i=0;i<m;i++){ if(!visited[i] && G[de][i]){ visited[i]=1; queue[++rear]=i; } } } } void DFS_ALG(){ int i=0; for(;i<m;i++){ if(!visited[i]){ cout<<"{ "; DFS(i); cout<<"}"<<endl; } } } void BFS_ALG(){ int i=0; for(;i<m;i++){ if(!visited[i]){ cout<<"{ "; BFS(i); cout<<"}"<<endl; } } } int main(){ int n,a,b; cin>>m>>n; for(int i=0;i<n;i++){ cin>>a>>b; G[a][b]=1; G[b][a]=1; } DFS_ALG(); for(int i=0;i<m;i++){ visited[i]=0; } BFS_ALG(); return 0; }