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

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

🎉写在前面

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

🎉目录

广度优先遍历概念

本案例示意图

邻接矩阵的设计

代码实现

关键代码详解

关于类

关于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
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