SDUT 2142 数据结构实验之图论二：基于邻接表的广度优先搜索遍历

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

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

Example Output

0 3 4 2 5 1

Hint

用邻接表存储。

DQE:

基于邻接表的图的广度优先搜索，利用栈纠正创建弧链表时颠倒的邻接点大小顺序。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <queue>
  4 #include <stack>
  5 using namespace std;
  6 
  7 #define MVN 110
  8 
  9 typedef struct ArcNode
 10 {
 11     int adj;
 12     ArcNode *next;
 13     char *info;
 14 }AN;    //弧结点
 15 
 16 typedef struct VNode
 17 {
 18     int x;
 19     AN *first;
 20 }VN;    //顶点节点
 21 
 22 typedef struct ALGraph
 23 {
 24     VN vex[MVN];
 25     int vexn,arcn;
 26     int s;
 27 }ALG;    //基于邻接表的图
 28 
 29 void creat(ALG &G)
 30 {
 31     int i,j,k;
 32     for(k=0;k<G.vexn;k++)
 33         G.vex[k].first=NULL;
 34     for(k=0;k<G.arcn;k++)
 35     {
 36         scanf("%d %d",&i,&j);
 37         AN *ia=new AN,*ja=new AN;
 38         ia->adj=j;
 39         ja->adj=i;
 40         ia->next=G.vex[i].first;
 41         ja->next=G.vex[j].first;
 42         G.vex[i].first=ia;
 43         G.vex[j].first=ja;
 44     }
 45 }
 46 
 47 void BFS(ALG &G)
 48 {
 49     int i;
 50     queue <int> Q;
 51     stack <int> S;
 52     bool f[MVN]={false};
 53     Q.push(G.s);
 54     while(!Q.empty())
 55     {
 56         i=Q.front();Q.pop();
 57         if(!f[i])
 58         {
 59             AN *p=G.vex[i].first;
 60             while(p)
 61             {
 62                 S.push(p->adj);
 63                 p=p->next;
 64             }
 65             //利用栈纠正临接点顺序
 66             while(!S.empty())
 67             {
 68                 Q.push(S.top());S.pop();
 69             }
 70             if(i==G.s)
 71                 printf("%d",i);
 72             else
 73                 printf(" %d",i);
 74             f[i]=true;
 75         }
 76     }
 77     printf("
");
 78 }
 79 
 80 int main()
 81 {
 82     int t;
 83     scanf("%d",&t);
 84     while(t--)
 85     {
 86         ALG G;
 87         scanf("%d %d %d",&G.vexn,&G.arcn,&G.s);
 88         creat(G);
 89         BFS(G);
 90     }
 91     return 0;
 92 }
 93 
 94 /***************************************************
 95 User name: ***
 96 Result: Accepted
 97 Take time: 0ms
 98 Take Memory: 156KB
 99 Submit time: 2016-11-18 19:51:04
100 ****************************************************/