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

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

（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;
            }
            
        }
    }
}