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

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

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

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

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

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

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

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

他先序遍歷結果是ABDEFCFG。

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

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

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

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

由于增設了成員字段 visited，所以在類的構造器中添加以下代碼。

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;
}

//以下為添加的代碼

//所有的結點，都沒有訪問過。 都賦值為0
visited = new int[adjList.Length];
for (int i = 0; i < visited.Length; ++i)
{
visited[i] = 0;
}
}

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

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

//從某個頂點出發(fā)進行深度優(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;
}
}

分析上面的算法，在遍歷圖時，對圖中每個頂點至多調用一次DFS方法，因為一旦某個頂點被標記成已被訪問，就不再從它出發(fā)進行遍歷。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接頂點的過程。 其時間復雜度取決于所采用的存儲結構。當圖采用鄰接矩陣作為存儲結構時，查找每個頂點的鄰接頂點的時間復雜度為O(n2)，其中，n為圖的頂點數(shù)。而以鄰接表作為圖的存儲結構時，查找鄰接頂點的時間復雜度為O(e)，其中，e為圖中邊或弧的數(shù)目。因此，當以鄰接表作為存儲結構時，深度優(yōu)先遍歷圖的時間復雜度為O(n+e)。具體情況，如圖所示：

下面介紹廣度遍歷。

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

樹的層次遍歷結果為ABCDEFG。

那圖的光序遍歷為

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

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

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

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

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

//從某個頂點出發(fā)進行廣度優(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;
}
}
}

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

cq.In(i);

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

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