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

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

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

/*----------------------
Name:图论之邻接矩阵的广度优先搜索
Author:Mr.z
Time:2016-11-16
------------------------*/
#include <iostream>
#include <memory.h>
#include <queue>
using namespace std;
#define MAX 101
bool visited[MAX];
typedef struct{
    int Vex[MAX];
    int begin,vNum,eNum;
    bool Edge[MAX][MAX];
}Graph;

void CreateGraph(Graph &G){
    cin >> G.vNum >> G.eNum >> G.begin;
    memset(visited,0,sizeof(bool)*MAX);
    memset(G.Edge,0,sizeof(bool)*MAX*MAX);
    for(int i=0;i<G.vNum;i++)
        G.Vex[i]=i;
    for(int i=0;i<G.eNum;i++){
        int k,w;
        cin >> k >> w;
        G.Edge[k][w]=true;
        G.Edge[w][k]=true;
    }
}
void BFS_visit(Graph G,int begin){
    visited[begin]=true;
    queue<int>que;
    que.push(G.Vex[begin]);
    cout << que.front();
    while(!que.empty()){
        int k=que.front();
        que.pop();
        for(int i=0;i<G.vNum;i++){
            if(G.Edge[k][i]==true && visited[i]==false){
                que.push(G.Vex[i]);
                cout <<" "<< i;
                visited[i]=true;
            }
        }
    }
}
void BFS(Graph G,int begin){
    for(int i=begin;i<G.vNum;i++)
        if(!visited[i])
            BFS_visit(G,i);
}
int main(){
    int n;
    cin >> n;
    while(n--){
        Graph G;
        CreateGraph(G);
        BFS(G,G.begin);
        cout << endl;
    }
    return 0;
}

/***************************************************
User name: zhxw150244李政
Result: Accepted
Take time: 0ms
Take Memory: 188KB
Submit time: 2016-11-17 22:11:42
****************************************************/