宽度优先遍历，是以离初状态的状态距离为序进行遍历。
宽度优先遍历详细介绍
宽度优先遍历，是以离初状态的状态距离为序进行遍历。
就是以离初状态的状态距离为序进行遍历。
维护一个队列，首先将初状态加入队列中，标记该状态已搜索，然后：
1）：取出队首元素，将它所有可产生的未标记后继状态加入队列，并将其标记为已搜索；
2）：当队列未空时重复1)；
具体题目加具体处理即可。
二叉树的宽度优先遍历
按层遍历
如右图 ：ABCDEF
图的优先遍历
图的宽度优先遍历需要一个队列作为保存当前节点的子节点的数据结构。具体的算法如下所示：
(1)顶点V入队列。
(2)当队列非空时继续执行，否则算法为空。
(3)出队列，获得队头节点V，访问顶点V并标记V已经被访问。
(4)查找顶点V的第一个邻接顶点col。
(5)若V的邻接顶点col未被访问过，则col进队列。
(6)继续查找V的其他邻接顶点col，转到步骤(5)，若V的所有邻接顶点都已经被访问过，则转到步骤(2)。
下面，我们以图示的方式介绍宽度优先遍历的过程，如图1.3所示。
图1.3 宽度优先遍历过程 |
选择A作为种子节点，则宽度优先遍历的过程，如表1.2所示。
表1.2 宽度优先遍历过程
操作 | 队列中的元素 |
初始 | 空 |
A入队列 | A |
A出队列 | 空 |
BCDEF入队列 | BCDEF |
B出队列 | CDEF |
C出队列 | DEF |
D出队列 | EF |
E出队列 | F |
H入队列 | FH |
F出队列 | H |
G入队列 | HG |
H出队列 | G |
I入队列 | GI |
G出队列 | I |
I出队列 | 空 |
在表1.2所示的遍历过程中，出队列的节点顺序既是图的宽度优先遍历的访问顺序。由此可以看出，图1.3所示的宽度优先遍历的访问顺序为
A->B->C->D->E->F->H->G->I
C++代码:
#include <iostream>#include <queue>#include <map>using namespace std;struct node{ int value; node* left; node *right;};map<node*,int> level;queue<node*> q;int process(node *head){//PengZhangZhi if (head==NULL) return 0; level=1; int nodes=0; int clevel=1; //当前遍历到的层数 int lev; int max=0; q.push(head); while(!q.empty()){ head=q.front(); lev=level; if(clevel==lev){ nodes++; } else{ clevel++; max=max>nodes? max:nodes; nodes=1; } if(head->left) level=lev+1,q.push(head->left); if(head->right) level=lev+1,q.push(head->right); } max=max>nodes? max:nodes; return max; }
