基于邻接表的广度优先搜索

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

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
****************************************************/