首页 > 代码库 > 数据结构之 图论---基于邻接矩阵的广度优先搜索遍历(输出bfs遍历序列)

数据结构之 图论---基于邻接矩阵的广度优先搜索遍历(输出bfs遍历序列)

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

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顶点的无向边。

输出

输出有n行,对应n组输出,每行为用空格隔开的k个整数,对应一组数据,表示BFS的遍历结果。

示例输入

16 7 00 30 41 41 52 32 43 5

示例输出

0 3 4 2 5 1

提示

以邻接矩阵作为存储结构。
 
#include <math.h>#include <string.h>#include <stdio.h>#include <iostream>#include <string>#include <algorithm>#include <queue>using namespace std;int map[102][102];int vis[102];int n;queue<int>q;int a[102], e=0;void bfs( int dd ){    q.push(dd);    vis[dd]=1;    e=0;    int ff;    int j;    while(!q.empty())    {        ff=q.front();        a[e++]=ff;        q.pop();        for(j=0; j<n; j++)        {            if(vis[j]==0 && map[ff][j]==1 )            {                q.push(j);                vis[j]=1;            }        }    }}int main(){    int t;    cin>>t;    int m, s;    int i, j;    int u, v;    while(t--)    {        cin>>n>>m>>s;        memset(map, 0, sizeof(map));        memset(vis, 0, sizeof(vis));        for(i=0; i<m; i++)        {            cin>>u>>v;            map[u][v]=1;            map[v][u]=1;        }        bfs(s);        for(j=0; j<e; j++)        {            if(j==0)            cout<<a[0];            else            cout<<" "<<a[j];        }        cout<<endl;    }    return 0;}

 

数据结构之 图论---基于邻接矩阵的广度优先搜索遍历(输出bfs遍历序列)