本系列文章【資料結構與演算法】所有完整代碼已上傳 github，想要完整代碼的小伙伴可以直接去那獲取，可以的話歡迎點個Star哦~下面放上跳轉鏈接

https://github.com/Lpyexplore/structureAndAlgorithm-JS

圖結構 非常得類似我們之前講到過的樹結構，但前者沒有很多的從屬關系，更多的是各個資料之間的相關聯系，在數學的概念中，后者是前者的一種，不過在資料結構中我們還是認為兩者有所區別，盡管如此，我們在學習圖結構的時候仍可以稍微借鑒一下樹結構的思想

這里放上之前樹結構的文章地址，沒看過的小伙伴可以查閱一下：

【資料結構與演算法】詳解什么是樹結構，并用代碼手動實作一個二叉查找樹

接下來讓我們來一起學習一下圖結構吧

在這里插入圖片描述

公眾號：Lpyexplore的編程小屋
關注我，每天更新，帶你在python爬蟲的程序中學習前端，還有更多電子書、面試題、資料結構與演算法代碼等你來拿

資料結構——圖結構

一、什么是圖結構
二、圖結構的術語
三、圖的表示

（1）鄰接矩陣
（2）鄰接表

四、遍歷搜索

（1）廣度優先搜索
（2）深度優先搜索

五、圖結構的方法
六、用代碼實作圖結構

（1）創建一個建構式
（2）實作addVertex()方法
（3）實作addEdge()方法
（4）實作toString()方法
（5）實作initColor()方法（內部方法）
（6）實作breadthFirstSearch()方法
（7）實作depthFirstSearch()方法

七、結束語

一、什么是圖結構

圖是由頂點的集合和邊的集合組成的，

在我們的身邊有很多用到圖結構的地方，例如地鐵線路圖

在這里插入圖片描述
地鐵線路圖中每一個站點都可以看成一個頂點，而連接著每個站點的線路可以看作是邊

其中邊是可以有方向的，例如從 站點1 到 站點2 是可以的，但是反過來 站點2 到 站點1 是不可以的，那么此時就說 頂點1 和 頂點2 之間的邊是有方向的，方向為 頂點1 -> 頂點2

二、圖結構的術語

文章開頭說過，圖結構與樹結構有很多的相似之處，因此我們還是要先來介紹一些下文會提到的圖結構中的術語

術語	含義
頂點	圖中的某個結點
邊	頂點之間連線
相鄰頂點	由同一條邊連接在一起的頂點
度	一個頂點的相鄰頂點個數
簡單路徑	由一個頂點到另一個頂點的路線，且沒有重復經過頂點
回路	第一個頂點和最后一個頂點的相同的路徑
無向圖	圖中所有的邊都沒有方向
有向圖	圖中所有的邊都有方向
無權圖	圖中的邊沒有權重值
有權圖	圖中的邊帶有一定的權重值

我們再來看個圖的例子，借此來更詳細地介紹一下每個術語地含義，如圖

在這里插入圖片描述
該圖為某某縣地村落分布圖，我們可以把其看成是一個圖結構，其中每個村看成是一個頂點，每兩個村之間可能通了一條路方便來往，例如 A村和D村之間就有一條路線1，我們稱之為邊

鄰村表示只需要經過一條邊就可以到達另一個村，那么我們就說這兩個村互為鄰村，也可以稱它們互為相鄰頂點，每個村都會有一個甚至多個鄰村，例如D村的鄰村有 A村、C村、F村，此時我們就說頂點D（D村）的度為3

假設有一天，你要從A村前往E村，你選擇的路線是這樣的，如圖所示
在這里插入圖片描述
途中我們經過了 頂點A 、頂點C 、頂點E ，沒有重復經過某個頂點，因此我們稱這條路線為簡單路徑

此時，若你選擇的路線是這樣的，如圖所示

在這里插入圖片描述
途中經過兩次 頂點C ，此時我們就不能稱這條路線為簡單路徑了

到了晚上，你準備起身回家，但選擇經過B村再回家，那么此時你一整天的路線是這樣的，如圖所示
在這里插入圖片描述
因為你當前的出發點和結束點都是A村（頂點A），因此這樣的路線我們稱之為回路

第二天，你接到一個任務，盡快將一個包裹送往E村，為了節省時間，你查閱資料獲取到了各條路的長度，如圖所示

在這里插入圖片描述
此時的圖結構上每條邊就帶上了權重值，我們稱這個圖為有權圖

通過計算，最后選擇了 A村 -> C村 -> E村 這條路線，等到包裹送到E村以后，你正準備原路回傳，但發現來時的路都是單向的，現在不允許走這條路回去了，于是你又查閱資料，查看這個縣各條路的方向情況，結果如圖所示

在這里插入圖片描述
此時的圖結構上每條邊都有一定的方向，我們稱這個圖為有向圖

最后你選擇了 E村 -> B村 -> A村 這條路線成功回到了家

三、圖的表示

上面我們在介紹圖的時候，都是用一個形象的圖片來講解的，但在程式中，這樣的表達方式顯然不是我們想要的，因此我們要找到別的方式來表示結構

圖結構的常見的兩個表達方式： 鄰接矩陣 、鄰接表

（1）鄰接矩陣

顧名思義，鄰接矩陣就像數學中的矩陣，我們只不過是借此來表示圖結構，如圖所示，現在有一個這樣的圖結構

在這里插入圖片描述

很明顯，該圖為無向圖，那么我們用矩陣的形式來表示它就如下圖
在這里插入圖片描述
圖中的 0 表示該頂點無法通向另一個頂點，相反 1 就表示該頂點能通向另一個頂點

先來看第一行，該行對應的是頂點A，那我們就拿頂點A與其它點一一對應，發現頂點A除了不能通向頂點D和自身，可以通向其它任何一個的頂點

因為該圖為無向圖，因此頂點A如果能通向另一個頂點，那么這個頂點也一定能通向頂點A，所以這個頂點對應頂點A的也應該是 1

為了大家更好的理解，我根據這個鄰接矩陣，重新還原了一幅正確的圖結構出來，如下面這張動圖所示：

在這里插入圖片描述
雖然我們確實用鄰接矩陣表示了圖結構，但是它有一個致命的缺點，那就是矩陣中存在著大量的0，這在程式中會占據大量的記憶體，此時我們思考一下，0就是表示沒有，沒有為什么還要寫，所以我們來看一下第二種表示圖結構的方法，它就很好的解決了鄰接矩陣的缺陷

（2）鄰接表

鄰接表 是由每個頂點以及它的相鄰頂點組成的

還是使用剛才上面的那個例子，如圖

在這里插入圖片描述
那么此時我們的鄰接表就是這樣的，如下圖

在這里插入圖片描述

圖中最左側紅色的表示各個頂點，它們對應的那一行存盤著與它相關聯的頂點

因此，我們可以看出：

頂點A 與 頂點B 、頂點C 、頂點E 相關聯
頂點B 與 頂點A 相關聯
頂點C 與 頂點A 、頂點D 、頂點E 相關聯
頂點D 與 頂點C 相關聯
頂點E 與 頂點A 、頂點C 相關聯

為了大家更好的理解，我根據這個鄰接表，重新還原了一幅正確的圖結構出來，如下面這張動圖所示：

在這里插入圖片描述
我們在文章末尾封裝圖結構時，也會用到這種表示方法

四、遍歷搜索

在圖結構中，存在著兩種遍歷搜索的方式，分別是 廣度優先搜索 和 深度優先搜索

在介紹這兩種搜索方式前，我們先來看一個例子

在這里插入圖片描述
這是一個吃金幣的小游戲，從入口開始，進去吃掉所到所有的金幣，但是要盡可能少得走重復的路

首先我們可以把它簡化成我們學習的圖結構，如圖

在這里插入圖片描述
接下來我們就根據這個圖結構來介紹兩種遍歷搜索方式

（1）廣度優先搜索

廣度優先搜索 就是從第一個頂點開始，嘗試訪問盡可能靠近它的頂點，即先訪問最靠近它的所有頂點，再訪問第二靠近它的所有頂點，以此類推，直到訪問完所有的頂點

概念比較抽象，我們就拿上面的例子來說，如圖所示

在這里插入圖片描述
第一次先搜索離 頂點1 最近的兩個頂點，即 頂點2 和 頂點7

然后再搜索離 頂點1 第二近的所有頂點，也就是離 頂點2 和 頂點7 最近的所有頂點，如圖所示
在這里插入圖片描述
由圖可知，離頂點2 最近的頂點為 頂點3 和 頂點5 ，離 頂點7 最近的頂點為 頂點8 ，因此這幾個點以此被遍歷

再繼續往下搜索離 頂點1 第三近的所有頂點，也就是離 頂點3 、頂點5 和 頂點8 最近的所有頂點，搜索程序如圖所示
在這里插入圖片描述
由圖可知，離 頂點3 最近的頂點有 頂點6 ；離 頂點5 最近的頂點有 頂點4 ；離 頂點8 最近的頂點有 頂點9，因此它們也逐一被遍歷

到此為止，整個圖結構就已經被遍歷完成了，這就是一個廣度優先搜索完整的程序

（2）深度優先搜索

深度優先搜索 就是從一個頂點開始，沿著一條路徑一直搜索，直到到達該路徑的最后一個結點，然后回退到之前經過但未搜索過的路徑繼續搜索，直到所有路徑和結點都被搜索完畢

同樣的，概念比較抽象，我們來用上面的例子模擬一遍深度優先搜索，如圖所示

先隨便沿著一條路徑一直搜索，圖中路徑為 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 5 -> 4

在這里插入圖片描述

當搜索到 頂點4 時，發現查找不到未被訪問的頂點了，因此 頂點4 就是這條路徑的最后一個頂點，此時我們要往后倒退，找尋別的每搜索過的路徑

此時發現當往后退到 頂點8 時，有一條路徑上還有未被搜索過的頂點，即 8 -> 7 ，如圖所示
在這里插入圖片描述

沿著這條路徑一直找到了最后一個頂點—— 頂點7，此時我們要繼續往后退，看看還有沒有別的路徑沒走過并且有未搜索過的頂點，但此時發現所有頂點都被訪問過了，因此一個完整的深度優先搜索就完成了

五、圖結構的方法

在封裝圖結構之前，我們先來了解一下圖結構都由哪些方法，如下表所示

方法	含義
addVertex()	添加頂點
addEdge()	添加邊
toString()	展示鄰接表
breadthFirstSearch()	廣度優先搜索
depthFirstSearch()	深度優先搜索

六、用代碼實作圖結構

前提：

我們封裝的圖結構中，存盤邊的方式用到的是我們上文提到的鄰接表
封裝的圖結構面向的都是無權無向圖

（1）創建一個建構式

首先創建一個大的建構式，用于存放二叉查找樹的一些屬性和方法，

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}
}

因為圖結構是由頂點的集合和邊的集合構成的，因此我們想要設定兩個屬性 vertexes 和 edges ，分別存盤著所有的頂點、所有的邊

其中，屬性 edges 是初始化了一個空物件，

假設我們先新添加一個 頂點A ，那么我們除了在屬性 vertexes 中存盤一下該頂點資訊，我們還要為 頂點A 在屬性 edges 中創建一個鍵值對，鍵為 頂點A ，值是一個空陣列，用于存放之后它的相鄰頂點，如圖所示

在這里插入圖片描述
然后我們又新添加一個 頂點B ，并且設定 頂點A 與 頂點B 為相鄰頂點，那么此時的屬性 edges 是這樣的

在這里插入圖片描述
此時可以很明顯的看出，頂點A 和 頂點B 相關聯，即它們之間有一條邊，它們互為相鄰頂點

（2）實作addVertex()方法

addVertex() 方法就是將一個頂點添加到圖結構中，該方法需要傳入一個引數 v 用于表示頂點資訊

實作思路：

將新添加的頂點 v 添加到屬性 vertexes 中
在屬性 edges 中為頂點 v 創建一個陣列空間，用于存放與其相關的邊的資訊

我們來看一下代碼

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}

	// 方法
    // 添加頂點
    Graph.prototype.addVertex = function(v) {
        this.vertexes.push(v)
        this.edges[v] = []
    }
}

我們來使用一下該方法

let graph = new Graph()

graph.addVertex(3)
graph.addVertex(9)
graph.addVertex(5)

我們來看一下我們定義的兩個屬性是什么樣的，如圖所示

在這里插入圖片描述

在這里插入圖片描述
此時的各個頂點之間是沒有任何的邊的，等我們后面封裝好了添加邊的方法以后，再回頭來看一下

（3）實作addEdge()方法

addEdge() 方法用于向圖結構中添加邊，該方法需要傳入兩個引數，即 v1 和 v2，分別代表兩個頂點

實作思路：

找到屬性 edges 中的 v1，為其添加一個相鄰頂點 v1
同時找到屬性 edges 中的 v2，為其添加一個相鄰頂點 v1

我們來看一下代碼

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}

	// 方法
    // 添加邊
    Graph.prototype.addEdge = function(v1, v2) {
        this.edges[v1].push(v2)
        this.edges[v2].push(v1)
    }
}

現在我們來使用一下該方法

let graph = new Graph()

// 向圖結構
graph.addVertex(3)
graph.addVertex(9)
graph.addVertex(5)

// 為頂點添加邊
// 在頂點3 和 頂點9 之間添加一條邊
graph.addEdge(3, 9)
// 在頂點3 和 頂點5 之間添加一條邊
graph.addEdge(3, 5)
// 在頂點5 和 頂點9 之間添加一條邊
graph.addEdge(5, 9)

我們來看一下我們定義的兩個屬性是什么樣的，如圖所示
在這里插入圖片描述

此時的圖結構是這樣的

在這里插入圖片描述

（4）實作toString()方法

toString() 方法是用字串的形式來向我們展示鄰接表，該方法無需傳入引數

我們先來看一下我們最終需要的展示效果是如何的，如圖

在這里插入圖片描述
其實就是依次展示了每個頂點的所有相鄰頂點

實作思路：

創建一個字串 str
遍歷屬性 vertexes，獲取到每個頂點
每獲取到一個頂點時，添加到 str 中，然后從屬性 edges 中找到存放該頂點的相鄰頂點的陣列，然后遍歷該陣列，將所有相鄰頂點添加到 str 中
最侄訓傳 str

我們直接來看一下代碼

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}

	// 方法
    // 展示鄰接表
    Graph.prototype.toString = function() {
    	// 1. 創建字串，用于存放資料
        let string = ''
        
        // 2. 遍歷所有頂點
        for(let i in this.vertexes) {
			
			// 2.1 獲取遍歷到的頂點
            let vertex = this.vertexes[i]
			
			// 2.2 將遍歷到的頂點添加到字串中
            string += `${vertex} => `
            
            // 2.3 獲取存盤該頂點所有的相鄰頂點的陣列
            let edges = this.edges[vertex]

			// 2.4 遍歷該頂點所有的相鄰頂點
            for(let i in edges) {
            	// 2.4.1 將遍歷到的相鄰頂點添加到字串中
                string += `${edges[i]} `
            }
            // 2.5 換行
            string += '\n'
        }
		
		// 3. 回傳最終結果
        return string
    }
}

我們來使用一下該方法，為了方便，這里仍用上面的例子

let graph = new Graph()

// 向圖結構
graph.addVertex(3)
graph.addVertex(9)
graph.addVertex(5)

// 為頂點添加邊
graph.addEdge(3, 9)
graph.addEdge(3, 5)
graph.addEdge(5, 9)

// 獲取鄰接表
console.log(graph.toString())
/* 回傳結果為：
				3 => 9 5 
				9 => 3 5 
				5 => 3 9 
*/

核對了一下，結果時正確的

（5）實作initColor()方法（內部方法）

在封裝 breadthFirstSearch()方法和 depthFirstSearch() 方法之前，我們要額外封裝一個 initColor()方法，這里要用到一個思想，但上面在介紹廣度優先搜索和深度優先搜索時沒有提到，這里我們來了解一下

無論是在進行廣度優先搜索還是深度優先搜索時，我們搜索頂點的時候，會頻繁地重復搜索到某些頂點，那么我們就要用一種方式，使被搜索過的頂點不再被重復搜索一次，這種方法就是給每個頂點一個顏色標記，沒有被搜索過的頂點被標記白色，被搜索過的頂點被標記黑色

我們就拿一個簡單的廣度優先搜索的例子，來感受一下該方法的作用

首先是廣度優先搜索的例子，如圖所示

在這里插入圖片描述
首先我們從 頂點A 開始搜索，先依次遍歷其所有的相鄰頂點有 頂點B 和 頂點C ；

然后接著分別遍歷 頂點B 和 頂點C 的所有相鄰頂點，其中 頂點B 的所有相鄰頂點有 頂點A 、頂點C 、頂點D ，頂點C 的所有相鄰頂點有 頂點A 、頂點B 、頂點D ，我們就按上述順序依次遍歷，此時我們可以發現，當遍歷 頂點B 的相鄰頂點時，會搜索到 頂點A，但是 頂點A 是我們一開始就搜索過的，因此不應該重復遍歷，

同樣的，當遍歷完 頂點B 的相鄰頂點以后，在遍歷 頂點C 的相鄰頂點時，我們會發現其所有的相鄰頂點之前都已經搜索過了，現在不應該重復遍歷了，

所以我們來看一下使用了顏色標記以后的搜索程序吧

首先遍歷到初始頂點——頂點A，此時我們給它標記黑色

在這里插入圖片描述
接著遍歷 頂點A 所有的相鄰頂點，即 頂點B 和 頂點C，并將它們都標記為黑色

在這里插入圖片描述
最后，我們要遍歷 頂點B 和 頂點C 所有的相鄰頂點

先遍歷 頂點B 的相鄰頂點，分別是 頂點A 、頂點C 、頂點D，我們通過顏色辨認得知 頂點A 和 頂點C 都為黑色，表示已經被搜索過了，所以無需重復遍歷它們，此時只有 頂點D 不為黑色，所以我們搜索到了 頂點D，并將其標記為黑色

在這里插入圖片描述
接著我們要遍歷 頂點C 的相鄰頂點，分別為 頂點A 、頂點B 、頂點D，但我們此時通過顏色辨認發現，所有的相鄰頂點都被搜索過了，因此無需重復遍歷這些頂點了，

這樣一個完美的廣度優先搜索就完成了，

因此，我們需要封裝一個顏色初始化的函式，用于將所有頂點的顏色都初始化為白色，并將顏色資訊存放在一個物件中，回傳該物件用于別的函式

我們來看一下代碼

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}

	// 方法
    // 頂點顏色初始化（內部函式）
    Graph.prototype.initColor = function() {
        // 1. 創建物件，存放顏色資訊
        let color = {}
        
        // 2. 遍歷所有頂點，將其顏色初始化為白色
        for(let i in this.vertexes) {
            color[this.vertexes[i]] = 'white'
        }
		
		// 3. 回傳顏色物件
        return color       
    }
}

該方法的使用我們會在后續使用到，這里就不做演示了

（6）實作breadthFirstSearch()方法

breadthFirstSearch() 方法是對圖結構進行廣度優先搜索，該方法接收兩個引數，第一個引數為初始頂點，即從哪個頂點開始搜索；第二個引數接收一個回呼函式 handle 作為引數，用于在搜索程序中進行一些操作

在上文多次介紹了廣度優先搜索，其實這是一種基于佇列來搜索頂點的方式

注：這里我就把我之前文章中封裝的佇列建構式直接拿來使用了，如果想看佇列的各個方法的實作程序的小伙伴可以點擊下面跳轉鏈接進行查看

【資料結構與演算法】詳解什么是佇列，并用代碼手動實作一個佇列結構

實作思路：

先將所有的頂點顏色初始化為白色
從給定的第一個頂點開始搜索，即將第一個頂點添加到佇列中，并將第一個頂點標記為黑色
從佇列中取出一個頂點，查找該頂點的未被訪問過的相鄰頂點，將其添加到佇列的隊尾位置，并將這些頂點標記未黑色，表示也被訪問過
執行我們的回呼函式 handle，將該頂點作為引數傳入
一直回圈 步驟3 ~ 步驟4 ，直到佇列為空

我們來看一下具體的代碼

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}

	// 已經封裝好的佇列建構式
	function Queue() {
	    this.list = []
	
	    //入佇列
	    Queue.prototype.enqueue = function (e) {
	        this.list.push(e)
	    }
	    //出佇列
	    Queue.prototype.dequeue = function () {
	        return this.list.shift()
	    }
	    //判斷佇列是否為空
	    Queue.prototype.isEmpty = function() {
	        if(this.list.length === 0) {
	            return true
	        }
	        else {
	            return false
	        }
	    }
	    //回傳佇列中元素個數
	    Queue.prototype.size = function () {
	        return this.list.length
	    }
	    //回傳佇列中的第一個元素
	    Queue.prototype.front = function () {
	        return this.list[0]
	    }
	    //回傳當前佇列
	    Queue.prototype.toString = function () {
	        let string = ''
	        for(let i in this.list) {
	            string += `${this.list[i]} `
	        }
	        return string
	    }
	}

	// 方法
    // 頂點顏色初始化（內部函式）
    Graph.prototype.initColor = function() {
        // 1. 創建物件，存放顏色資訊
        let color = {}
        
        // 2. 遍歷所有頂點，將其顏色初始化為白色
        for(let i in this.vertexes) {
            color[this.vertexes[i]] = 'white'
        }
		
		// 3. 回傳顏色物件
        return color       
    }

	// 廣度優先搜索
    Graph.prototype.breadthFirstSearch = function(firstVertex, handle) {
        // 1. 初始化所有頂點顏色
        const color = this.initColor()
        
        // 2. 新建一個佇列
        const queue = new Queue()
        
        // 3. 將第一個頂點加入佇列
        queue.enqueue(firstVertex)

        // 4. 開始廣度優先搜索
        while(!queue.isEmpty()) {

            // 4.1 從佇列中取出一個頂點
            let vertex = queue.dequeue()

            // 4.2 獲取與該頂點相關的其他頂點
            let otherVertexes = this.edges[vertex]

            // 4.3 將該頂點設為黑色，表示已被訪問過，防止后面重復訪問
            color[vertex] = 'black'

            // 4.4 遍歷與該頂點相關的其它頂點
            for(let i in otherVertexes) {

                // 4.4.1 獲取與該頂點相關的頂點
                let item = otherVertexes[i]

                // 4.4.1 若未被訪問，則加入到佇列中
                if(color[item] === 'white') {
                    color[item] = 'black'
                    queue.enqueue(item)
                }
            }

            // 4.5 執行我們的回呼函式
            handle(vertex)
        }     
    }
}

我們來使用一下該方法吧，為了方便檢查函式的正確性，我們之前介紹到的吃金幣的例子，并且回呼函式 handle 用來列印一下訪問到的頂點

這里我直接把正確的訪問順序圖放在這里，方便大家下面核對結果是否正確
在這里插入圖片描述

let graph = new Graph()

graph.addVertex(1)
graph.addVertex(2)
graph.addVertex(3)
graph.addVertex(4)
graph.addVertex(5)
graph.addVertex(6)
graph.addVertex(7)
graph.addVertex(8)
graph.addVertex(9)

graph.addEdge(1, 2)
graph.addEdge(1, 7)
graph.addEdge(2, 3)
graph.addEdge(2, 5)
graph.addEdge(3, 2)
graph.addEdge(3, 6)
graph.addEdge(4, 5)
graph.addEdge(5, 4)
graph.addEdge(5, 2)
graph.addEdge(5, 8)
graph.addEdge(6, 3)
graph.addEdge(6, 9)
graph.addEdge(7, 1)
graph.addEdge(7, 8)
graph.addEdge(8, 5)
graph.addEdge(8, 7)
graph.addEdge(8, 9)
graph.addEdge(9, 6)
graph.addEdge(9, 8)

// 廣度優先搜索
graph.breadthFirstSearch(1, function(vertex) {
	// 列印訪問到的頂點
	console.log(vertex)
})
/* 列印結果：
			1
			2
			7
			3
			5
			8
			6
			4
			9
*/

把列印的結果和圖片核對以后發現結果是一致的，因此這個方法是沒有問題的

（7）實作depthFirstSearch()方法

depthFirstSearch() 方法是對圖結構進行深度優先搜索，該方法接收兩個引數，第一個引數為初始頂點，即從哪個頂點開始搜索；第二個引數接收一個回呼函式 handle 作為引數，用于在搜索程序中進行一些操作

在上文多次介紹了深度優先搜索，其實這是一種基于堆疊來搜索頂點的方式，我們也直到其實遞回也是利用堆疊結構的思路實作的，因此我們這里封裝該方法時就不把之前封裝好的堆疊結構拿來使用了，直接利用遞回實作，正好遞回也能把代碼變得簡潔點

因此首先我們要封裝一個遞回呼叫的主體函式，方法名為 depthVisit，該方法接收三個引數，第一個引數為搜索的頂點；第二個引數為存盤頂點顏色資訊的物件；第三個引數為回呼函式，實作思路如下

depthVisit()方法的實作思路：

從給定的頂點開始搜索，將其標記為黑色，表示已被訪問過
執行我們的回呼函式 handle，將該頂點作為引數傳入
遍歷該頂點的所有相鄰頂點，若相鄰頂點為黑色，則表示已被訪問過，就不做任何處理
若相鄰頂點為白色，則表示未被訪問，于是就再次呼叫 breadthFirstSearch()方法，將該頂點作為第一個引數

再來簡單說一下 depthFirstSearch() 方法的實作思路

depthFirstSearch()方法的實作思路：

將所有頂點的顏色初始化為白色
選擇一個頂點作為深度優先搜索的第一個頂點，呼叫 depthVisit()方法，并將該頂點作為該方法的第一個引數

接下來我們來看一下具體的代碼吧

function Graph() {
    // 屬性
    this.vertexes = []
    this.edges = {}

	// 方法
    // 頂點顏色初始化（內部函式）
    Graph.prototype.initColor = function() {
        // 1. 創建物件，存放顏色資訊
        let color = {}
        
        // 2. 遍歷所有頂點，將其顏色初始化為白色
        for(let i in this.vertexes) {
            color[this.vertexes[i]] = 'white'
        }
		
		// 3. 回傳顏色物件
        return color       
    }
	
	// 深度優先搜索
    Graph.prototype.depthFirstSearch = function(firstVertex, handle) {
        // 1. 初始化所有頂點顏色
        const color = this.initColor()

        // 2. 開始遞回訪問各個頂點
        this.depthVisit(firstVertex, color, handle)
    }

    // 深度優先搜索的遞回訪問（內部函式）
    Graph.prototype.depthVisit = function(vertex, color, handle) {
        // 1. 先將訪問到的頂點顏色設為黑色，防止后面重復訪問
        color[vertex] = 'black'

        // 2. 執行回呼函式
        handle(vertex)

        // 3. 獲取與該頂點相關的其它頂點
        let otherVertexes = this.edges[vertex]

        // 4. 遍歷所有相關的頂點
        for(let i in otherVertexes) {
            let item = otherVertexes[i]
            // 4.1 訪問沒有被訪問過的相鄰頂點
            if(color[item] === 'white') {
                this.depthVisit(item, color, handle)
            }
        }

    }
	
}

同樣的，我們也用上文將到的吃金幣例子中的深度優先搜索的結果圖來驗證我們方法的正確性，圖片如下

在這里插入圖片描述

let graph = new Graph()

graph.addVertex(1)
graph.addVertex(2)
graph.addVertex(3)
graph.addVertex(4)
graph.addVertex(5)
graph.addVertex(6)
graph.addVertex(7)
graph.addVertex(8)
graph.addVertex(9)

graph.addEdge(1, 2)
graph.addEdge(1, 7)
graph.addEdge(2, 3)
graph.addEdge(2, 5)
graph.addEdge(3, 2)
graph.addEdge(3, 6)
graph.addEdge(4, 5)
graph.addEdge(5, 4)
graph.addEdge(5, 2)
graph.addEdge(5, 8)
graph.addEdge(6, 3)
graph.addEdge(6, 9)
graph.addEdge(7, 1)
graph.addEdge(7, 8)
graph.addEdge(8, 5)
graph.addEdge(8, 7)
graph.addEdge(8, 9)
graph.addEdge(9, 6)
graph.addEdge(9, 8)

// 深度優先搜索
graph.depthFirstSearch(1, function(vertex) {
	// 列印訪問到的頂點
	console.log(vertex)
})
/* 列印結果：
			1
			2
			3
			6
			9
			8
			5
			4
			7
*/

把列印的結果和圖片核對以后發現結果是一致的，因此這個方法是沒有問題的

七、結束語

圖結構的講解就到這里了，希望大家對圖結構有了更深一層的理解，到此為止，我的【資料結構與演算法】專欄中的資料結構部分已經結束了，接下來準備開始講解排序演算法了，下一篇文章為基本排序演算法，順便會在文中介紹一下大O表示法，

大家可以關注我，之后我還會一直更新別的資料結構與演算法的文章來供大家學習，并且我會把這些文章放到【資料結構與演算法】這個專欄里，供大家學習使用，

然后大家可以關注一下我的微信公眾號：Lpyexplore的編程小屋，等這個專欄的文章完結以后，我會把每種資料結構和演算法的筆記放到公眾號上，大家可以去那獲取，

或者也可以去我的github上獲取完整代碼，歡迎大家點個Star

https://github.com/Lpyexplore/structureAndAlgorithm-JS

我是Lpyexplore，創作不易，喜歡的加個關注，點個收藏，給個贊~ 帶你們在Python爬蟲的程序中學習Web前端

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/4237.html

標籤：其他

上一篇：DataTransmission：免費薅羊毛，Are you kidding me? 鐳速傳輸 “百日計劃”提前大曝光！Raysync傳輸協議要開放？

下一篇：Linux VI VIM編輯器

【資料結構與演算法】詳解什么是圖結構，并用代碼手動實作一個圖結構

資料結構——圖結構

一、什么是圖結構

二、圖結構的術語

三、圖的表示

（1）鄰接矩陣

（2）鄰接表

四、遍歷搜索

（1）廣度優先搜索

（2）深度優先搜索

五、圖結構的方法

六、用代碼實作圖結構

（1）創建一個建構式

（2）實作addVertex()方法

（3）實作addEdge()方法

（4）實作toString()方法

（5）實作initColor()方法（內部方法）

（6）實作breadthFirstSearch()方法

（7）實作depthFirstSearch()方法

七、結束語