广度优先遍历.txt

图的遍历算法

void traver(TD g[],int n)
{  int i;
   static int visited[M];
   for(i=1;i<=n;i++)
      visited[i]=0;
   for(i=1;i<=n;i++)
      if(visited[i]==0)
         bfs(g,i,visited);   
} //准备工作与深度遍历相似

void bfs(TD g[],int v,int visited[])
{  int qu[M],f=0,r=0;
   JD *p;
   printf("%d\n",v);  //打印结点v
   visited[v]=1;   //v的标志数组置为1
   qu[0]=v;    //v入队
   while(f<=r)  //对不空
   {  v=qu[f++];   //v出队（谁出队就查找谁的所有未被处理的邻接点，并入队）
      p=g[v].firstarc;  // p指向v的第一个邻接点
      while(p!=NULL)
      {  v=p->adjvex;  // v表示邻接点在数组中的下标
         if(visited[v]==0) 
         {  visited[v]=1;
            printf("%d\n",v);
            qu[++r]=v;  //v入队
         }
         p=p->next; //继续查找v的下一个邻接点
      }
    }
}