【数据结构】图的广度优先遍历

一.广度优先遍历的基本思想

（1）访问顶点v；

（2）依次访问v的各个未被访问的邻接点v1，v2，v3……，vk；

（3）分别从v1，v2，v3……，vk出发依次访问他们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

二.广度优先遍历的伪代码

1.初始化队列Q；

2.访问顶点v；visited[v]=true;顶点v入队列Q；

3.while（队列Q非空）

        3.1 v=队列Q的队头元素出队；

        3.2 w=顶点v的第一个邻接点；

        3.3while（w存在）

                3.3.1 如果w未被访问，则访问顶点w；visited[w]=1;顶点w入队；

                3.3.2 w=顶点v的下一个邻接点

三.代码实现

template<class T>
void MGraph<T>::BFSTraverse(int v){bool visited[vertexNum]=false;queue<int> Q;int w,i=0,count=0;cout<<vertex[v]<<endl;visited[v]=true;++count;Q.push(v);if(count==vertexNum){return;}while(!Q.empty()){v=Q.front();//队头元素出队Q.pop();for(i=0;i<vertexNum;i++){if(arc[v][i]&&!visited[i]){//w未被访问w=i;cout<<vertex[w]<<endl;visited[w]=true;++count;Q.push(w);}}}}

template <class T>
void ALGraph<T>::BFSTraverse(int v){bool visited[vertexNum]=false;queue<int> Q;int w,i=0,count=0;cout<<adjList[v].vertex<<endl;visited[v]=true;++count;Q.push(v);if(count==vertexNum){return;}while(!Q.empty()){v=Q.front();//队头元素出队Q.pop();struct ArcNode *p=adjList[v].firstEdge;while(p){if(!visited[p->adjvex]){w=p->adjvex;cout<<adjList[w].vertex<<endl;visited[w]=true;++count;Q.push(w);}else{p=p->next;}}}
}

四.总结

广度优先：确定起始节点后，全部邻接点（分支）同时开始遍历；

深度优先：先从一个邻接点（分支）开始遍历，直至该分支全部遍历完成，再遍历按顺序的下一个分支。