广度优先搜索（BFS）

什么是广度优先搜索

广度优先搜索就是层序遍历，一层一层的搜索整个图

BFS的代码实现

使用数组实现静态的二叉树，树的结构如下显示

 

代码如下显示

 #include "stdio.h"
 #include "queue"
 using namespace std;
 ​
 const int N=100005;
 //静态数组的节点
 struct Node{
     char value;
     int lson,rson;
 ​
 }tree[N];
 //下标
 int index=1;
 //得到一个新的节点
 int newNode(char value){
     tree[index].value=value;
     tree[index].lson=0;
     tree[index].rson=0;
     return index++;
 }
 //插入一个新的节点
 void insertNode(int &father,int child,int l_r){
     if(l_r==0){
         tree[father].lson=child;
     }else{
         tree[father].rson=child;
     }
 }
 //构建一颗树
 int buildTree(){
     int A= newNode('A');
     int B= newNode('B');
     int C= newNode('C');
     int D= newNode('D');
     int E= newNode('E');
     int F= newNode('F');
     int G= newNode('G');
     int H= newNode('H');
     int I= newNode('I');
 ​
     insertNode(E,B,0);
     insertNode(E,G,1);
     insertNode(B,A,0);
     insertNode(B,D,1);
     insertNode(G,F,0);
     insertNode(G,I,1);
     insertNode(D,C,0);
     insertNode(I,H,0);
 ​
     return E;
 }
 ​
 int main(){
 ​
 //    生成这个树，得到这个树的根节点
     int root=buildTree();
 //    队列
     queue<int> q;
 //  把根节点放在队列的后面
     q.push(root);
 //    如果队列不为空
     while (q.size()){
 //        得到前面的节点
         int tmp=q.front();
 //      打印这个节点
         printf("%c\t",tree[tmp].value);
 //      这个节点已经使用过了，直接丢弃
         q.pop();
 //        如果tmp这个节点的子节点不为空，将这些子节点添加到队列的尾部
         if(tree[tmp].rson!=0)q.push(tree[tmp].rson);
         if(tree[tmp].lson!=0)q.push(tree[tmp].lson);
     }
     return 0;
 }