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

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

（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::BFSTraverse(int v){
    bool visited[vertexNum]=false;
    queue<int> Q;
    int w,i=0,count=0;
    
    cout<
    visited[v]=true;
    ++count;
    Q.push(v);
    
    if(count==vertexNum){
        return;
    }
    while(!Q.empty()){
        v=Q.front();//队头元素出队
        Q.pop();
        for(i=0;i
            if(arc[v][i]&&!visited[i]){//w未被访问
                w=i;
                cout<
                visited[w]=true;
                ++count;
                Q.push(w);
            }
        }
    }
    
}

template <class T>
void ALGraph::BFSTraverse(int v){
    bool visited[vertexNum]=false;
    queue<int> Q;
    int w,i=0,count=0;
    
    cout<
    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<
                visited[w]=true;
                ++count;
                Q.push(w);
            }
            
            else{
                p=p->next;
            }
            
        }
    }
}

四.总结

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

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