用C++类和队列实现图搜索的广度优先遍历算法

🎉我的世界没有陌生人，只有不问远近的缘分🎉

🎉写在前面

算法课老师讲了用C++类和队列数组的知识实现bfs算法，我结合自己的理解，画了示意图并做出了改进，现在分享给大家，绝对每一个点都照顾到，让大家稍微动脑筋就能理解这个算法，那么广度优先遍历现在开始。

🎉目录

🎉总结

广度优先遍历概念

出现背景：

求解节点间的最短路径，因为它的特点是 "搜到就是最优解"。

定义：

广度优先搜索（Breadth-First Search），又称作宽度优先搜索。BFS是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。但是它盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。一般只有需求最优解的时候会用BFS。

本案例示意图

编辑

要求：

使用广度优先遍历算法输出访问结点的顺序，结果为0、1、2、4、5、8、9、3、6、7、10

邻接矩阵的设计

编辑

按照案例给出的图，我简化成了这个邻接矩阵，画法就是，两个结点之间相连设置为T，不相连设置为F，规定结点自身与自身不相连，当然对T和F要有声明，例如 const bool T =true,F=false;这样T就代表通路，F就代表断路了。

代码实现

#include<iostream> using namespace std; const int n = 11;//结点个数 const int SIZE = 10; class queue { private:
    int buffer[SIZE];
    int rear, head;//rear指向队尾元素，front指向队列前一格     int update(int value) { return (value + 1) % SIZE; } public:
    queue():head(0),rear(0){}
    bool queueNull() { return rear == head;}//队空队尾下标和队首下标相同     bool queueMax() { return update(rear) == head; } //队满     bool queueAdd(int E)     {
        if (queueMax()) return false;
        rear = update(rear);
        buffer[rear] = E;
        return true;
    }
    bool getFirstQueue(int& E)     {
        if (queueNull()) return false;
        head = update(head);
        E = buffer[head];
        return true;
    }
}; const bool F = false, T = true; bool nextClose[n][n] = {
    {F,T,T,F,F,F,F,F,F,F,F},
    {T,F,F,F,T,T,F,F,F,F,F},
    {T,F,F,F,F,F,F,F,T,T,F},
    {F,F,F,F,T,F,F,F,F,F,F},
    {F,T,F,T,F,F,T,F,F,F,F},
    {F,T,F,F,F,F,F,T,F,F,T},
    {F,F,F,F,T,F,F,F,F,F,F},
    {F,F,F,F,F,T,F,F,F,F,F},
    {F,F,T,F,F,F,F,F,F,F,F},
    {F,F,T,F,F,F,F,F,F,F,F},
    {F,F,F,F,F,T,F,F,F,F,F}
}; bool flag[n]; void BreadthFirstSearch(int begin) {
    for (int i = 0; i < n; i++) flag[i] = false;
    queue que;//创建队列对象     que.queueAdd(begin);
    flag[begin] = true;
    int node;
    while (!que.queueNull())
    {
        que.getFirstQueue(node);
        cout << node << ",";
        for (int i=0;i<n;i++)
        {
            if (nextClose[node][i] && !flag[i])
            {
                que.queueAdd(i);
                flag[i] = true;
            }
        }
    }
} int main() {
    BreadthFirstSearch(0);
    cout << "Hello World" << endl;
}

编辑

关键代码详解

相信使用类来做这个案例，很多入门的朋友都会很疑惑，对这方面知识了解比较少，所以我把最重要的两部分队列类和bfs具体实现详解一下

关于类

const int n = 11;//结点个数 const int SIZE = 10; class queue { private:
    int buffer[SIZE];
    int rear, head;//rear指向队尾元素，front指向队列前一格     int update(int value) { return (value + 1) % SIZE; } public:
    queue():head(0),rear(0){}
    bool queueNull() { return rear == head;}//队空队尾下标和队首下标相同     bool queueMax() { return update(rear) == head; } //队满     bool queueAdd(int E)     {
        if (queueMax()) return false;
        rear = update(rear);
        buffer[rear] = E;
        return true;
    }
    bool getFirstQueue(int& E)     {
        if (queueNull()) return false;
        head = update(head);
        E = buffer[head];
        return true;
    }
};

首先私有的属性有长度为10的buffer整型数组、用来指向数组的rear和head下标，和一个undate方法用来使rear和head的指向往下进行，对10求余就是得到个位数，由于是加1后求余，所以会逐步往下进行；公有区域下第一个就是queue的无参构造了，他利用初始化列表给head和rear的初始化为0；下面queueNull 是队空的判断（rear=head)；queMax 是队满的判断，让rear或者head下标重置为零；queAdd 是追加方法，将数据加到buffer队列中，如果队满，不能追加，方法结束，当队非满时，尾下标加一，将输入数据加入到队列第二个空中；而getFirstQueue 方法是取队首元素的方法，当队非空时，head下标加一，取出队列第二格元素。

关于bfs的具体实现

bool flag[n]; void BreadthFirstSearch(int begin) {
    for (int i = 0; i < n; i++) flag[i] = false;
    queue que;//创建队列对象     que.queueAdd(begin);
    flag[begin] = true;
    int node;
    while (!que.queueNull())
    {
        que.getFirstQueue(node);
        cout << node << ",";
        for (int i=0;i<n;i++)
        {
            if (nextClose[node][i] && !flag[i])
            {
                que.queueAdd(i);
                flag[i] = true;
            }
        }
    }
}

假设begin为0结点，先把标志位flag数组全置为false，接下来添加0结点到队列第二个格子，并把标志位置为true，定义node，取出0结点并输出，代表已经访问过，后面的一重循环是为了把当前结点相连的结点全部追加到队列中，当然已经访问的不会追加，追加后把该结点标志位置为true；rear 和 head 下标会随着元素的追加不断变大，当下标大于队列长度n时，又变为从零开始增大，不追加元素的时候，rear不变，等head慢慢接近rear，当二者相等时，程序结束。

五图助理解

初始状态，此时rear和head均为0，将结点0待添加

编辑

将结点0插入buffer[1]，并将与0结点连接的1、2结点追加到队列中，rear指向队尾，head取队首元素0，停留在1处，下一次循环head加1，继续追加和结点1相连的结点

编辑

这次head停留在2处，追加了与1结点相连的4、5结点，rear依然指向队尾

编辑

这里显示rear即将大于队列长度的情况，此时把head指向的4结点连接的结点3、6追加到队列中

编辑

继续加连接5结点的7、10结点，但是上一次队列已满，经过 return value=(value+1)%10，rear变为0，最终变为一，停留在1上，后续不再增加结点。随着循环的进行，head不断往后走，直到大于队列，重置为0，1，等于rear时，循环结束，rear==head，整个程序结束。

编辑