先广遍历

算法描述

①将图中所有顶点作“未访问过”标记
②任选图中一个尚未访问过的顶点v作搜索起点
③访问v
④相继地访问与v相邻而尚未访问过的所有节点,并依次访问与这些顶点相邻而尚未访问过的所有顶点。反复如此，直至找不到这样的顶点。

先广遍历算法

void bfs()
{
    Eptr p;
    int u,v,w,first,last,q[n]; //q用作队列，first,last是首尾指针
    first=last=0;             //队列初始化
    for (int u=0;u<n;u++)
        L[u].mark=0;          //进队标记初始化
    for(int u=0;u<n;u++)       //找搜索起点 
        if(L[u].mark==0)       //若u未进队，则选作搜索起点
        {
            q[last++]=u;       //u进队
            L[u].mark=1;          //置u进队标记
            while(first!=last)     //当队列不空时
            {
                v=q[first++];      //v出队
                visit(v);            //访问v
                p=L[v].firstedge;    //搜索v的邻接点
                while(p!=NULL)
                {
                    w=p->adjacent;    //w作为v的邻接点
                    if(L[w].mark==0)  //若w未进队
                    {
                        q[last++]=w;    //w进队
                        L[w].mark=1;     //置进队标记
                    }
                    p=p->next;          //找v的下一个邻接点
                }
            }
        }
}