图的遍历方式-深度遍历/广度遍历

深度优先遍历

深度优先遍历图的方法是，从图中某顶点v出发：

1. 访问顶点v；
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

邻接矩阵的实现

 //DFS遍历
 Boolean visited[MAXVEX]; /* 访问标志的数组 */
 //1. 标识顶点是否被标记过;
 //2. 选择从某一个顶点开始(注意:非连通图的情况)
 //3. 进入递归,打印i点信息,标识; 边表
 //4. [i][j] 是否等于1,没有变遍历过visted
 void DFS(MGraph G,int i){
     //1.
     visited[i] = TRUE;
     printf("%c",G.vexs[i]);
     for(int j = 0; j < G.numVertexes;j++){
         if(G.arc[i][j] == 1 && !visited[j])
             DFS(G, j);
     }
 }
 void DFSTravese(MGraph G){
     //1.初始化
     for(int i=0;i<G.numVertexes;i++){
         visited[i] = FALSE;
     }
     //2.某一个顶点
     for(int i = 0;i<G.numVertexes;i++){
         if(!visited[i]){
             DFS(G, i);
         }
     }
 }

邻接表的实现

    Boolean visited[MAXSIZE]; /* 访问标志的数组 */
  /* 邻接表的深度优先递归算法 */
  void DFS(GraphAdjList GL, int i)
 {
   EdgeNode *p;
   visited[i] = TRUE;
   //2.打印顶点 A
   printf("%c ",GL->adjList[i].data);
   p = GL->adjList[i].firstedge;
   //3.
   while (p) {
       if(!visited[p->adjvex])
           DFS(GL,p->adjvex);
       p = p->next;
   }
 }
 // 邻接表的深度遍历操作
 void DFSTraverse(GraphAdjList GL)
 {
   //1. 将访问记录数组默认置为FALSE
   for (int i = 0; i < GL->numVertexes; i++) {
       /*初始化所有顶点状态都是未访问过的状态*/
       visited[i] = FALSE;
   }

   //2. 选择一个顶点开始DFS遍历. 例如A
   for(int i = 0; i < GL->numVertexes; i++)
       //对未访问过的顶点调用DFS, 若是连通图则只会执行一次.
       if(!visited[i])
           DFS(GL, i);
 }

广度优先遍历

广度优先搜索使用队列（queue）来实现，

1. 把根节点放到队列的末尾。
2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3. 找到所要找的元素时结束程序。
4. 如果遍历还没有找到，结束程序。

邻接矩阵的实现

 ```c
  Boolean visited[MAXVEX]; /* 访问标志的数组 */
void BFSTraverse(MGraph G){
    
    int temp = 0;
    
    //1.
    Queue Q;
    InitQueue(&Q);
    
    //2.将访问标志数组全部置为"未访问状态FALSE"
    for (int i = 0 ; i < G.numVertexes; i++) {
        visited[i] = FALSE;
    }
    
    //3.对遍历邻接表中的每一个顶点(对于连通图只会执行1次,这个循环是针对非连通图)
    for (int i = 0 ; i < G.numVertexes; i++) {
        
        if(!visited[i]){
            visited[i] = TRUE;
            printf("%c  ",G.vexs[i]);
            
            //4. 入队
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                //出队
                DeQueue(&Q, &i);
                for (int j = 0; j < G.numVertexes; j++) {
                    if(G.arc[i][j] == 1 && !visited[j])
                    {    visited[j] = TRUE;
                        printf("%c   ",G.vexs[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
        
    }
}
 ```

邻接表的实现

  Boolean visited[MAXSIZE]; /* 访问标志的数组 */
  void BFSTraverse(GraphAdjList GL){
   
   //1.创建结点
   EdgeNode *p;
   
   Queue Q;
   InitQueue(&Q);
   

   //2.将访问标志数组全部置为"未访问状态FALSE"
   for(int i = 0; i < GL->numVertexes; i++)
       visited[i] = FALSE;
   //3.对遍历邻接表中的每一个顶点(对于连通图只会执行1次,这个循环是针对非连通图)
   for(int i = 0 ;i < GL->numVertexes;i++){
       //4.判断当前结点是否被访问过.
       if(!visited[i]){
           visited[i] = TRUE;
           //打印顶点
           printf("%c ",GL->adjList[i].data);
           
           EnQueue(&Q, i);
           while (!QueueEmpty(Q)) {
               DeQueue(&Q, &i);
               p = GL->adjList[i].firstedge;
               while (p) {
                   //判断
                   if(!visited[p->adjvex]){
                       visited[p->adjvex] = TRUE;
                        printf("%c ",GL->adjList[p->adjvex].data);
                       EnQueue(&Q, p->adjvex);
                   }
                   p = p->next;
               }
           }
           
       }
       }
   }