数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历
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顶点的无向边。
对于每组数据,第一行是三个整数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
以邻接矩阵作为存储结构。
DQE:
邻接矩阵表示图的广度优先搜索,借助队列实现。
#include <iostream> #include <cstdio> #include <queue> #include <climits> using namespace std; #define MVN 110 typedef struct AdjMatrix { int w; char *info; }AM; typedef struct MGraph { int vex[MVN]; AM arc[MVN][MVN]; int vexnum,arcnum; int k; }MG; void creat(MG &G) { int i,j,k; ;k<G.vexnum;k++) { G.vex[k]=k; } ;k<G.arcnum;k++) { scanf("%d %d",&i,&j); G.arc[i][j].w=G.arc[j][i].w=; } } void BFS(MG &G) { queue <int> Q; int i,k; bool visited[MVN]={false}; ;k<G.vexnum;k++) { if(G.vex[k]==G.k) break; } Q.push(k); while(!Q.empty()) { i=Q.front(); Q.pop(); if(!visited[i]) { if(i==G.k) printf("%d",G.vex[i]); else printf(" %d",G.vex[i]); visited[i]=true; ;k<G.vexnum;k++) { ) Q.push(k); } } } printf("\n"); } int main() { int t; scanf("%d",&t); while(t--) { MG G={}; scanf("%d %d %d",&G.vexnum,&G.arcnum,&G.k); creat(G); BFS(G); } ; } /*************************************************** User name: *** Result: Accepted Take time: 0ms Take Memory: 344KB Submit time: 2016-11-13 18:54:57 ****************************************************/