广度优先遍历概念
出现背景：
求解节点间的最短路径，因为它的特点是 "搜到就是最优解"。
定义：
广度优先搜索（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，整个程序结束。
调试界面
浅看一下调试结果，在取队首和追加结点之间加断点调试debug，head等于9时，输出结点值6，当head等于1时，输出结点时，再调试程序就会退出，因为rear=head,队满程序结束。
