廣度優先java

㈠ 深度優先遍歷與廣度優先遍歷的區別

一、指代不同

1、深度優先遍歷：是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

2、廣度優先遍歷：系統地展開並檢查圖中的所有節點，以找尋結果。

二、特點不同

1、深度優先遍歷：所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。

2、廣度優先遍歷：並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

三、演算法不同

1、深度優先遍歷：把根節點壓入棧中。每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。

2、廣度優先遍歷：把根節點放到隊列的末尾。每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。

㈡ 數據結構題目，廣度優先和深度優先

（一）深度優先搜索的特點是：

（1）從上面幾個實例看出，可以用深度優先搜索的方法處理的題目是各種
各樣的。
有的搜索深度是已知和固定的，如例題2-4，2-5，2-6；有的是未知的，如例題2-7、例題2-8；
有的搜索深度是有限制的，但達到目標的深度是不定的。
但也看到，無論問題的內容和性質以及求解要求如何不同，它們的程序結構
都是相同的，即都是深度優先演算法（一）和深度優先演算法（二）中描述的演算法結
構，不相同的僅僅是存儲結點數據結構和產生規則以及輸出要求。
（2）深度優先搜索法有遞歸以及非遞歸兩種設計方法。一般的，當搜索深度較小、問題遞歸方式比較明顯時，用遞歸方法設計好，它可以使得程序結構更簡捷易懂。當搜索深度較大時，如例題2-5、2-6。當數據量較大時，由於系統堆棧容量的限制，遞歸容易產生溢出，用非遞歸方法設計比較好。
（3）深度優先搜索方法有廣義和狹義兩種理解。廣義的理解是，只要最新產生的結點（即深度最大的結點）先進行擴展的方法，就稱為深度優先搜索方法。在這種理解情況下，深度優先搜索演算法有全部保留和不全部保留產生的結點的兩種情況。而狹義的理解是，僅僅只保留全部產生結點的演算法。本書取前一種廣義的理解。
不保留全部結點的演算法屬於一般的回溯演算法范疇。
保留全部結點的演算法，
實際上是在資料庫中產生一個結點之間的搜索樹，
因此也屬於圖搜索演算法的范疇。
（4）不保留全部結點的深度優先搜索法，由於把擴展望的結點從資料庫中彈出刪除，這樣，一般在資料庫中存儲的結點數就是深度值，因此它佔用的空間較少，所以，當搜索樹的結點較多，用其他方法易產生內存溢出時，深度優先搜索不失為一種有效的演算法。
（5）從輸出結果可看出，深度優先搜索找到的第一個解並不一定是最優解。例如例題2-8得最優解為13，但第一個解卻是17。如果要求出最優解的話，一種方法將是後面要介紹的動態規劃法，另一種方法是修改原演算法：把原輸出過程的地方改為記錄過程，即記錄達到當前目標的路徑和相應的路程值，並與前面已記錄的值進行比較，保留其中最優的，等全部搜索完成後，才把保留的最優解輸出。
二、廣度優先搜索法的顯著特點是：
（1）在產生新的子結點時，深度越小的結點越先得到擴展，即先產生它的子結點。為使演算法便於實現，存放結點的資料庫一般用隊列的結構。
（2）無論問題性質如何不同，利用廣度優先搜索法解題的基本演算法是相同的，但資料庫中每一結點內容，產生式規則，根據不同的問題，有不同的內容和結構，就是同一問題也可以有不同的表示方法。
（3）當結點到跟結點的費用（有的書稱為耗散值）和結點的深度成正比時，特別是當每一結到根結點的費用等於深度時，用廣度優先法得到的解是最優解，但如果不成正比，則得到的解不一定是最優解。這一類問題要求出最優解，一種方法是使用後面要介紹的其他方法求解，另外一種方法是改進前面深度（或廣度）優先搜索演算法：找到一個目標後，不是立即退出，而是記錄下目標結點的路徑和費用，如果有多個目標結點，就加以比較，留下較優的結點。把所有可能的路徑
都搜索完後，才輸出記錄的最優路徑。
（4）廣度優先搜索演算法，一般需要存儲產生的所有結點，占的存儲空間要比深度優先大得多，因此程序設計中，必須考慮溢出和節省內存空間得問題。
（5）比較深度優先和廣度優先兩種搜索法，廣度優先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優先搜索演算法法要快些。
總之，一般情況下，深度優先搜索法佔內存少但速度較慢，廣度優先搜索演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。因此在選擇用哪種演算法時，要綜合考慮。決定取捨

㈢ 深度優先遍歷怎麼修改為廣度優先遍歷

假設初始狀態是圖中所有頂點均未被訪問
從某個頂點出發，然後依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到。
若此時尚有其他頂點未被訪問到，則另選一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。
實現深度優先遍歷的關鍵在於回溯。所謂「回溯」，就是自後往前，追溯曾經走過的路徑。

演算法特點
深度優先搜索是一個遞歸的過程。

首先，選定一個出發點後進行遍歷，如果有鄰接的未被訪問過的節點則繼續前進。
若不能繼續前進，則回退一步再前進
若回退一步仍然不能前進，則連續回退至可以前進的位置為止。
重復此過程，直到所有與選定點相通的所有頂點都被遍歷。
深度優先搜索是遞歸過程，帶有回退操作，因此需要使用棧存儲訪問的路徑信息。當訪問到的當前頂點沒有可以前進的鄰接頂點時，需要進行出棧操作，將當前位置回退至出棧元素位置。

圖解過程
無向圖的深度優先遍歷
以下圖所示無向圖說明深度優先搜索遍歷過程。

實例一

在這里插入圖片描述
假設我們從頂點A開始，遍歷過程中的每一步如下：

首先選取頂點A為起始點，輸出A頂點信息，而且將A入棧，並且標記A為已訪問頂點
A的鄰接頂點有C、D、F，從中任意選取一個頂點前進。這里我們選取C為前進位置頂點。輸出C頂點信息，將C入棧，並標記C為已訪問頂點。當前位置指向頂點C
頂點C的鄰接頂點有A、D、B，此時A已經標記為已訪問頂點，因此不能繼續訪問。從B或者D中選取一個頂點前進，這里我們選取B頂點為前進位置頂點。輸出B頂點信息，將B入棧，標記B頂點為已訪問頂點。當前位置指向B
頂點B的鄰接頂點只有C、E，C已被標記，不能繼續訪問，因此選取E為前進位置頂點，輸出E頂點信息，將E入棧，標記E頂點，當前位置指向E。
頂點E的鄰接頂點均已被標記，此時無法繼續前進，則需要進行回退。將當前位置回退至頂點B，回退的同時將E出棧。
頂點B的鄰接頂點也均被標記，需要繼續回退，當前位置回退至C，回退同時將B出棧。
頂點C可以前進的頂點位置為D，則輸出D頂點信息，將D入棧，並標記D頂點。當前位置指向頂點D。
頂點D沒有前進的頂點位置，因此需要回退操作。將當前位置回退至頂點C，回退同時將D出棧。
頂點C沒有前進的頂點位置，繼續回退，將當前位置回退至頂點A，回退同時將C出棧。
頂點A前進的頂點位置為F，輸出F頂點信息，將F入棧，並標記F。將當前位置指向頂點F。
頂點F的前進頂點位置為G，輸出G頂點信息，將G入棧，並標記G。將當前位置指向頂點G。
頂點G沒有前進頂點位置，回退至F。當前位置指向F，回退同時將G出棧。
頂點F沒有前進頂點位置，回退至A，當前位置指向A，回退同時將F出棧。
頂點A沒有前進頂點位置，繼續回退，棧為空，則以A為起始的遍歷結束。若圖中仍有未被訪問的頂點，則選取未訪問的頂點為起始點，繼續執行此過程。直至所有頂點均被訪問。
採用深度優先搜索遍歷順序為A->C->B->E->D->F->G。
利用一個臨時棧來實現回溯，最終遍歷完所有頂點

問題：

（1）必須選取A作為遍歷的起點嗎？

不是原則我們可以選取任何一個節點作為起點進行開始，進行深度優先遍歷
（2）當有多個鄰接點未被訪問時，可以選取哪個作為下一個起點呢？

隨便哪個都行。
當有多個臨界點可選時，相當於走迷宮時出現了多個分叉路口，我們只要不走之前走過的路就行了。所以關鍵在於標記哪個點是否已經走過。不過，一般我們會定義一個原則，必須不碰重復點的情況下，選擇走左/右手第一條沒有走過的路，這樣比較好理解
兩個原則：

右手原則： 在沒有碰到重復頂點的情況下，分叉路口始終是向右手邊走，每路過一個頂點就做一個記號
左手原則： 在沒有碰到重復頂點的情況下，分叉路口始終是向左手邊走，每路過一個頂點就做一個記號
下面以右手原則進行深度優先遍歷再看個例子

實例二

在這里插入圖片描述

原則我們可以選取任何一個節點作為起點進行開始，進行深度優先遍歷，假設我們從頂點A開始，遍歷過程中的每一步如下：

第一步：從頂點A開始，將頂點A標記為已訪問節點

第二步：根據右手原則，訪問頂點B，並將B標記為已訪問節點

第三步：右手原則，訪問頂點C

第四步：右手原則，訪問頂點D

第五步：右手原則，訪問頂點E

第六步：右手原則，訪問頂點F
在這里插入圖片描述

第七步：右手原則，應該先訪問頂點F的鄰接頂點A，但發現A已經被訪問，則訪問A之外的最右側頂點G
在這里插入圖片描述

第八步：右手原則，先訪問頂點B，頂點B已經被訪問；在訪問頂點D，頂點D已經被訪問；最後訪問頂點H
在這里插入圖片描述

第九步：發現頂點H的鄰接頂點均已被訪問，則退回到頂點G;

第十步：頂點G的鄰接頂點均已被訪問，則退回到頂點F；

第十一步：頂點F的鄰接頂點已被訪問，則退回到頂點E；

第十二步：頂點E的鄰接頂點均已被訪問，則退回到頂點D；

第十三步：頂點D的鄰接頂點I尚未被訪問，則訪問頂點I；
在這里插入圖片描述

第十四步：頂點I的鄰接頂點均已被訪問，則退回到頂點D;

第十五步：頂點D的鄰接頂點均已被訪問，退回到頂點C；

第十六步：頂點C的鄰接頂點均已被訪問，則退回到頂點B；

頂點B的鄰接頂點均已被訪問，則退回到頂點A，頂點A為起始頂點，深度優先搜索結束。

圖的深度優先搜索和二叉樹的前序遍歷、中序遍歷、後序遍歷本質上均屬於一類方法。

上面的過程可以總結為以下3個步驟：

首先選定一個未被訪問過的頂點V作為起始頂點（或者訪問指定的起始頂點V），並將其標記為已訪問

然後搜索與頂點V鄰接的所有頂點，判斷這些頂點是否被訪問過，如果有未被訪問過的頂點W；再選取與頂點W鄰接的未被訪問過的一個頂點並進行訪問，依次重復進行。當一個頂點的所有的鄰接頂點都被訪問過時，則依次回退到最近被訪問的頂點。若該頂點還有其他鄰接頂點未被訪問，則從這些未被訪問的頂點中取出一個並重復上述過程，直到與起始頂點V相鄰接的所有頂點都被訪問過為止。

若此時圖中依然有頂點未被訪問，則再選取其中一個頂點作為起始頂點並進行遍歷，轉（2）。反之，則遍歷結束。

有向圖深度優先搜索
在這里插入圖片描述
（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，將G出棧。當前位置指向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為起始點的遍歷過程結束。若圖中仍有未被訪問的頂點，則選取未訪問的頂點為起始點，繼續執行此過程。直至所有頂點均被訪問。

性能分析
當圖採用鄰接矩陣存儲時，由於矩陣元素個數為n 2 n^2n
2
，因此時間復雜度就是O ( n 2 ) O(n^2)O(n
2
)

當圖採用鄰接表存儲時，鄰接表中只是存儲了邊結點(e條邊，無向圖也只是2e個結點)，加上表頭結點為n（也就是頂點個數），因此時間復雜度為O(n+e)。

廣度優先搜索
演算法思想
思想：
從圖中某頂點v出發，在訪問了v之後依次訪問v的各個未曾訪問過的鄰接點
然後分別從這些鄰接點出發依次訪問它們的鄰接點，並使得「先被訪問的頂點的鄰接點先於後被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。
如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。
實現廣度優先遍歷的關鍵在於回放。
回溯與重放是完全相反的過程。

仍然以剛才的圖為例，按照廣度優先遍歷的思想

我們先遍歷頂點0，然後遍歷其鄰接點1、3
接下來我們要遍歷更外圍的頂點，可是如何找到這些更外圍的頂點呢？我們需要把剛才遍歷過的頂點1,3按照順序回顧一遍，從頂點1發現了鄰接點2，從頂點3發現了鄰接點4。於是得到了順序2,4
再把剛才遍歷過的頂點2，4按照順序回顧一遍，分別得到鄰接點5，6
再把剛才遍歷過的頂點5，7按照順序回顧一遍，分別得到鄰接點7，7。7隻需要列印一次，所以我們需要一個東西來標記當前頂點是否已經訪問過
在這里插入圖片描述

像這樣把遍歷過的頂點按照之前的遍歷順序重新回顧，就叫做重放。

同樣的，要實現重放也需要額外的存儲空間，可以利用隊列的先入先出特性來實現。
另外，還需要標記某個點是否已經被訪問過，可以用數組、set等來實現
可以看出，廣度優先搜索它其實就是一種「地毯式」層層推進的搜索策略，即先查找離起始頂點最近的，然後是次近的，依次往外搜索。

演算法特點
廣度優先搜索類似於樹的層次遍歷，是按照一種由近及遠的方式訪問圖的頂點。在進行廣度優先搜索時需要使用隊列存儲頂點信息。

圖解過程
無向圖的廣度優先搜索
在這里插入圖片描述

（1）選取A為起始點，輸出A，A入隊列，標記A，當前位置指向A。

在這里插入圖片描述

（2）隊列頭為A，A出隊列。A的鄰接頂點有B、E，輸出B和E，並將B和E入隊，以及標記B、E為已訪問。當前位置指向B。
在這里插入圖片描述
（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。
在這里插入圖片描述
（10）隊列空，則以A為起始點的遍歷結束。若圖中仍有未被訪問的頂點，則選取未訪問的頂點為起始點，繼續執行此過程。直至所有頂點均被訪問。

有向圖的廣度優先搜索
在這里插入圖片描述
（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–>C->E->F->G->H->D。

演算法分析
我們來看下，廣度優先搜索的時間、空間復雜度是多少呢？假設圖有V個頂點，E條邊

每個頂點都需要進出一遍隊列，每個邊都會被訪問一次。所以，廣度優先搜索的時間復雜度是O(V+E)。當然，對於一個連通圖來說，也就是說一個圖中的所有頂點都是連通的，，E 肯定要大於等於 V-1，所以，廣度優先搜索的時間復雜度也可以簡寫為 O(E)
廣度優先搜索的空間消耗主要在幾個輔助變數 visited 數組、queue 隊列上。這兩個存儲空間的大小都不會超過頂點的個數，所以空間復雜度是 O(V)。
總結
圖的遍歷主要就是這兩種遍歷思想，深度優先搜索使用遞歸方式，需要棧結構輔助實現。廣度優先搜索需要使用隊列結構輔助實現。在遍歷過程中可以看出，

對於連通圖，從圖的任意一個頂點開始深度或廣度優先遍歷一定可以訪問圖中的所有頂點
對於非連通圖，從圖的任意一個頂點開始深度或廣度優先遍歷並不能訪問圖中的所有頂點。
實現
深度優先遍歷
當圖採用鄰接矩陣進行存儲，遞歸的實現操作：

#define MAXVBA 100
#define INFINITY 65536

typedef struct {
char vexs[MAXVBA];
int arc[MAXVBA][MAXVBA];
int numVertexes, numEdges;
} MGraph;

// 鄰接矩陣的深度有限遞歸演算法

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean; // 這里我們定義Boolean為布爾類型，其值為TRUE或FALSE
Boolean visited[MAX]; // 訪問標志的數組

void DFS(MGraph G, int i){
visited[i] = TRUE;
printf("%c", G.vexs[i]);

for (int j = 0; j < G.numVertexes; ++j) {
if (G.arc[i][j] == 1 && !visited[j]){
DFS(G, j); // 對為訪問的鄰接頂點遞歸調用
}
}
}

// 鄰接矩陣的深度遍歷操作
void DFSTraverse(MGraph G){
int i;

// 初始化所有頂點狀態都是未訪問過狀態
for (i = 0; i < G.numVertexes; ++i) {
visited[i] = FALSE;
}

//防止圖為非聯通的情況，遍歷整個圖
for (i = 0; i < G.numVertexes; ++i) {
if (!visited[i]){ // 若是連通圖，只會執行一次
DFS(G, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
當圖採用鄰接矩陣進行存儲，棧的實現操作：

void DFS_Stack(MGraph G, int i)
{
int node;
int count = 1;
printf("%c ", G.vexs[i]); // 列印已訪問頂點
visited[i] = TRUE;
node = i;
push(i); //開始的節點入棧
while(count < G.numVertexes) //still has node not visited
{
/* 所有被訪問的節點依次入棧，只有node當找不到下一個相連的節點時，才使用出棧節點 */
for(j=0; j < G.numVertexes; j++)
{
if(G.arc[node][j] == 1 && visited[j] == FALSE)
{
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
count++;
push(j); //push node j
break;
}
}
if(j == G.numVertexes) //與node相連的頂點均已被訪問過，所以需要從stack里取出node的上一個頂點，再看該頂點的鄰接頂點是否未被訪問
node = pop();
else //找到與node相連並且未被訪問的頂點，
node = j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
請添加圖片描述
鄰接表存儲下圖的深度優先搜索代碼實現，與鄰接矩陣的思想相同，只是實現略有不同：

// 鄰接表的深度有限遞歸演算法

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean; // 這里我們定義Boolean為布爾類型，其值為TRUE或FALSE
Boolean visited[MAX]; // 訪問標志的數組

void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;

visited[i] = TRUE;
printf("%c " GL->adjList[i].data);
p = GL->adjList[i].firstEdge;

while(p)
{
if( !visited[p->adjvex] )
{
DFS(GL, p->adjvex);
}
p = p->next;
}
}

// 鄰接表的深度遍歷操作
void DFSTraverse(GraphAdjList GL)
{
int i;

for( i=0; i < GL->numVertexes; i++ )
{
visited[i] = FALSE; // 初始化所有頂點狀態都是未訪問過狀態
}

for( i=0; i < GL->numVertexes; i++ )
{
if( !visited[i] ) // 若是連通圖，只會執行一次
{
DFS(GL, i);
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
廣度優先遍歷
請添加圖片描述

// 鄰接矩陣的廣度遍歷演算法
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;

for( i=0; i < G.numVertexes; i++ )
{
visited[i] = FALSE;
}

initQueue( &Q );

for( i=0; i < G.numVertexes; i++ )
{
if( !visited[i] )
{
printf("%c ", G.vex[i]);
visited[i] = TRUE;
EnQueue(&Q, i);

while( !QueueEmpty(Q) )
{
DeQueue(&Q, &i);
for( j=0; j < G.numVertexes; j++ )
{
if( G.art[i][j]==1 && !visited[j] )
{
printf("%c ", G.vex[j]);
visited[j] = TRUE;
EnQueue(&Q, j);
}
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
原文鏈接：https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw%3D%3D&chksm=db828f&idx=1&mid=2653197523&scene=21&sn=#wechat_redirect