图的遍历基础

图的遍历(Travering Graph)：从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的操作的基础。

复杂性：图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。
解决办法：在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited[1…n](n为顶点数)，其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号。

图的遍历算法有深度优先搜索算法和广度优先搜索算法。采用的数据结构是(正)邻接链表。

深度优先搜索算法

深度优先搜索(Depth First Search–DFS)遍历类似树的先序遍历，是树的先序遍历的推广。

算法思想

设初始状态时图中的所有顶点未被访问，则：

从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi1 ；
从vi1出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶点；
转1，直到和vi相邻接的所有顶点都被访问为止；
继续选取图中未被访问顶点vj作为起始顶点，转1，直到图中所有顶点都被访问为止。
算法实现

由算法思想知，这是一个递归过程。因此，先设计一个从某个顶点(编号)为v0开始深度优先搜索的函数，便于调用。在遍历整个图时，可以对图中的每一个未访问的顶点执行所定义的函数。
```
typedef  emnu { FALSE , TRUE } BOOLEAN ;
BOOLEAN  Visited[MAX_VEX] ;
void  DFS(ALGraph *G , int v)
{  LinkNode  *p ;
Visited[v]=TRUE ; 
Visit[v] ;       /*  置访问标志，访问顶点v  */ 
p=G->AdjList[v].firstarc;   /*  链表的第一个结点  */
while (p!=NULL)
{  if  (!Visited[p->adjvex]) DFS(G, p->adjvex) ;
    /*  从v的未访问过的邻接顶点出发深度优先搜索   */
   p=p->nextarc ;
}   
}
void DFS_traverse_Grapg(ALGraph *G)
{  int v ;
for (v=0 ; v<G->vexnum ; v++)
Visited[v]=FALSE ;    /*  访问标志初始化  */ 
p=G->AdjList[v].firstarc ;
for (v=0 ; v<G->vexnum ; v++)
if (!Visited[v])   DFS(G , v);
}
```
算法分析

遍历时，对图的每个顶点至多调用一次DFS函数。其实质就是对每个顶点查找邻接顶点的过程，取决于存储结构。当图有e条边，其时间复杂度为O(e)，总时间复杂度为O(n+e) 。

广度优先搜索算法

广度优先搜索(Breadth First Search–BFS)遍历类似树的按层次遍历的过程。

算法思想

设初始状态时图中的所有顶点未被访问，则：
从图中某个顶点vi出发，访问vi；
访问vi的所有相邻接且未被访问的所有顶点vi1，vi2，…，vim；
以vi1，vi2， …，vim的次序，以vij(1≦j≦m)依此作为vi ，转1；

继续选取图中未被访问顶点vk作为起始顶点，转1，直到图中所有顶点都被访问为止。

算法实现

为了标记图中顶点是否被访问过，同样需要一个访问标记数组；其次，为了依此访问与vi相邻接的各个顶点，需要附加一个队列来保存访问vi的相邻接的顶点。

typedef  emnu { FALSE , TRUE } BOOLEAN ;
BOOLEAN  Visited[MAX_VEX] ;
typedef struct Queue
{  int   elem[MAX_VEX] ;
int  front , rear ;
} Queue ;     /*   定义一个队列保存将要访问顶点  */
void BFS_traverse_Grapg(ALGraph *G)
{  int k ,v , w ;
LinkNode  *p ; Queue  *Q ;
Q=(Queue *)malloc(sizeof(Queue)) ;
Q->front=Q->rear=0 ;   /*  建立空队列并初始化  */
for (k=0 ; k<G->vexnum ; k++)
Visited[k]=FALSE ;      /*  访问标志初始化  */
for (k=0 ; k<G->vexnum ; k++)
{  v=G->AdjList[k].data ;     /*  单链表的头顶点  */
   if (!Visited[v])     /*   v尚未访问   */
   {  Q->elem[++Q->rear]=v ;    /*   v入对   */
      while (Q->front!=Q->rear)
      {  w=Q->elem[++Q->front] ;
         Visited[w]=TRUE ;     /*  置访问标志  */
         Visit(w) ;     /*  访问队首元素  */
         p=G->AdjList[w].firstarc ;
         while (p!=NULL)
         {  if (!Visited[p->adjvex])
               Q->elem[++Q->rear]=p->adjvex ;
               p=p->nextarc ;
             }
         }   /*  end  while  */
     }    /*  end  if  */
 }  /*  end for  */
}

总结

用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同，因此，广度优先搜索算法遍历图的总时间复杂度为O(n+e) 。图的遍历可以系统地访问图中的每个顶点，因此，图的遍历算法是图的最基本、最重要的算法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。

总结自：《数据结构（C语言版）》清华大学出版社严蔚敏、吴伟民编著

图的遍历基础

深度优先搜索算法

算法思想

算法实现

算法分析

广度优先搜索算法

算法思想

算法实现

总结