Description

給定一個(gè)無向連通圖，頂點(diǎn)編號(hào)從0到n-1，用廣度優(yōu)先搜索(BFS)遍歷，輸出從某個(gè)頂點(diǎn)出發(fā)的遍歷序列。(同一個(gè)結(jié)點(diǎn)的同層鄰接點(diǎn)，節(jié)點(diǎn)編號(hào)小的優(yōu)先遍歷）
Input

輸入第一行為整數(shù)n（0< n <100），表示數(shù)據(jù)的組數(shù)。
對(duì)于每組數(shù)據(jù)，第一行是三個(gè)整數(shù)k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜ t＜k），表示有m條邊，k個(gè)頂點(diǎn)，t為遍歷的起始頂點(diǎn)。
下面的m行，每行是空格隔開的兩個(gè)整數(shù)u，v，表示一條連接u，v頂點(diǎn)的無向邊。
Output

輸出有n行，對(duì)應(yīng)n組輸出，每行為用空格隔開的k個(gè)整數(shù)，對(duì)應(yīng)一組數(shù)據(jù)，表示BFS的遍歷結(jié)果。
Sample
Input

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

Output

0 3 4 2 5 1

Hint
以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)。

#include<bits/stdc++.h>using namespace std;const int N = 110; int mp[N][N]; int book[N];void bfs(int k, int t) {queue<int>q;int top;book[t] = 1;q.push(t);while(!q.empty()){top = q.front();q.pop();cout << top << ' ';for(int i = 0; i < k; i++){if(mp[top][i] && !book[i]){q.push(i);book[i] = 1;}}}cout << endl; }int main() {int k, n, m, t;cin >> n;while(n--){memset(book, 0, sizeof(book));memset(mp, 0, sizeof(mp));cin >> k >> m >> t;for(int i = 0; i < m; i++){int u, v;cin >> u >> v;mp[u][v] = mp[v][u] = 1;}bfs(k, t);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构实验之图论一：基于邻接矩阵的广度优先搜索遍历(BFS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。