数据结构实验图论一：基于邻接矩阵邻接表的广度优先搜索遍历

数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历

Time Limit: 1000MS Memory limit: 65536K

题目描述

给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

输入

输入第一行为整数n（0< n <100），表示数据的组数。 对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。 下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

输出

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。

示例输入

1 6 7 0 0 3 0 4 1 4 1 5 2 3 2 4 3 5

示例输出

0 3 4 2 5 1

提示

以邻接矩阵作为存储结构。

来源

 

示例程序

 邻接表 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node { int u,v; struct node *next; } Lin; Lin *head[105]; int rear,front,vis[105],q[105]; void add(int a,int b) { Lin *p; p=(Lin *)malloc(sizeof(p)); p->v=b; p->next=head[a]; head[a]=p; } void BFS(int e) { Lin *p; p=head[e]; while(p) { int t=p->v; if(vis[t]==0) { q[rear++]=t; vis[t]=1; } p=p->next; } if(front<rear) BFS(q[front++]); } int main() { int n,t,m,i,k,j,a,b; scanf("%d",&n); while(n--) { memset(head,NULL,sizeof(head)); memset(vis,0,sizeof(vis)); scanf("%d%d%d",&k,&m,&t); while(m--) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } int tt; for(i=0; i<k; i++) { Lin *p,*q; for( p=head[i]; p; p=p->next) for(q=p->next; q; q=q->next) { if(q->v<p->v) { int t; t=p->v; p->v=q->v; q->v=t; } } } front=rear=0; printf("%d",t); vis[t]=1; BFS(t); for(i=0;i<k-1;i++) printf(" %d",q[i]); printf("\n"); } } 邻接矩阵 #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<iostream> #include<queue> #include<cstring> using namespace std; int map[105][105],vis[105],d[105]; int a,b,k,m; void BFS(int e) { int i; a++; for(i=0;i<k;i++) { if(map[e][i]==1&&vis[i]==0) { d[b++]=i;//相当于入队列 vis[i]=1; } } if(a<=b) BFS(d[a]); } int main() { int t,n,i,j; scanf("%d",&t); while(t--) { memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); scanf("%d%d%d",&k,&m,&n); while(m--) { int v,u; scanf("%d%d",&u,&v); map[u][v]=map[v][u]=1; } a=0; b=1; printf("%d",n); vis[n]=1; BFS(n); for(i=1;i<b;i++) printf(" %d",d[i]); printf("\n"); } }