圖的遍歷

從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這一過程就叫做圖的遍歷。

（1） 深度優(yōu)先遍歷

深度優(yōu)先遍歷類似于數(shù)的先序遍歷，是樹的先序遍歷的推廣。

1. 從圖中某個頂點v出發(fā)，訪問v。
2. 找到剛訪問過得頂點的第一個未被訪問的鄰接點，訪問該頂點。以該頂點為新頂點，重復此步驟，直至剛訪問的頂點沒有未被訪問的鄰接點為止。
3. 返回前一個訪問過得且扔有未被訪問的鄰接點的頂點，找到該頂點的下一個未被訪問的鄰接點，訪問該頂點。

4. 重復步驟2，3，直至圖中所有頂點都被訪問過。

   
   

1. 深度優(yōu)先遍歷算法的實現(xiàn)

為了在遍歷過程中便于區(qū)分頂點是否已經(jīng)被訪問，需附設(shè)訪問標志組visited[i]n],其初值為false，一旦某個頂點被訪問，則其相應的分量置為true。

深度優(yōu)先遍歷連通圖

1. 從圖中某個頂點v出發(fā)，訪問v，并置visited[v]的值為true。
2. 依次檢查v 的所有鄰接點w，如果visited[w]的值為false，再從w出發(fā)進行遞歸遍歷，直至圖中所有頂點都被訪問過。

bool visited[MVNum];//訪問標志數(shù)組，其初值為false
void DFS(Graph G,int v)
{//從v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖
      cout<<v;visited[v]=true;//訪問第v個頂點，并置訪問標志數(shù)組相應分量值為true
    for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w))
//依次檢查v的所有鄰接點w，F(xiàn)irstAdjVex(G,v)表示v第一個鄰接點
//NextAdjVex(G,v,w)表示v相對于w的下一個鄰接點，w>0表示有鄰接點。
          if(!visited[w]) DFS(G,w);//對于v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS
}

深度優(yōu)先遍歷非連通圖

void DFSTraverse(Graph G)
{
      for(v=0;v<G.vexnum;v++) visited[v] = false; //訪問標志數(shù)組初始化
     for(v=0;v<G.vexnum;v++)  if(!visited[v]) DFS(G,v);//對尚未訪問的頂點調(diào)用DFS
}

采用鄰接矩陣表示圖的深度優(yōu)先遍歷

void DFS_AM(AMGraph G,int v)
{//圖G為鄰接矩陣類型，從v個頂點出發(fā)深度優(yōu)先遍歷圖G
    cout<<v;visited[v] = true; //訪問第v個頂點，并置訪問標志數(shù)組相應的分量為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未被訪問，則遞歸調(diào)用DFS_AM 
    }
}

采用鄰接表表示圖的深度優(yōu)先遍歷

void DFS_AL(ALGraph G  ,int v)
{//圖G為鄰接表類型，從v個頂點出發(fā)的深度優(yōu)先遍歷圖
    cout <<v;visited[v]=true;
    p= G.vertices[v].firstarc;//p指向v的邊鏈表的第一個結(jié)點
    while(P!=NULL)//邊結(jié)點非空
   {
        w = p->adjvex;表示w是v 的鄰接點
        if(!visited[w]) DFS_AL(G,w);//如果w未被訪問，則遞歸調(diào)用DFS_AL 
        p=p->nexttrac;//p指向下一個邊結(jié)點
    }
}

(2)廣度優(yōu)先遍歷

圖的廣度優(yōu)先遍歷就類似于樹的層序遍歷。

1. 從圖中某個頂點v出發(fā)，訪問v。
2. 依次訪問v的各個未被訪問過得鄰接點。

3. 分別從這些鄰接點出發(fā)依次訪問他們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問。重復步驟3，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。

   
   

1.廣度優(yōu)先遍歷連通圖

1. 從圖中某個頂點v出發(fā)，訪問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個頂點，并置訪問標志數(shù)組相應分量值為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，F(xiàn)irstAdjVex(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進隊
                  }
            }
    }
}