圖的遍歷 ——深度優(yōu)先遍歷

深度優(yōu)先搜索（Depth First Search，DFS）是最常見的圖搜索方法之一。

深度優(yōu)先搜索沿著一條路徑一直搜索下去，在無法搜索時，回退到剛剛訪問過的節(jié)點。深度優(yōu)先遍歷是按照深度優(yōu)先搜索的方式對圖進(jìn)行遍歷的。

深度優(yōu)先遍歷的秘籍：后被訪問的節(jié)點，其鄰接點先被訪問。

根據(jù)深度優(yōu)先遍歷的秘籍，后來者先服務(wù)，這可以借助于棧實現(xiàn)。遞歸本身就是使用棧實現(xiàn)的，因此使用遞歸的方法更方便。

【算法步驟】

① 初始化圖中的所有節(jié)點均未被訪問。

② 從圖中的某個節(jié)點v 出發(fā)，訪問v 并標(biāo)記其已被訪問。

③ 依次檢查v 的所有鄰接點w ，如果w 未被訪問，則從w 出發(fā)進(jìn)行深度優(yōu)先遍歷（遞歸調(diào)用，重復(fù)步驟2～3）。

【完美圖解】

例如，一個無向圖如下圖所示，

其深度優(yōu)先遍歷的過程如下所述。

① 初始化所有節(jié)點均未被訪問，visited[i]=false，i =1,2,…,8。

② 從節(jié)點1出發(fā)，標(biāo)記其已被訪問，visited[1]=true。

③ 從節(jié)點1出發(fā)訪問鄰接點2，然后從節(jié)點2出發(fā)訪問節(jié)點4，從節(jié)點4出發(fā)訪問節(jié)點5，從節(jié)點5出發(fā)訪問未被訪問的鄰接點。

④ 回退到剛剛訪問過的節(jié)點4，節(jié)點4也沒有未被訪問的鄰接點，回退到最近訪問過的節(jié)點2，從節(jié)點2出發(fā)訪問下一個未被訪問的鄰接點6。

⑤ 從節(jié)點6出發(fā)訪問未被訪問的鄰接點，回退到剛剛訪問過的節(jié)點2，節(jié)點2沒有未被訪問的鄰接點，回退到最近訪問過的節(jié)點1。

⑥ 從節(jié)點1出發(fā)訪問下一個未被訪問的鄰接點3，從節(jié)點3出發(fā)訪問節(jié)點7，從節(jié)點7出發(fā)訪問節(jié)點8，從節(jié)點8出發(fā)訪問未被訪問的鄰接點。

⑦ 回退到剛剛訪問過的節(jié)點7，節(jié)點7也沒有未被訪問的鄰接點，回退到最近訪問過的節(jié)點3，節(jié)點3也沒有未被訪問的鄰接點，回退到最近訪問過的節(jié)點1，節(jié)點1也沒有未被訪問的鄰接點，遍歷結(jié)束。訪問路徑如下圖所示。

∴ 深度優(yōu)先遍歷序列為1 2 4 5 6 3 7 8。

深度優(yōu)先遍歷經(jīng)過的節(jié)點及邊被稱為深度優(yōu)先生成樹，如下圖所示。

如果深度優(yōu)先遍歷非連通圖，則每一個連通分量都會產(chǎn)生一棵深度優(yōu)先生成樹。

【算法實現(xiàn)】

① 基于鄰接矩陣的深度優(yōu)先遍歷

void DFS_AM(AMGragh G , int v){ //基于鄰接矩陣的深度優(yōu)先遍歷
	cout << G.Vex[v] << "\t";
	visited[v] = true;
	for(int w = 0 ; w < G.vexnum ; w++){ //依次檢查v 的所有鄰接點
		if(G.Edge[v][w] && visited[w]){ //v、w 鄰接并且w 未被訪問
			DFS_AM(G , w); //從節(jié)點w 出發(fā)，遞歸深度優(yōu)先遍歷
		}
	}
}

② 基于鄰接表的深度優(yōu)先遍歷

void DFS_AL(ALGragh G , int v){ //基于鄰接表的深度優(yōu)先遍歷
	AdjNode *p;
	cout << G.Vex[v].data << "\t";
	visited[v] = true;
	p = G.Vex[v].first;
	while(p){ //依次檢查v 的所有鄰接點
		int w = p->v; //w 為 v 的鄰接點
		if(!visited[w]){ //w未被訪問
			DFS_AL(G , w); //從w 出發(fā)，遞歸深度優(yōu)先遍歷
		}
		p = p->next;
	}
}

③ 基于非連通圖的深度優(yōu)先遍歷

void DFS_AL(ALGragh G){ //非連通圖，基于鄰接表的深度優(yōu)先遍歷
	for(int i = 0 ; i < G.vexnum ; i++){ //對非連通圖需要查漏點，檢查未被訪問的節(jié)點
		if(!visited[i]){ //i 未被訪問，以i 為起點再次廣度優(yōu)先遍歷
			DFS_AL(G , i); //基于鄰接表，也可以替換為基于鄰接矩陣DFS_AM(G , i);
		}
	}
}

【算法分析】

深度優(yōu)先遍歷的過程實質(zhì)上是對每個節(jié)點都搜索其鄰接點的過程，圖的存儲方式不同，其算法復(fù)雜度也不同。

① 基于鄰接矩陣的深度優(yōu)先遍歷算法。查找每個節(jié)點的鄰接點需要O (n )時間，共n 個節(jié)點，總的時間復(fù)雜度為O (n^2 )。這里使用了一個遞歸工作棧，空間復(fù)雜度為O (n )

② 基于鄰接表的深度優(yōu)先遍歷算法。查找節(jié)點vi 的鄰接點需要O (d (vi ))時間，d (vi )為vi 的出度，對有向圖而言，所有節(jié)點的出度之和等于邊數(shù)e ；對無向圖而言，所有節(jié)點的度之和等于2e ，因此查找鄰接點的時間復(fù)雜度為O (e )，加上初始化時間O (n )，總的時間復(fù)雜度為O (n +e )。這里使用了一個遞歸工作棧，空間復(fù)雜度為O (n)。

需要注意的是，一個圖的鄰接矩陣是唯一的，因此基于鄰接矩陣的廣度優(yōu)先級遍歷或深度優(yōu)先遍歷的序列也是唯一的，而圖的鄰接表不是唯一的，邊的輸入順序不同，正序或逆序建表都會影響鄰接表中的鄰接點順序，因此基于鄰接表的廣度優(yōu)先遍歷或深度優(yōu)先遍歷的序列不是唯一的。文章來源地址http://www.zghlxwxcb.cn/news/detail-778590.html

到了這里，關(guān)于圖的遍歷 ——深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！