图的遍历程序模板–BFS

//图的遍历：DFS 和 BFS



//BFS 伪代码模板


//遍历u所在的连通块

BFS(u) 
{
    //定义队列q 
    queue q;

    将u入队;

    //设置u已被加入过队列 
    inq[u] = true; 

    while(q非空)
    {
        取出队首元素u进行访问;

        //枚举从u能直接到达的顶点v 
        for(从u出发可达的所有顶点v) 
        {
            //如果v未曾加入过队列

            if( inq[v] == false )
            {

                将v入队列;

                //设置v已经加入过队列 
                inq[v]=true; 


            }

        }



    } 





}


//遍历图G 
BFS_traverse(G) 
{
    //枚举G中的所有顶点u

    for(G的所有顶点u) 
    {
        //如果u未曾加入过队列

        if(inq[u] == false )
         {
            //遍历u所在的连通块 
            BFS(u);

         }

    }


}







//BFS 程序具体实现模板


//邻接矩阵版：


//n为顶点数，MAXV为最大顶点数 
int n,G[MAXV][MAXV]; 

//若顶点i曾加入过队列，则inq[i]==true.初值为false

//遍历u所在的连通块

void BFS(int u) 
{
    queue<int> q;
    //将初始点u入队列 
    q.push(u);

    //设置u已经 加入过队列 
    inq[u]=true;

    while(!q.empty())
    {
        int u=q.front();
        q.pop();


        for(int v=0;v<n;v++)
        {
            //如果u的邻接点v未曾加入过队列

            if(inq[v]== false && G[u][v] !=INF ) 
            {
                //将v入队列 
                q.push(v);

                //标记v为已经加入过队列 
                inq[v]=true;


            }

        } 


    }




}


//遍历图G

void BFS_traverse() 
{
    for(int u=0;u<n;u++)
    {
        if(inq[u] == false)
        {
            //遍历u所在的连通块 
            BFS(u);

        }
    }



}





//邻接表版


//图G，adj[u]存放从顶点u出发可以到达的所有顶点 
vector<int> adj[MAXV]; 
//n为顶点数，MAXV为最大顶点数
int n;

//若顶点i曾入过队列，则inq[i]==true.初值为false
bool inq[MAXV]={
  false};


//遍历单个连通块 
void BFS(int u)
{

    queue<int> q;
    q.push(u);

    inq[u]==true;

    while(!q.empty())
    {

        int u=q.front();
        q.pop();

        for(int i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i];

            if(inq[v]==false)
            {
                q.push(v);
                inq[v] = true;


            }


        }



    }










}




//遍历图G

void BFS_traverse() 
{
    //枚举所有顶点

    for(int u=0;u<n;u++)
     {

        if(inq[u] == false )
        {
            //遍历u所在的连通块 
            BFS(u);

        }
     }



}




//加入层 的数据结构


struct Node{

    int v;//顶点编号

    int layer;  //顶点层号 


}; 

vector<Node>    adj[N];


//进而修改的BFS


//s为起始顶点编号 
void BFS(int s) 
{

    //BFS 队列 
    queue<Node> q;

    //起始结点 
    Node start;

    start.v=s;
    start.layer=0;

    //将起始顶点压入队列 
    q.push(start);

    //起始顶点的编号设为已被加入过队列 
    inq[start.v]=true;

    while(!q.empty())
    {
        Node top=q.front();
        q.pop();

        //队首结点的编号 
        int u=top.v;

        for(int i=0;i<adj[u].size();i++)
        {
            int next=adj[u][i];

            next.layer = top.layer+1;

            //如果next的编号未被加入过队列


            if(inq[next.v] == false)
             {

                //将next入队列 
                q.push(next);

                //next 的编号设为已被加入过队列

                inq[next.v]=true; 


             }


        }


    }




}