数据结构实验之图论二：基于邻接表的广度优先搜索遍历
Time Limit: 1000MS
Memory Limit: 65536KB
Problem Description
给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）
Input
输入第一行为整数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顶点的无向边。
Output
输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。
Example Input
1
6 7 0
0 3
0 4
1 4
1 5
2 3
2 4
3 5
Example Output
0 3 4 2 5 1
Hint
用邻接表存储。
/*--------------------------------
Name:基于邻接表的广度优先搜索
Author:Mr.z
Time:2016-11-20
----------------------------------*/
#include <iostream>
#include <queue>
#include <memory.h>
#include <stdlib.h>
using namespace std;
#define MAX 500
bool visited[MAX];
int Begin;
typedef struct ArcNode{
int vex;
struct ArcNode *nextarc;
};
typedef struct Graph{
ArcNode G_list[MAX];
int vexNum,arcNum;
};
void CreateGraph(Graph &G){
int i;
cin >> G.vexNum >> G.arcNum >> Begin;
memset(visited,0,sizeof(bool)*MAX);
for(i=0;i<G.vexNum;i++){
G.G_list[i].nextarc=NULL;
G.G_list[i].vex=i;
}
ArcNode *p,*q1,*q2;
int first,last;
for(i=0;i<G.arcNum;i++){
cin >> first >> last;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->vex=first;
q1=&G.G_list[last];
while(q1->nextarc) q1=q1->nextarc;
p->nextarc=q1->nextarc;
q1->nextarc=p;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->vex=last;
q1=&G.G_list[first];
while(q1->nextarc) q1=q1->nextarc;
p->nextarc=q1->nextarc;
q1->nextarc=p;
}
/*for(i=0;i<G.arcNum;i++){
for(p=G.G_list[i].nextarc;p!=NULL;p=p->nextarc){
for(q1=p->nextarc;q1!=NULL;q1=q1->nextarc){
if(p->vex>q1->vex){
int temp;
temp=p->vex;
p->vex=q1->vex;
q1->vex=temp;
}
}
}
}*/
}
void BFS(Graph G){
int i;
ArcNode *p,*q1,*q2;
queue<int>que;
for(i=Begin;i<G.vexNum;i++){
if(!visited[i]){
visited[i] = true;
cout << G.G_list[i].vex;
que.push(i);
while(!que.empty()){
int k=que.front();
que.pop();
p=&G.G_list[k];
while(p->nextarc){
if(!visited[p->nextarc->vex]){
visited[p->nextarc->vex]=true;
cout << " " << p->nextarc->vex;
que.push(p->nextarc->vex);
}
p=p->nextarc;
}
}
}
}
}
int main(){
int n;
cin >> n;
while(n--){
Graph G;
CreateGraph(G);
BFS(G);
cout << endl;
}
return 0;
}
/***************************************************
User name: zhxw150244李政
Result: Accepted
Take time: 0ms
Take Memory: 176KB
Submit time: 2016-11-22 11:24:08
****************************************************/
