SDUT 2136 数据结构实验之二叉树的建立与遍历

seven_ • 2023年2月21日下午10:13 • Python • 阅读 323

图的广度优先遍历

题目

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

Sample Input
1
6 7 0
0 3
0 4
1 4
1 5
2 3
2 4
3 5
Sample Output
0 3 4 2 5 1

代码&分析

简单的广度优先搜索，广度优先遍历实际上就是根据一个起始点，按照不同的点离这个点的距离进行访问，先访问一遍距离为一的点，然后访问一遍距离为2的点….以此类推，因此一般是借助队列来实现。

#include<stdio.h>
#include<memory.h>
#include<queue>
#include<iostream>
using namespace std;
int s[105][105];
queue<int> v;
int k,m,t;
int flag[105];   //标记每个点是否已经遍历过
void dfs(int st){
    v.push(st);
    flag[st]=1;
    int p=0;
    while(!v.empty()){
        int temp = v.front();  //每次都取出队列首
        if(p)                 //控制一下输出格式除了第一次之外都输出一个空格
            cout<<" ";
        cout<<temp;
        p=1;
        v.pop();
        for(int i=0; i<k ;i++){    //循环所有顶点
            if((s[temp][i]==1||s[i][temp]==1)&&!flag[i]){  //如果有相邻的点并且没有访问过就加入队列
                v.push(i);
                flag[i]=1;
            }
        }
    }
}
int main(){
    int N;
    scanf("%d", &N);
    while(N--){
        cin>>k>>m>>t;
        int va, vb;
        memset(s, 0, sizeof(s));
        memset(flag, 0, sizeof(flag));
        for(int i=0; i<m; i++){         //对于输入的每一条边，无向图所以两个点都要改变值
            cin>>va>>vb;
            s[va][vb] = s[vb][va] = 1;
        }
        dfs(t);
    }
}