6.3圖的遍歷

遍歷定義：

? 從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪問遍歷圖中所有的頂點，且使每個頂點僅被訪問一次，就叫作圖的遍歷，它是圖的基本運算。

遍歷實質(zhì)：找每個頂點的鄰接點的過程。

圖的特點：

? 圖中可能存在回路，且圖的任一頂點都可能與其他頂點相通，在訪問某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。

怎樣避免重復訪問？

解決思路：設(shè)置輔助數(shù)組visited[n]，用來標記每個被訪問過的頂點。

• 初始狀態(tài)visited[i]為0
• 頂點i被訪問，改visited[i]為1，防止被多次訪問

圖常用的遍歷：

• 深度優(yōu)先搜索（Depth First Search——DFS）
• 廣度優(yōu)先搜索（Breadth Frist Search——BFS）

6.3.1深度優(yōu)先遍歷(DFS)

方法：

1. 在訪問圖中某一起始頂點v后，由v出發(fā)，訪問它的任一鄰接頂點w1；
2. 再用w1出發(fā)，訪問與w1鄰接但還未被訪問過的頂點w2；
3. 然后再從w2出發(fā)，進行類似的訪問，…
4. 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。
5. 接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其他沒有被訪問的鄰接頂點。
6. 如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；
7. 如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。

例如：

連通圖的深度優(yōu)先遍歷類似于樹的先根遍歷

6.3.2深度優(yōu)先搜索遍歷算法實現(xiàn)

鄰接矩陣無向圖深度遍歷實現(xiàn)（連通圖）

void DFS(AMGraph G,int v){//圖G為鄰接矩陣類型cout<<v;visited[v]=true;//訪問第v個頂點for(w=0;w<G.vexnum;w++)//依次檢查鄰接矩陣v所在的行if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);//w是v的鄰接點，如果w未訪問，則遞歸調(diào)用DFS
}

DFS算法效率分析

• 用鄰接矩陣來表示圖，遍歷圖中每一個頂點都要從頭掃描該頂點所在行，時間復雜度為O(n²)。
• 用鄰接表來表示圖，雖然有2e個表結(jié)點，但只需掃描e個結(jié)點即可完成遍歷，加上訪問n個頭結(jié)點的時間，時間復雜度為O(n+e)。

結(jié)論：

• 稠密圖適于在鄰接矩陣上進行深度遍歷；
• 稀疏圖適于在鄰接表上進行深度遍歷。

非連通圖的遍歷

6.3.3廣度優(yōu)先搜索(BFS)

方法：從圖的某一結(jié)點出發(fā)，首先依次訪問該結(jié)點的所有鄰接點v1，v2，…，vn再按這些頂點被訪問的先后次序依次訪問與他們相鄰接的所有未被訪問的頂點。

? 重復此過程，直至所有頂點均被訪問為止。

非連通圖的廣度遍歷

頂點訪問次序：a c d e f h k b g

void BFS(Graph G,int v){//按廣度優(yōu)先非遞歸遍歷連通圖Gcout<<v;visited[v]=true;//訪問第v個頂點InitQueue(Q);//輔助隊列Q初始化，置空EnQueue(Q,v);//v進隊while(!QueueEmpty(Q)){//隊列非空DeQueue(Q,u);//隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!visited[w]){//w為u的尚未訪問的鄰接頂點cout<<w;visited[w]=true;EnQueue(Q,w);//w進隊}}
}

BFS算法效率分析

• 如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（n個元素），總的時間代價為O(n²）。
• 用鄰接表來表示圖，雖然有2e個表結(jié)點，但只需掃描e個結(jié)點即可完成遍歷，加上訪問n個頭結(jié)點的時間，時間復雜度為O(n+e)。

6.3.4DFS和BFS算法效率比較

• 空間復雜度相同，都是O(n)（借用了堆棧或隊列）；
• 時間復雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。