7.5 圖的遍歷

7.5 圖的遍歷

圖的遍歷和樹的遍歷類似，從圖中某一頂點出發訪遍其余頂點，且使每一個頂點僅被訪問一次，這一過程叫做圖的遍歷。分為深度優先遍歷和廣度優先遍歷

7.5.1深度優先遍歷

深度優先遍歷Depth_First_Search)，也稱深度優先搜索，簡稱為DFS。

深度優先搜索其實是一個遞歸的過程，就像是一棵樹的前序遍歷，它從圖中某個頂點V出發，訪問此頂點，然後從V的未被訪問的鄰接點出發深度優先遍歷圖，直至圖中所有和V有路徑相同的頂點都被訪問到。若圖中尚有頂點未被訪問，則令選圖中一個未曾訪問過的頂點作為起始點，重復上述過程，直至圖中的所有頂點都被訪問到為止。

如果是鄰接矩陣，則代碼如下

如果是鄰接表結構，代碼如下：

7.5.2廣度優先遍歷

1、從圖中某個頂點V0出發，首先訪問V0。

2、依次訪問V0的各個未被訪問過的鄰節點。

3、分別從這些鄰接點出發，依次訪問它們的各個未被訪問過的鄰接點。

本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1293328