這節(jié)，我們來(lái)看看一下什么了，來(lái)看看圖的遍歷吧！

首先，搞清楚，圖的遍歷的基本的含義了。

圖的遍歷是指從圖中的某個(gè)頂點(diǎn)出發(fā)，按照某種順序訪問(wèn)圖中的每個(gè)頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問(wèn)一次且僅一次。圖的遍歷與樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，并且圖的許多其他操作都是建立在遍歷操作的基礎(chǔ)之上的。遍歷示意圖，如圖所示：

然而，圖的遍歷要比樹的遍歷復(fù)雜得多。這是因?yàn)閳D中的頂點(diǎn)之間是多對(duì)多的關(guān)系，圖中的任何一個(gè)頂點(diǎn)都可能和其它的頂點(diǎn)相鄰接。所以，在訪問(wèn)了某個(gè)頂點(diǎn)之后， 從該頂點(diǎn)出發(fā)， 可能沿著某條路徑遍歷之后， 又回到該頂點(diǎn)上。 例如，在下圖中，由于圖中存在回路，因此在訪問(wèn)了 A、B、C、D、E之后，沿著邊<E,A>為圖中頂點(diǎn)的數(shù)目。數(shù)組中元素的初始值全為 0，表示頂點(diǎn)都沒有被訪問(wèn)過(guò)，如果頂點(diǎn)vi 被訪問(wèn)，visited[i-1]為 1。

圖的遍歷有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式，它們對(duì)圖和網(wǎng)都適用。 

首先，介紹了一些優(yōu)先遍歷。

圖的深度優(yōu)先遍歷（Depth_First Search）類似于樹的先序遍歷，是樹的先序遍歷的推廣。

我們先回顧一下樹的先序遍歷，如圖所示：

他先序遍歷結(jié)果是ABDEFCFG。

那圖的圖的深度優(yōu)先遍歷，究竟是那樣的。

假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問(wèn)過(guò)， 則深度優(yōu)先遍歷可從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從v的未被訪問(wèn)的鄰接頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v路徑相通的頂點(diǎn)都被遍歷過(guò)。若此時(shí)圖中尚有未被訪問(wèn)的頂點(diǎn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)到為止。

下圖(a)所示的無(wú)向圖的深度優(yōu)先遍歷的過(guò)程如下圖(b)所示。假設(shè)從頂點(diǎn) v1出發(fā)，在訪問(wèn)了頂點(diǎn) v1之后，選擇鄰接頂點(diǎn) v2，因?yàn)?v2未被訪問(wèn)過(guò)，所以從 v2出發(fā)進(jìn)行深度優(yōu)先遍歷。依次類推，接著從 v4、v8、v5出發(fā)進(jìn)行深度優(yōu)先遍歷。當(dāng)訪問(wèn)了 v5之后，由于 v5的鄰接頂點(diǎn) v2和 v8都已被訪問(wèn)，所以遍歷退回到 v8。由于同樣的理由，遍歷繼續(xù)退回到 v4、v2 直到 v1。由于 v1 的另一個(gè)鄰接頂點(diǎn) v3未被訪問(wèn)，所以又從 v3開始進(jìn)行深度優(yōu)先遍歷，這樣得到該圖的深度優(yōu)先遍歷的頂點(diǎn)序列v1→v2→v4→v8→v5→v3→v6→v7。

顯然，這是一個(gè)遞歸的過(guò)程。下面以無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)為例來(lái)實(shí)現(xiàn)圖的深度優(yōu)先遍歷算法。在類中增設(shè)了一個(gè)整型數(shù)組的成員字段visited，它的初始值全為 0， 表示圖中所有的頂點(diǎn)都沒有被訪問(wèn)過(guò)。 如果頂點(diǎn)vi被訪問(wèn)， visited[i-1]為1。并且，把該算法作為無(wú)向圖的鄰接表類 GraphAdjList<T>的成員方法。

由于增設(shè)了成員字段 visited，所以在類的構(gòu)造器中添加以下代碼。

public GraphAdjList(Node<T>[] nodes)
{

adjList = new VexNode<T>[nodes.Length];
for (int i = 0; i < nodes.Length; ++i )
{
adjList[i].Data = nodes[i];
adjList[i].FirstAdj = null;
}

//以下為添加的代碼

//所有的結(jié)點(diǎn)，都沒有訪問(wèn)過(guò)。 都賦值為0
visited = new int[adjList.Length];
for (int i = 0; i < visited.Length; ++i)
{
visited[i] = 0;
}
}

由于，他是循環(huán)遍歷，他的時(shí)間的復(fù)雜度是O(n).

無(wú)向圖的深度優(yōu)先遍歷算法的實(shí)現(xiàn)如下：   
public void DFS()
{
for (int i = 0; i < visited.Length; ++i)
{
if (visited[i] == 0)
{
DFSAL(i);
}
}
}

//從某個(gè)頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷
public void DFSAL(int i)
{
visited[i] = 1;
adjListNode<T> p = adjList[i].FirstAdj;

while (p != null)
{
if (visited[p.Adjvex] == 0)
{
DFSAL(p.Adjvex);
}

p = p.Next;
}
}

分析上面的算法，在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS方法，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)記成已被訪問(wèn)，就不再?gòu)乃霭l(fā)進(jìn)行遍歷。因此，遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接頂點(diǎn)的過(guò)程。 其時(shí)間復(fù)雜度取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)圖采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O(n2)，其中，n為圖的頂點(diǎn)數(shù)。而以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O(e)，其中，e為圖中邊或弧的數(shù)目。因此，當(dāng)以鄰接表作為存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先遍歷圖的時(shí)間復(fù)雜度為O(n+e)。具體情況，如圖所示：

下面介紹廣度遍歷。

圖的廣度優(yōu)先遍歷（Breadth_First Search）類似于樹的層序遍歷。 我們回顧一下樹的層次遍歷，如圖所示：

樹的層次遍歷結(jié)果為ABCDEFG。

那圖的光序遍歷為

假設(shè)從圖中的某個(gè)頂點(diǎn) v 出發(fā)，訪問(wèn)了 v 之后，依次訪問(wèn) v 的各個(gè)未曾訪問(wèn)的鄰接頂點(diǎn)。然后分別從這些鄰接頂點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接頂點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接頂點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接頂點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接頂點(diǎn)都被訪問(wèn)。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中未被訪問(wèn)的頂點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有的頂點(diǎn)都被訪問(wèn)為止。換句話說(shuō)，廣度優(yōu)先遍歷圖的過(guò)程是以某個(gè)頂點(diǎn) v 作為起始點(diǎn)，由近至遠(yuǎn)，依次訪問(wèn)和 v 有路徑相通且路徑長(zhǎng)度為 1，2，…的頂點(diǎn)。

圖(a)所示的無(wú)向圖的廣度優(yōu)先遍歷的過(guò)程如圖(b)所示。假設(shè)從頂點(diǎn) v1開始進(jìn)行廣度優(yōu)先遍歷，首先訪問(wèn)頂點(diǎn) v1和它的鄰接頂點(diǎn) v2和 v3，然后依次訪問(wèn) v2 的鄰接頂點(diǎn) v4 和 v5，以及 v3 的鄰接頂點(diǎn) v6 和 v7，最后訪問(wèn) v4b的鄰接頂點(diǎn) v8。由于這些頂點(diǎn)的鄰接頂點(diǎn)都已被訪問(wèn)，并且圖中所有頂點(diǎn)都已被訪問(wèn)，由此完成了圖的遍歷，得到的頂點(diǎn)訪問(wèn)序列為：v1→v2→v3→v4→v5→v6→v7→v8，其遍歷過(guò)程如下圖(b)所示。

和深度優(yōu)先遍歷類似，在廣度優(yōu)先遍歷中也需要一個(gè)訪問(wèn)標(biāo)記數(shù)組，我們采用與深度優(yōu)先遍歷同樣的數(shù)組。并且，為了順序訪問(wèn)路徑長(zhǎng)度為 1，2，…的頂點(diǎn)，需在算法中附設(shè)一個(gè)隊(duì)列來(lái)存儲(chǔ)已被訪問(wèn)的路徑長(zhǎng)度為 1，2，…的頂點(diǎn)。 以鄰接表作為存儲(chǔ)結(jié)構(gòu)的無(wú)向圖的廣度優(yōu)先遍歷算法的實(shí)現(xiàn)如下， 隊(duì)列是循環(huán)順序隊(duì)列。

public void BFS()
{
for (int i = 0; i < visited.Length; ++i)
{

//所有結(jié)點(diǎn)的都沒有遍歷
if (visited[i] == 0)
{
BFSAL(i);
}
}
}

//從某個(gè)頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷
public void BFSAL(int i)
{
visited[i] = 1;
CSeqQueue<int> cq = new CSeqQueue<int>(visited.Length);

while (!cq.IsEmpty())
{
int k = cq.Out();
adjListNode<T> p = adjList[k].FirstAdj;

while (p != null)
{
if (visited[p.Adjvex] == 0)
{
visited[p.Adjvex] = 1;
cq.In(p.Adjvex);
}

p = p.Next;
}
}
}

算法的復(fù)雜度是O(n2),具體情況，如圖所示：

cq.In(i);

分析上面的算法，每個(gè)頂點(diǎn)至多入隊(duì)列一次。遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧查找鄰接頂點(diǎn)的過(guò)程，因此，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度與深度優(yōu)先遍歷相同，兩者的不同之處在于對(duì)頂點(diǎn)的訪問(wèn)順序不同。

這就是圖的遍歷，極其算法的實(shí)現(xiàn)，下屆，我們討論圖的應(yīng)用。