图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

（1） 深度优先遍历

深度优先遍历类似于数的先序遍历，是树的先序遍历的推广。

1. 从图中某个顶点v出发，访问v。
2. 找到刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有未被访问的邻接点为止。
3. 返回前一个访问过得且扔有未被访问的邻接点的顶点，找到该顶点的下一个未被访问的邻接点，访问该顶点。

4. 重复步骤2，3，直至图中所有顶点都被访问过。

   
   

1. 深度优先遍历算法的实现

为了在遍历过程中便于区分顶点是否已经被访问，需附设访问标志组visited[i]n],其初值为false，一旦某个顶点被访问，则其相应的分量置为true。

深度优先遍历连通图

1. 从图中某个顶点v出发，访问v，并置visited[v]的值为true。
2. 依次检查v 的所有邻接点w，如果visited[w]的值为false，再从w出发进行递归遍历，直至图中所有顶点都被访问过。

bool visited[MVNum];//访问标志数组，其初值为false
void DFS(Graph G,int v)
{//从v个顶点出发递归地深度优先遍历图
      cout<<v;visited[v]=true;//访问第v个顶点，并置访问标志数组相应分量值为true
    for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w))
//依次检查v的所有邻接点w，FirstAdjVex(G,v)表示v第一个邻接点
//NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w>0表示有邻接点。
          if(!visited[w]) DFS(G,w);//对于v的尚未访问的邻接顶点w递归调用DFS
}

深度优先遍历非连通图

void DFSTraverse(Graph G)
{
      for(v=0;v<G.vexnum;v++) visited[v] = false; //访问标志数组初始化
     for(v=0;v<G.vexnum;v++)  if(!visited[v]) DFS(G,v);//对尚未访问的顶点调用DFS
}

采用邻接矩阵表示图的深度优先遍历

void DFS_AM(AMGraph G,int v)
{//图G为邻接矩阵类型，从v个顶点出发深度优先遍历图G
    cout<<v;visited[v] = true; //访问第v个顶点，并置访问标志数组相应的分量为true
    for(w=0;w<G.vexnum;w++) //一次检查邻接矩阵v所在的行
    {
        if((G.arcs[v][w] !=0)&& (!visited[w])) DFS_AM(G,w);
//G.arcs[v][w] != 0 表示w是v的邻接点，如果w未被访问，则递归调用DFS_AM 
    }
}

采用邻接表表示图的深度优先遍历

void DFS_AL(ALGraph G  ,int v)
{//图G为邻接表类型，从v个顶点出发的深度优先遍历图
    cout <<v;visited[v]=true;
    p= G.vertices[v].firstarc;//p指向v的边链表的第一个结点
    while(P!=NULL)//边结点非空
   {
        w = p->adjvex;表示w是v 的邻接点
        if(!visited[w]) DFS_AL(G,w);//如果w未被访问，则递归调用DFS_AL 
        p=p->nexttrac;//p指向下一个边结点
    }
}

(2)广度优先遍历

图的广度优先遍历就类似于树的层序遍历。

1. 从图中某个顶点v出发，访问v。
2. 依次访问v的各个未被访问过得邻接点。

3. 分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤3，直至图中所有已被访问的顶点的邻接点都被访问到。

   
   

1.广度优先遍历连通图

1. 从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。
2. 只要队列不为空，则重复下述操作：

• 队头顶点u出队。
• 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w,并置visited[w]的值为true。然后将w进队。

void BFS(Graph G,int v)
{
    cout<<v;visited[v] =true; //访问第v个顶点，并置访问标志数组相应分量值为true
    InitQueue(Q);//辅助队列Q初始化，置空
    EnQueue(Q,v);//v进队
    while(!QueueEmpty(Q))//队列非空
    {
          DeQueue(Q,u);
          for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
          {//依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点
//NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w>=0表示存在邻接点
                  if(!visited[w])//w为u的尚未访问的邻接顶点
                  {
                          cout<<w;visited[w]=true;//访问w
                          EnQueue(Q,w);//w进队
                  }
            }
    }
}