数据结构实验之图论二：基于邻接表的广度优先搜索遍历
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顶点的无向边。
对于每组数据，第一行是三个整数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
提示
用邻接表存储。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<queue> 5 #include<vector> 6 using namespace std; 7 priority_queue<int ,vector<int>,greater<int> >pque[102]; 8 /*这个是跟堆，具体可以去网上看看,这里用的比较简单， 9 所以不用理解很多，大概需要知道有3个参数， 10 不多说了，自己百度去吧。*/ 11 int visit[102],T;//visit是标记数组 12 queue<int>temp; 13 void BFS(int key) 14 { 15 temp.push(key); 16 while(!temp.empty())//一直访问到空为止 17 { 18 int b=temp.front(); 19 if(visit[b]) 20 temp.pop(); 21 else 22 { 23 if(T)//标记打印，以免出现格式错误 24 printf(" %d",b); 25 else 26 { 27 printf("%d",b); 28 T=1; 29 } 30 visit[b]=1; 31 temp.pop(); 32 while(!pque[b].empty())//不断地将与该点相关的点弹出 33 { 34 int a=pque[b].top(); 35 temp.push(a); 36 pque[b].pop(); 37 } 38 } 39 } 40 } 41 int main() 42 { 43 int n; 44 cin>>n; 45 while(n--) 46 { 47 memset(visit,0,sizeof(visit));//初始化 48 int k,m,t; 49 cin>>k>>m>>t; 50 for(int i=0; i<k; i++)//初始化，就是清空跟堆 51 while(!pque[i].empty()) 52 pque[i].pop(); 53 while(m--)//这里是输入 54 { 55 int a,b; 56 cin>>a>>b; 57 pque[a].push(b); 58 pque[b].push(a); 59 } 60 T=0; 61 BFS(t); 62 printf("\n"); 63 } 64 return 0; 65 }