1 引言
周遊是指從某個節點出發，按照一定的的搜尋路線，依次通路對資料結構中的全部節點，且每個節點僅通路一次。
在二叉樹基礎中，介紹了對于樹的周遊。樹的周遊是指從根節點出發，按照一定的通路規則，依次通路樹的每個節點資訊。樹的周遊過程，根據通路規則的不同主要分為四種周遊方式：
（1）先序周遊
（2）中序周遊
（3）後序周遊
（4）層次周遊
類似的，圖的周遊是指，從給定圖中任意指定的頂點（稱為初始點）出發，按照某種搜尋方法沿着圖的邊通路圖中的所有頂點，使每個頂點僅被通路一次，這個過程稱為圖的周遊。周遊過程中得到的頂點序列稱為圖周遊序列。
圖的周遊過程中，根據搜尋方法的不同，又可以劃分為兩種搜尋政策：
（1）深度優先搜尋（DFS，Depth First Search）
（2）廣度優先搜尋（BFS，Breadth First Search）
2 深度優先搜尋
2.1 算法思想
深度優先搜尋思想：假設初始狀态是圖中所有頂點均未被通路，則從某個頂點v出發，首先通路該頂點，然後依次從它的各個未被通路的鄰接點出發深度優先搜尋周遊圖，直至圖中所有和v有路徑相通的頂點都被通路到。若此時尚有其他頂點未被通路到，則另選一個未被通路的頂點作起始點，重複上述過程，直至圖中所有頂點都被通路到為止。
2.2 算法特點
深度優先搜尋是一個遞歸的過程。首先，標明一個出發點後進行周遊，如果有鄰接的未被通路過的節點則繼續前進。若不能繼續前進，則回退一步再前進，若回退一步仍然不能前進，則連續回退至可以前進的位置為止。重複此過程，直到所有與標明點相通的所有頂點都被周遊。
深度優先搜尋是遞歸過程，帶有回退操作，是以需要使用棧存儲通路的路徑資訊。當通路到的目前頂點沒有可以前進的鄰接頂點時，需要進行出棧操作，将目前位置回退至出棧元素位置。
2.3 圖解過程
2.3.1 無向圖深度優先搜尋
以圖2.3.1.1中所示無向圖說明深度優先搜尋周遊過程。
圖2.3.1.1
（1）首先選取頂點A為起始點，輸出A頂點資訊，且将A入棧，并标記A為已通路頂點。
（2）A的鄰接頂點有C、D、F，從中任意選取一個頂點前進。這裡我們選取C頂點為前進位置頂點。輸出C頂點資訊，将C入棧，并标記C為已通路頂點。目前位置指向頂點C。
（3）頂點C的鄰接頂點有A、D和B，此時A已經标記為已通路頂點，是以不能繼續通路。從B或者D中選取一個頂點前進，這裡我們選取B頂點為前進位置頂點。輸出B頂點資訊，将B入棧，标記B頂點為已通路頂點。目前位置指向頂點B。
（4）頂點B的鄰接頂點隻有C、E，C已被标記，不能繼續通路，是以選取E為前進位置頂點，輸出E頂點資訊，将E入棧，标記E頂點，目前位置指向E。
（5）頂點E的鄰接頂點均已被标記，此時無法繼續前進，則需要進行回退。将目前位置回退至頂點B，回退的同時将E出棧。
（6）頂點B的鄰接頂點也均被标記，需要繼續回退，目前位置回退至C，回退同時将B出棧。
（7）頂點C可以前進的頂點位置為D，則輸出D頂點資訊，将D入棧，并标記D頂點。目前位置指向頂點D。
（8）頂點D沒有前進的頂點位置，是以需要回退操作。将目前位置回退至頂點C，回退同時将D出棧。
（9）頂點C沒有前進的頂點位置，繼續回退，将目前位置回退至頂點A，回退同時将C出棧。
（10）頂點A前進的頂點位置為F，輸出F頂點資訊，将F入棧，并标記F。将目前位置指向頂點F。
（11）頂點F的前進頂點位置為G，輸出G頂點資訊，将G入棧，并标記G。将目前位置指向頂點G。
（12）頂點G沒有前進頂點位置，回退至F。目前位置指向F，回退同時将G出棧。
（13）頂點F沒有前進頂點位置，回退至A，目前位置指向A，回退同時将F出棧。
（14）頂點A沒有前進頂點位置，繼續回退，棧為空，則以A為起始的周遊結束。若圖中仍有未被通路的頂點，則選取未通路的頂點為起始點，繼續執行此過程。直至所有頂點均被通路。
（15）采用深度優先搜尋周遊順序為A->C->B->E->D->F->G。
2.3.2 有向圖深度優先搜尋
以圖2.3.2.1中所示有向圖說明深度優先搜尋周遊過程。
圖2.3.2.1 有向圖
（1）以頂點A為起始點，輸出A，将A入棧，并标記A。目前位置指向A。
（2）以A為尾的邊隻有1條，且邊的頭為頂點B，則前進位置為頂點B，輸出B，将B入棧，标記B。目前位置指向B。
（3）頂點B可以前進的位置有C與F，選取F為前進位置，輸出F，将F入棧，并标記F。目前位置指向F。
（4）頂點F的前進位置為G，輸出G，将G入棧，并标記G。目前位置指向G。
（5）頂點G沒有可以前進的位置，則回退至F，将F出棧。目前位置指向F。
（6）頂點F沒有可以前進的位置，繼續回退至B，将F出棧。目前位置指向B。
（7）頂點B可以前進位置為C和E，選取E，輸出E，将E入棧，并标記E。目前位置指向E。
（8）頂點E的前進位置為D，輸出D，将D入棧，并标記D。目前位置指向D。
（9）頂點D的前進位置為C，輸出C，将C入棧，并标記C。目前位置指向C。
（10）頂點C沒有前進位置，進行回退至D，回退同時将C出棧。
（11）繼續執行此過程，直至棧為空，以A為起始點的周遊過程結束。若圖中仍有未被通路的頂點，則選取未通路的頂點為起始點，繼續執行此過程。直至所有頂點均被通路。
2.4 算法分析
當圖采用鄰接矩陣存儲時，由于矩陣元素個數為n^2，是以時間複雜度就是O(n^2)。
當圖采用鄰接表存儲時，鄰接表中隻是存儲了邊結點(e條邊，無向圖也隻是2e個結點)，加上表頭結點為n（也就是頂點個數），是以時間複雜度為O(n+e)。
3 廣度優先搜尋
3.1 算法思想
廣度優先搜尋思想：從圖中某頂點v出發，在通路了v之後依次通路v的各個未曾通路過的鄰接點，然後分别從這些鄰接點出發依次通路它們的鄰接點，并使得“先被通路的頂點的鄰接點先于後被通路的頂點的鄰接點被通路，直至圖中所有已被通路的頂點的鄰接點都被通路到。如果此時圖中尚有頂點未被通路，則需要另選一個未曾被通路過的頂點作為新的起始點，重複上述過程，直至圖中所有頂點都被通路到為止。
3.2 算法特點
廣度優先搜尋類似于樹的層次周遊，是按照一種由近及遠的方式通路圖的頂點。在進行廣度優先搜尋時需要使用隊列存儲頂點資訊。
3.3 圖解過程
3.3.1 無向圖的廣度優先搜尋
例如：圖3.3.1.1所示的無向圖，采用廣度優先搜尋過程。
圖3.3.1.1
（1）選取A為起始點，輸出A，A入隊列，标記A，目前位置指向A。
（2）隊列頭為A，A出隊列。A的鄰接頂點有B、E，輸出B和E，将B和E入隊，并标記B、E。目前位置指向A。
（3）隊列頭為B，B出隊列。B的鄰接頂點有C、D，輸出C、D，将C、D入隊列，并标記C、D。目前位置指向B。
（4）隊列頭為E，E出隊列。E的鄰接頂點有D、F，但是D已經被标記，是以輸出F，将F入隊列，并标記F。目前位置指向E。
（5）隊列頭為C，C出隊列。C的鄰接頂點有B、D，但B、D均被标記。無元素入隊列。目前位置指向C。
（6）隊列頭為D，D出隊列。D的鄰接頂點有B、C、E，但是B、C、E均被标記，無元素入隊列。目前位置指向D。
（7）隊列頭為F，F出隊列。F的鄰接頂點有G、H，輸出G、H，将G、H入隊列，并标記G、H。目前位置指向F。
（8）隊列頭為G，G出隊列。G的鄰接頂點有F，但F已被标記，無元素入隊列。目前位置指向G。
（9）隊列頭為H，H出隊列。H的鄰接頂點有F，但F已被标記，無元素入隊列。目前位置指向H。
img
（10）隊列空，則以A為起始點的周遊結束。若圖中仍有未被通路的頂點，則選取未通路的頂點為起始點，繼續執行此過程。直至所有頂點均被通路。
3.3.2 有向圖的廣度優先搜尋
以圖3.3.2.1所示的有向圖為例進行廣度優先搜尋。
3.3.2.1
（1）選取A為起始點，輸出A，将A入隊列，标記A。
（2）隊列頭為A，A出隊列。以A為尾的邊有兩條，對應的頭分别為B、C，則A的鄰接頂點有B、C。輸出B、C，将B、C入隊列，并标記B、C。
（3）隊列頭為B，B出隊列。B的鄰接頂點為C，C已經被标記，是以無新元素入隊列。
（4）隊列頭為C，C出隊列。C的鄰接頂點有E、F。輸出E、F，将E、F入隊列，并标記E、F。
（5）隊列頭為E，E出隊列。E的鄰接頂點有G、H。輸出G、H，将G、H入隊列，并标記G、H。
（6）隊列頭為F，F出隊列。F無鄰接頂點。
（7）隊列頭為G，G出隊列。G無鄰接頂點。
（8）隊列頭為H，H出隊列。H鄰接頂點為E，但是E已被标記，無新元素入隊列。
（9）隊列為空，以A為起始點的周遊過程結束，此時圖中仍有D未被通路，則以D為起始點繼續周遊。選取D為起始點，輸出D，将D入隊列，标記D。
（10）隊列頭為D，D出隊列，D的鄰接頂點為B，B已被标記，無新元素入隊列。
（11）隊列為空，且所有元素均被通路，廣度優先搜尋周遊過程結束。廣度優先搜尋的輸出序列為：A->B->E->C->D->F->G->H。
3.4 算法分析
假設圖有V個頂點，E條邊，廣度優先搜尋算法需要搜尋V個節點，時間消耗是O(V)，在搜尋過程中，又需要根據邊來增加隊列的長度，于是這裡需要消耗O(E)，總得來說，效率大約是O(V+E)。
4 總結
圖的周遊主要就是這兩種周遊思想，深度優先搜尋使用遞歸方式，需要棧結構輔助實作。廣度優先搜尋需要使用隊列結構輔助實作。在周遊過程中可以看出，對于連通圖，從圖的任意一個頂點開始深度或廣度優先周遊一定可以通路圖中的所有頂點，但對于非連通圖，從圖的任意一個頂點開始深度或廣度優先周遊并不能通路圖中的所有頂點。