【数据结构】图遍历--广度优先搜索

叶茂林

发布于 2023-07-30 13:22:13

1700

发布于 2023-07-30 13:22:13

文章被收录于专栏：叶子的开发者社区

题目描述

给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始

以下代码框架仅供参考，同学们可在理解的基础上自行设计算法，不强制要求和框架相同

注意：图n个顶点编号从0到n-1

代码框架如下：

输入

第一行输入t，表示有t个测试实例

第二行输入n，表示第1个图有n个结点

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开

以此类推输入下一个示例

输出

每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开

输入样例1

2 4 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 5 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0

输出样例1

0 2 3 1 0 3 4 2 1

思路分析

它的代码框架我们就不看了，文字太多，不想看，不过是个BFS，我们自己写。

毫无疑问我们需要用到队列，这次不用自己写一个队列了，没说不能用STL吧。

把队首元素取出来，标记为已访问，之后把队首元素连接的节点入队，重复操作，直到队列为空，这不就完事了。

当然，为了避免它是一个非连通的图，我们需要遍历每一个未曾访问的节点去BFS，具体看代码就懂了，代码这么短。

AC代码

#include<iostream>
#include<queue>
using namespace std;
const int max_vertex_number=20;
class Map{
    int vertex_number=0;
    bool visited[max_vertex_number]={false};
    int matrix[max_vertex_number][max_vertex_number];
public:
    Map(){
        cin>>vertex_number;
        for(int i=0;i<vertex_number;i++)
            for(int j=0;j<vertex_number;j++)
                cin>>matrix[i][j];
    }
    void BFS(int cur){
        queue<int>open;
        open.push(cur);
        cout<<cur<<' ';
        visited[cur]= true;
        while(!open.empty()){
            cur=open.front();
            open.pop();
            for(int i=0;i<vertex_number;i++)
                if(matrix[cur][i]&&visited[i]== false){
                    cout<<i<<' ';
                    visited[i]= true;
                    open.push(i);
                }
        }
    }
    void Traverse(){
        for(int i=0;i<vertex_number;i++)
            if(visited[i]== false)
                BFS(i);
        cout<<endl;
    }
};
int main() {
    int t;
    cin>>t;
    while(t--){
        Map test;
        test.Traverse();
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构