guangdubianli.txt

图的广度优先遍历算法

void   BFSTraverseAL(MGraph   *G)   
              {/*广度优先遍历以邻接矩阵存储的图G*/   
                int   i;   
                for   (i=0;i<G->n;i++)   
            visited[i]=FALSE;                             /*标志向量初始化*/   
                for   (i=0;i<G->n;i++)   
            if   (!visited[i])   BFSM(G,i);                 /*   vi未访问过，从vi开始BFS搜索*/   
              }/*BFSTraverseAL*/   
    
    
              void   BFSM(MGraph   *G,int   k)   
              {/*以Vi为出发点，对邻接矩阵存储的图G进行BFS搜索*/   
                int   i,j;   
                CirQueue   Q;   
                InitQueue(&Q);   
                printf("visit   vertex:V%c\n",G->vexs[k]);       /*访问原点Vk*/   
                visited[k]=TRUE;   
                EnQueue(&Q,k);                                             /*原点Vk入队列*/   
                while   (!QueueEmpty(&Q))   
            {i=DeQueue(&Q);                                             /*Vi出队列*/   
              for   (j=0;j<G->n;j++)                                       /*依次搜索Vi的邻接点Vj*/   
              if   (G->edges[i][j]==1   &&   !visited[j])   /*若Vj未访问*/   
                {printf("visit   vertex:V%c\n",G->vexs[j]);     /*访问Vj   */   
                                  visited[j]=TRUE;   
                EnQueue(&Q,j);                                                   /*访问过的Vj入队列*/   
                        }   
                    }   
              }/*BFSM*/