廣度優先遍歷樹演算法

Ⅰ 廣度優先遍歷是什麼

1.廣度優先遍歷的思想廣度優先遍歷類似樹的按層次遍歷。設初始狀態時圖中的所有頂點未被訪問，則演算法思想為：首先訪問圖中某指定的起始頂點v，並將其標記為已訪問過，然後由v出發依次訪問v的各個未被訪問的鄰接點v1，v2，…，vk；並將其均標識為已訪問過，再分別從v1，v2，…，vk出發依次訪問它們未被訪問的鄰接點，並使「先被訪問頂點的鄰接點」先於「後被訪問頂點的鄰接點」被訪問。直至圖中所有與頂點v路徑相通的頂點都被訪問到。

若G是連通圖，則遍歷完成；否則，在圖G中另選一個尚未訪問的頂點作為新源點繼續上述搜索過程，直至圖G中所有頂點均被訪問為止。

2.廣度優先遍歷示例例如，對圖7－18（a）所示的圖G，假設指定從頂點v1開始進行廣度優先遍歷，首先訪問v1，因與v1相鄰並且未被訪問過的頂點有v2和v6，則訪問v2和v6，然後訪問與v2相鄰並未訪問的鄰接點v2，v7，再訪問與v6相鄰並且未被訪問過的鄰接點v5，按這樣的次序依次訪問與v2相鄰並且未被訪問過的鄰接點v4，v8，與v7相鄰並且未被訪問過的鄰接點v9，此時，與v5，v4，v8，v9相鄰並且未被訪問過的鄰接點沒有了，即圖G中的所有頂點訪問完，其遍歷序列為：v1－＞v2－＞v6－＞v2－＞v7－＞v5－＞v4－＞v8－＞v9。這種順序不是唯一的，如果從v1出發後，相鄰的多個頂點優先選擇序號大的頂點訪問，其遍歷序列為：v1－＞v6－＞v2－＞v5－＞v7－＞v2－＞v4－＞v9－＞v8。同理，圖7－18（b）是假設從v1開始，相鄰的多個頂點優先選擇序號小的頂點訪問，其遍歷序列為：v1－＞v2－＞v2－＞v4－＞v5－＞v6－＞v7－＞v8；相鄰的多個頂點優先選擇序號大的頂點訪問，其遍歷序列為：v1－＞v2－＞v2－＞v7－＞v6－＞v5－＞v4－＞v8。圖7－18（c）假設從a開始，相鄰的多個頂點優先選擇ASCII碼小的頂點訪問，其遍歷序列為：a－＞b－＞d－＞e－＞f－＞c－＞g；相鄰的多個頂點優先選擇ASCII碼大的頂點訪問，其遍歷序列為：a－＞f－＞e－＞d－＞b－＞g－＞c。

2.廣度優先遍歷的演算法在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點的訪問順序，將訪問的每個頂點入隊，然後再依次出隊。

在廣度優先遍歷過程中，為了避免重復訪問某個頂點，也需要創建一個一維數組visited［n］（n是圖中頂點的數目），用來記錄每個頂點是否已被訪問過。

Ⅱ 廣度優先演算法

廣度優先演算法（Breadth-First Search），同廣度優先搜索，又稱作寬度優先搜索，或橫向優先搜索，簡稱BFS，是一種圖形搜索演演算法。簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點，如果發現目標，則演算終止。廣度優先搜索的實現一般採用open-closed表。

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

一、指代不同

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

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

二、特點不同

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

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

三、演算法不同

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

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

Ⅳ JS樹結構數據的遍歷

title: JS樹結構數據的遍歷
date: 2022-04-14
description: 針對項目中出現樹形結構數據的時候，我們怎樣去操作他

項目中我們會經常出現對樹形結構的遍歷、查找和轉換的場景，比如說DOM樹、族譜、社會機構、組織架構、許可權、菜單、省市區、路由、標簽等等。那針對這些場景和數據，我們又如何去遍歷和操作，有什麼方式或者技巧可以簡化我們的實現思路。下面我們將針對常規出現的場景去總結一下我們的遍歷方式

樹的特點
1、每個節點都只有有限個子節點或無子節點；
2、沒有父節點的節點稱為根節點；
3、每一個非根節點有且只有一個父節點；
4、除了根節點外，每個子節點可以分為多個不相交的子樹；
5、樹裡面沒有環路

下面的圖片表示一顆樹

在下面的JS中我們由多棵樹組成我們的數據

在這數據中我們如何評判數據是否為葉節點（也就是最後一級），我們每個節點都會存在children屬性，如果不存在children屬性或者children不是一個數組或者children為數組且長度為0我們則認為他是一個葉節點

我們針對樹結構的操作離不開遍歷，遍歷的話又分為廣度優先遍歷、深度優先遍歷。其中深度優先遍歷可以通過遞歸和循環的方式實現，而廣度優先遍歷的話是非遞歸的

從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。即訪問樹結構的第n+1層前必須先訪問完第n層。

簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。

所以我們的實現思路是，維護一個隊列，隊列的初始值為樹結構根節點組成的列表，重復執行以下步驟直到隊列為空：
取出隊列中的第一個元素，進行訪問相關操作，然後將其後代元素（如果有）全部追加到隊列最後。

深度優先搜索演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜索樹或圖的演算法。這個演算法會盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止

1、先序遍歷
訪問子樹的時候，先訪問根再訪問根的子樹

2、後序遍歷
訪問子樹的時候，先訪問子樹再訪問根

1、先序遍歷
先序遍歷與廣度優先循環實現類似，要維護一個隊列，不同的是子節點不追加到隊列最後，而是加到隊列最前面

2、後序遍歷
後序遍歷就略微復雜一點，我們需要不斷將子樹擴展到根節點前面去，執行列表遍歷，並且通過一個臨時對象維護一個id列表，當遍歷到某個節點如果它沒有子節點或者它本身已經存在於我們的臨時id列表，則執行訪問操作，否則繼續擴展子節點到當前節點前面

對於樹結構的遍歷操作，其實遞歸是最基礎，也是最容易理解的。遞歸本身就是循環的思想，所以可以用循環來改寫遞歸,以上的方式在項目中已經廊括了大部分的場景了，我們在日常開發中可以根據場景或者需要去選擇我們的遍歷方式，或者基於此對他進行調整和優化，至於每種方式的空間復雜度和時間復雜度我們在這個地方就不去嘗試了，各位感興趣可以自己去驗證。

廣度優先搜索

樹的遍歷

深度優先搜索

圖文詳解兩種演算法：深度優先遍歷（DFS）和廣度優先遍歷（BFS）

二叉樹遍歷（前序，後序，中序，層次）遞歸與迭代實現JavaScript

JS樹結構操作:查找、遍歷、篩選、樹和列表相互轉換

Ⅳ 基本演算法——深度優先搜索（DFS）和廣度優先搜索（BFS）

        深度優先搜索和廣度優先搜索，都是圖形搜索演算法，它兩相似，又卻不同，在應用上也被用到不同的地方。這里拿一起討論，方便比較。

一、深度優先搜索

        深度優先搜索屬於圖演算法的一種，是一個針對圖和樹的遍歷演算法，英文縮寫為DFS即Depth First Search。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

基本步奏

（1）對於下面的樹而言，DFS方法首先從根節點1開始，其搜索節點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優先選擇左分枝）。

（2）從stack中訪問棧頂的點；

（3）找出與此點鄰接的且尚未遍歷的點，進行標記，然後放入stack中，依次進行；

（4）如果此點沒有尚未遍歷的鄰接點，則將此點從stack中彈出，再按照（3）依次進行；

（5）直到遍歷完整個樹，stack里的元素都將彈出，最後棧為空，DFS遍歷完成。

二、廣度優先搜索

        廣度優先搜索（也稱寬度優先搜索，縮寫BFS，以下採用廣度來描述）是連通圖的一種遍歷演算法這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。一般用隊列數據結構來輔助實現BFS演算法。

基本步奏

（1）給出一連通圖，如圖，初始化全是白色（未訪問）；

（2）搜索起點V1（灰色）；

（3）已搜索V1（黑色），即將搜索V2，V3，V4（標灰）；

（4）對V2，V3，V4重復以上操作；

（5）直到終點V7被染灰，終止；

（6）最短路徑為V1，V4，V7.

Ⅵ 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。

Ⅶ Python數據結構-隊列與廣度優先搜索（Queue）

隊列（Queue） ：簡稱為隊，一種線性表數據結構，是一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。
我們把隊列中允許插入的一端稱為 「隊尾（rear）」 ；把允許刪除的另一端稱為 「隊頭（front）」 。當表中沒有任何數據元素時，稱之為 「空隊」 。

廣度優先搜索演算法（Breadth First Search） ：簡稱為 BFS，又譯作寬度優先搜索 / 橫向優先搜索。是一種用於遍歷或搜索樹或圖的演算法。該演算法從根節點開始，沿著樹的寬度遍歷樹或圖的節點。如果所有節點均被訪問，則演算法中止。

廣度優先遍歷 類似於樹的層次遍歷過程 。呈現出一層一層向外擴張的特點。先看到的節點先訪問，後看到的節點後訪問。遍歷到的節點順序符合「先進先出」的特點，所以廣度優先搜索可以通過「隊列」來實現。

力扣933

游戲時，隊首始終是持有土豆的人
模擬游戲開始，隊首的人出隊，之後再到隊尾（類似於循環隊列）
傳遞了num次之後，將隊首的人移除
如此反復，直到隊列中剩餘一人

多人共用一台列印機，採取「先到先服務」的隊列策略來執行列印任務
需要解決的問題：1 列印系統的容量是多少？2 在能夠接受的等待時間內，系統可容納多少用戶以多高的頻率提交列印任務？

輸入：abba
輸出：False
思路：1 先將需要判定的詞從隊尾加入 deque; 2從兩端同時移除字元並判斷是否相同，直到deque中剩餘0個（偶數）或1個字元（奇數）

內容參考： https://algo.itcharge.cn/04.%E9%98%9F%E5%88%97/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/

Ⅷ 圖的廣度優先遍歷為什麼w加一

一 圖的廣度優先遍歷基本思想
1 圖的廣度優先搜索(Broad First Search) ，簡稱BFS。

2 該遍歷類似於一個分層搜索的過程，廣度優先遍歷需要使用一個隊列以保持訪問過的結點的順序，以便按這個順序來訪問這些結點的鄰接結點。

二 廣度優先遍歷演算法步驟
1 訪問初始結點v並標記結點v為已訪問。

2 結點v入隊列。

3 當隊列非空時，繼續執行，否則演算法結束。

4 出隊列，取得隊頭結點u。

5 查找結點u的第一個鄰接結點w。

6 若結點u的鄰接結點w不存在，則轉到步驟3；否則循環執行以下三個步驟：

6.1 若結點w尚未被訪問，則訪問結點w並標記為已訪問。

6.2 結點w入隊列。

6.3 查找結點u的繼w鄰接結點後的下一個鄰接結點w，轉到步驟6。

三 實戰
1 需求
用廣度優先演算法實現下圖。

2 代碼
3 測試

Ⅸ 廣度優先搜索有什麼難點

廣度優先搜索難點在於每一種演算法的不同，樹的遍歷。

擴展知識：

廣度優先搜索演算法又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜索的實現一般採用open-closed表。

廣度優先搜索演算法主要有四個特性：

空間復雜度：由於對空間的大量需求，因此BFS並不適合解非常大的問題，對於類似的問題，應用IDDFS已達節省空間的效果。

時間復雜度：最差情形下，BFS必須查找所有到可能節點的所有路徑。

完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。

最佳解：若所有邊的長度相等，廣度優先搜索演算法是最佳解——亦即它找到的第一個解，距離根節點的邊數目一定最少；但對一般的圖來說，BFS並不一定回傳最佳解。

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

假設初始狀態是圖中所有頂點均未被訪問
從某個頂點出發，然後依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直至圖中所有和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