數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)小記4（圖4之圖的遍歷）
圖的遍歷和樹的遍歷類似，也是從圖中的某一頂點(diǎn)出發(fā)按照某種方法對(duì)圖中所有頂點(diǎn)訪問且僅僅訪問一次，圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝完P(guān)鍵路徑等算法的基礎(chǔ)。
根據(jù)路徑的方向，通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。它們對(duì)無向圖和有向圖都適用。
深度優(yōu)先搜索：
深度優(yōu)先搜索（Depth First Search,DFS,類似于樹的先序遍歷，是樹的先序遍歷的推廣）過程：
（1）找圖中某個(gè)頂點(diǎn)v出發(fā)，訪問v
（2）找出剛訪問過的頂點(diǎn)的第一個(gè)未被訪問的鄰接點(diǎn)，訪問該頂點(diǎn)。以該頂點(diǎn)為新頂點(diǎn)，重復(fù)此步驟，直到剛訪問過的頂點(diǎn)沒有未被訪問過的鄰接點(diǎn)為止。
（3）返回前一個(gè)訪問過的且仍有未被訪問的鄰接點(diǎn)的頂點(diǎn)，找出該頂點(diǎn)的下一個(gè)未被訪問的鄰接點(diǎn)，訪問該頂點(diǎn)。
（4）重復(fù)步驟（2）和（3）。
例如此圖，DFS的順序?yàn)椋?->2->3->5->4(回溯到點(diǎn)4）（還有其他的遍歷路徑）
2.算法實(shí)現(xiàn)
【算法步驟】
（1）從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問v,并置visited[v]為true
（2）依次檢查v的所有鄰接點(diǎn)w,若visited[w]的值為false,再?gòu)膚出發(fā)進(jìn)行遞歸遍歷，直到圖中所有的頂點(diǎn)都被訪問過。（visited[]數(shù)組用于標(biāo)記區(qū)分頂點(diǎn)是否已被訪問，初值置為false,一旦某個(gè)頂點(diǎn)被訪問，則其相應(yīng)的分量置為true）
【算法描述】
DFS遍歷連通圖(大體的算法，后續(xù)算法會(huì)用鄰接矩陣和鄰接表實(shí)現(xiàn)）
bool visited[MVNum]; //其初值為false
void DFS(Graph G,int v)
{//從第v個(gè)頂點(diǎn)出發(fā)遞歸
cout<<v;
visited[v]=true; //頂點(diǎn)被訪問，則其相應(yīng)的分量置為true
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)）
//FirstAdjVex(G,v)表示v的第一個(gè)鄰接點(diǎn)
//NextAdjVex(G,v,w)表示v相對(duì)于w的下一個(gè)鄰接點(diǎn)，w≥ 0表示存在鄰接點(diǎn)
//以上兩個(gè)函數(shù)如果圖的存儲(chǔ)結(jié)構(gòu)不同，這倆的實(shí)現(xiàn)方法也不同，時(shí)間耗費(fèi)也不同，后續(xù)的算法會(huì)用鄰接矩陣和鄰接表具體實(shí)現(xiàn)遍歷過程
if(!visited[w])? DFS(G,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);//調(diào)用DFS算法
}
用鄰接矩陣表示圖的DFS
void DFS_AM(AMGraph G,int v)
{cout<<v;
visited[v]=true;//置訪問過的標(biāo)志數(shù)組相應(yīng)分量值為true
for(w=0;w<G.vexnum;w++)//依次檢查鄰接矩陣v所在的行
if((G.arcs[v][w]!=0)&&（!visited[w]）) DFS_AM(G,M);
//G.arcs[v][w]!=0表示w是v的鄰接點(diǎn)，如果w未訪問，則遞歸調(diào)用DFS_AM
}
用鄰接表表示圖的DFS
void DFS_AL(ALGraph G,int v)
{
cout<<v;
visited[v]=true;//置訪問過的標(biāo)志數(shù)組相應(yīng)分量值為true
p=G.vertices[v].firstarc;//p指向v的邊鏈表的第一個(gè)邊結(jié)點(diǎn)
while(p!=NULL)
{
w=p->adjvex;
if(!visited[w]) DFS_AL(G,w);
p=p->nextarc;
}
}
【算法分析】
在分析以上算法，在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問，就不再?gòu)乃霭l(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上就是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程，其耗費(fèi)的時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。
當(dāng)用鄰接矩陣表示圖時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)的時(shí)間復(fù)雜度為O(n^2).(n為圖中頂點(diǎn)數(shù)）
當(dāng)用鄰接表做圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找鄰接點(diǎn)的時(shí)間復(fù)雜度為O(e),其中e為圖中的?邊數(shù)，故當(dāng)以鄰接表做存儲(chǔ)結(jié)構(gòu)時(shí)，DFS遍歷圖的時(shí)間復(fù)雜度為O(n+e).
廣度優(yōu)先搜索遍歷的過程?
廣度優(yōu)先搜索(Breadth First Search,BFS)遍歷類似于樹的層次遍歷過程。
過程：
（1）從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問v
（2）依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)
（3）分別從這些鄰接點(diǎn)出發(fā)依次訪問他們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問。重復(fù)步驟(3)，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。
BFS遍歷的順序?yàn)椋?->2->4->3->5
BFS算法實(shí)現(xiàn)
【算法步驟】
（1）從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問v, 并置visited[v]的值為true,然后將v進(jìn)隊(duì)
（2）只要隊(duì)列不為空，則重復(fù)下述操作：
隊(duì)頭頂點(diǎn)u出隊(duì)
依次檢查u的所有鄰接點(diǎn)w,如果visited[w]的值為false,則訪問w,并置visited[w]的值為true,然后將w進(jìn)隊(duì)
【算法描述】
BFS遍歷連通圖
void BFS(Graph G,int v)
{
cout<<v;
visited[w]=true;
InitQueue(Q);//輔助隊(duì)列Q初始化，置空
EnQueue(Q，v);//v進(jìn)隊(duì)
while(!QueueEmpty(Q))//隊(duì)列非空
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)）
//FirstAdjVex(G,v)表示v的第一個(gè)鄰接點(diǎn)
//NextAdjVex(G,v,w)表示v相對(duì)于w的下一個(gè)鄰接點(diǎn)，w≥ 0表示存在鄰接點(diǎn)
//以上兩個(gè)函數(shù)如果圖的存儲(chǔ)結(jié)構(gòu)不同，這倆的實(shí)現(xiàn)方法也不同，時(shí)間耗費(fèi)也不同，后續(xù)的算法會(huì)用鄰接矩陣和鄰接表具體實(shí)現(xiàn)遍歷過程
if(!visited[w])?
{
cout<<v;
visited[w]=true;
EnQueue(Q,w);//v進(jìn)隊(duì)
}
}
}
對(duì)于非連通圖，從另一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)以上過程
【算法分析】
當(dāng)用鄰接矩陣表示圖時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)的時(shí)間復(fù)雜度為O(n^2).(n為圖中頂點(diǎn)數(shù)）
當(dāng)用鄰接表做圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找鄰接點(diǎn)的時(shí)間復(fù)雜度為O(e),其中e為圖中的?邊數(shù)，故當(dāng)以鄰接表做存儲(chǔ)結(jié)構(gòu)時(shí)，BFS遍歷圖的時(shí)間復(fù)雜度為O(n+e),和DFS相同。
兩種遍歷方式的不同之處僅僅在于對(duì)頂點(diǎn)訪問的順序不同。
