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

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

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的遍历结果。

示例输入

1 6 7 0 0 3 0 4 1 4 1 5 2 3 2 4 3 5

示例输出

0 3 4 2 5 1

提示

以邻接矩阵作为存储结构。

#include <stdio.h> #include <stdlib.h> #include<queue> #define INF = 0x3f3f3f3f #define MAX 100 using namespace std; queue<int> q; typedef struct arcnode { int adj; }arcnode, adjmatrix[100][100]; typedef struct { adjmatrix a; int vn; int an; }MG; int k;//初始点 int i, j; int create(MG &g) { int v1, v2; scanf("%d %d %d", &g.vn, &g.an, &k); for(i=0; i<g.vn; i++) for(j=0; j<g.vn; j++) g.a[i][j].adj = 0; for(i=0; i<g.an; i++) { scanf("%d %d", &v1, &v2); g.a[v1][v2].adj = 1; g.a[v2][v1].adj = g.a[v1][v2].adj; } return 1; } int v[110];//标记数组 void bfs(MG &g, int k) { for(i=0; i<g.vn; i++) v[i] = 0; v[k] = 1; q.push(k); printf("%d", k); while(!q.empty()) { i = q.front(); q.pop(); for(j=0; j<g.vn; j++) { if(g.a[i][j].adj == 1 && !v[j]) { v[j] = 1; q.push(j); printf(" %d", j); } } } } int main() { int t; MG g; scanf("%d", &t); while(t--) { create(g); bfs(g, k); if(t!=0) printf("\n"); } return 0; }

#include <stdio.h> #include <stdlib.h> #include <queue> #include <string.h> using namespace std; int n, m; int a[110][110]; int v[110]; void bfs(int k) { int i, j; memset(v, 0, sizeof(v)); queue<int> q; q.push(k); v[k] = 1; printf("%d", k); while(!q.empty()) { i = q.front(); q.pop(); for(j=0; j<n; j++) if(a[i][j]==1&&v[j]==0) { v[j]=1; q.push(j); printf(" %d", j); } } } int main() { int t, i, j, v1, v2, k; scanf("%d", &t); while(t--) { scanf("%d %d %d", &n, &m, &k); for(i=0; i<n; i++) for(j=0; j<n; j++) a[i][j] = 0; while(m--) { scanf("%d %d", &v1, &v2); a[v1][v2] = a[v2][v1] = 1; } bfs(k); printf("\n"); } }