一、圖論

1.1.圖的簡(jiǎn)介

什么是圖？

• 圖結(jié)構(gòu)是一種與樹(shù)結(jié)構(gòu)有些相似的數(shù)據(jù)結(jié)構(gòu)；
• 圖論是數(shù)學(xué)的一個(gè)分支，并且，在數(shù)學(xué)中，樹(shù)是圖的一種；
• 圖論以圖為研究對(duì)象，研究頂點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法；
• 主要的研究目的為：事物之間的聯(lián)系，頂點(diǎn)代表事物，邊代表兩個(gè)事物間的關(guān)系；

圖的特點(diǎn)：

• 一組頂點(diǎn)：通常用 V （Vertex）表示頂點(diǎn)的集合；
• 一組邊：通常用 E（Edge）表示邊的集合；
  • 邊是頂點(diǎn)和頂點(diǎn)之間的連線；
  • 邊可以是有向的，也可以是無(wú)向的。比如A----B表示無(wú)向，A —> B 表示有向；

圖的常用術(shù)語(yǔ)：

• 頂點(diǎn)：表示圖中的一個(gè)節(jié)點(diǎn)；
• 邊：表示頂點(diǎn)和頂點(diǎn)給之間的連線；
• 相鄰頂點(diǎn)：由一條邊連接在一起的頂點(diǎn)稱為相鄰頂點(diǎn)；
• 度：一個(gè)頂點(diǎn)的度是相鄰頂點(diǎn)的數(shù)量；
• 路徑：
  • 簡(jiǎn)單路徑： 簡(jiǎn)單路徑要求不包含重復(fù)的頂點(diǎn)；
  • 回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路；
• 無(wú)向圖：圖中的所有邊都是沒(méi)有方向的；
• 有向圖：圖中的所有邊都是有方向的；
• 無(wú)權(quán)圖： 無(wú)權(quán)圖中的邊沒(méi)有任何權(quán)重意義；
• 帶權(quán)圖： 帶權(quán)圖中的邊有一定的權(quán)重含義；

1.2.圖的表示

鄰接矩陣

表示圖的常用方式為：鄰接矩陣。

• 可以使用二維數(shù)組來(lái)表示鄰接矩陣；
• 鄰接矩陣讓每個(gè)節(jié)點(diǎn)和一個(gè)整數(shù)相關(guān)聯(lián)，該整數(shù)作為數(shù)組的下標(biāo)值；
• 使用一個(gè)二維數(shù)組來(lái)表示頂點(diǎn)之間的連接；

如上圖所示：

• 二維數(shù)組中的0表示沒(méi)有連線，1表示有連線；
• 如：A[ 0 ] [ 3 ] = 1，表示 A 和 C 之間有連接；
• 鄰接矩陣的對(duì)角線上的值都為0，表示A - A ，B - B，等自回路都沒(méi)有連接（自己與自己之間沒(méi)有連接）；
• 若為無(wú)向圖，則鄰接矩陣應(yīng)為對(duì)角線上元素全為0的對(duì)稱矩陣；

鄰接矩陣的問(wèn)題：

• 如果圖是一個(gè)稀疏圖，那么鄰接矩陣中將存在大量的 0，造成存儲(chǔ)空間的浪費(fèi)；

鄰接表

另外一種表示圖的常用方式為：鄰接表。

• 鄰接表由圖中每個(gè)頂點(diǎn)以及和頂點(diǎn)相鄰的頂點(diǎn)列表組成；
• 這個(gè)列表可用多種方式存儲(chǔ)，比如：**數(shù)組/鏈表/字典（哈希表）**等都可以；

如上圖所示：

• 圖中可清楚看到A與B、C、D相鄰，假如要表示這些與A頂點(diǎn)相鄰的頂點(diǎn)（邊），可以通過(guò)將它們作為A的值（value）存入到對(duì)應(yīng)的數(shù)組/鏈表/字典中。
• 之后，通過(guò)鍵（key）A可以十分方便地取出對(duì)應(yīng)的數(shù)據(jù)；

鄰接表的問(wèn)題：

• 鄰接表可以簡(jiǎn)單地得出出度，即某一頂點(diǎn)指向其他頂點(diǎn)的個(gè)數(shù)；
• 但是，鄰接表計(jì)算入度（指向某一頂點(diǎn)的其他頂點(diǎn)的個(gè)數(shù)稱為該頂點(diǎn)的入度）十分困難。此時(shí)需要構(gòu)造逆鄰接表才能有效計(jì)算入度；

二、封裝圖結(jié)構(gòu)

在實(shí)現(xiàn)過(guò)程中采用鄰接表的方式來(lái)表示邊，使用字典類來(lái)存儲(chǔ)鄰接表。

2.1.添加字典類和隊(duì)列類

首先需要引入之前實(shí)現(xiàn)的，之后會(huì)用到的字典類和隊(duì)列類：

    //封裝字典類
function Dictionary(){
  //字典屬性
  this.items = {}

  //字典操作方法
  //一.在字典中添加鍵值對(duì)
  Dictionary.prototype.set = function(key, value){
    this.items[key] = value
  }

  //二.判斷字典中是否有某個(gè)key
  Dictionary.prototype.has = function(key){
    return this.items.hasOwnProperty(key)
  }

  //三.從字典中移除元素
  Dictionary.prototype.remove = function(key){
    //1.判斷字典中是否有這個(gè)key
    if(!this.has(key)) return false

    //2.從字典中刪除key
    delete this.items[key]
    return true
  }

  //四.根據(jù)key獲取value
  Dictionary.prototype.get = function(key){
    return this.has(key) ? this.items[key] : undefined
  }

  //五.獲取所有keys
  Dictionary.prototype.keys = function(){
    return Object.keys(this.items)
  }

  //六.size方法
  Dictionary.prototype.keys = function(){
    return this.keys().length
  }

  //七.clear方法
  Dictionary.prototype.clear = function(){
    this.items = {}
  }
}

   // 基于數(shù)組封裝隊(duì)列類
    function Queue() {
    // 屬性
      this.items = []
    // 方法
    // 1.將元素加入到隊(duì)列中
    Queue.prototype.enqueue = element => {
      this.items.push(element)
    }

    // 2.從隊(duì)列中刪除前端元素
    Queue.prototype.dequeue = () => {
      return this.items.shift()
    }

    // 3.查看前端的元素
    Queue.prototype.front = () => {
      return this.items[0]
    }

    // 4.查看隊(duì)列是否為空
    Queue.prototype.isEmpty = () => {
      return this.items.length == 0;
    }

    // 5.查看隊(duì)列中元素的個(gè)數(shù)
    Queue.prototype.size = () => {
      return this.items.length
    }

    // 6.toString方法
    Queue.prototype.toString = () => {
      let resultString = ''
        for (let i of this.items){
          resultString += i + ' '
        }
        return resultString
      }
    }

2.2.創(chuàng)建圖類

先創(chuàng)建圖類Graph，并添加基本屬性，再實(shí)現(xiàn)圖類的常用方法：

    //封裝圖類
    function Graph (){
      //屬性：頂點(diǎn)(數(shù)組)/邊(字典)
      this.vertexes = []  //頂點(diǎn)
      this.edges = new Dictionary() //邊
      }

2.3.添加頂點(diǎn)與邊

如圖所示：

創(chuàng)建一個(gè)數(shù)組對(duì)象vertexes存儲(chǔ)圖的頂點(diǎn)；創(chuàng)建一個(gè)字典對(duì)象edges存儲(chǔ)圖的邊，其中key為頂點(diǎn)，value為存儲(chǔ)key頂點(diǎn)相鄰頂點(diǎn)的數(shù)組。

代碼實(shí)現(xiàn)：

      //添加方法
      //一.添加頂點(diǎn)
      Graph.prototype.addVertex = function(v){
        this.vertexes.push(v)
        this.edges.set(v, []) //將邊添加到字典中，新增的頂點(diǎn)作為鍵，對(duì)應(yīng)的值為一個(gè)存儲(chǔ)邊的空數(shù)組
      }
      //二.添加邊
      Graph.prototype.addEdge = function(v1, v2){//傳入兩個(gè)頂點(diǎn)為它們添加邊
        this.edges.get(v1).push(v2)//取出字典對(duì)象edges中存儲(chǔ)邊的數(shù)組，并添加關(guān)聯(lián)頂點(diǎn)
        this.edges.get(v2).push(v1)//表示的是無(wú)向表，故要添加互相指向的兩條邊
      }

2.4.轉(zhuǎn)換為字符串輸出

為圖類Graph添加toString方法，實(shí)現(xiàn)以鄰接表的形式輸出圖中各頂點(diǎn)。

代碼實(shí)現(xiàn)：

      //三.實(shí)現(xiàn)toString方法:轉(zhuǎn)換為鄰接表形式
      Graph.prototype.toString = function (){
        //1.定義字符串，保存最終結(jié)果
        let resultString = ""

        //2.遍歷所有的頂點(diǎn)以及頂點(diǎn)對(duì)應(yīng)的邊
        for (let i = 0; i < this.vertexes.length; i++) {//遍歷所有頂點(diǎn)
          resultString += this.vertexes[i] + '-->'
          let vEdges = this.edges.get(this.vertexes[i])
          for (let j = 0; j < vEdges.length; j++) {//遍歷字典中每個(gè)頂點(diǎn)對(duì)應(yīng)的數(shù)組
            resultString += vEdges[j] + '  ';
          }
          resultString += '\n'
        }
        return resultString
      }

測(cè)試代碼：

   //測(cè)試代碼
    //1.創(chuàng)建圖結(jié)構(gòu)
    let graph = new Graph()

    //2.添加頂點(diǎn)
    let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
    for (let i = 0; i < myVertexes.length; i++) {
      graph.addVertex(myVertexes[i])
    }

    //3.添加邊
    graph.addEdge('A', 'B')
    graph.addEdge('A', 'C')
    graph.addEdge('A', 'D')
    graph.addEdge('C', 'D')
    graph.addEdge('C', 'G')
    graph.addEdge('D', 'G')
    graph.addEdge('D', 'H')
    graph.addEdge('B', 'E')
    graph.addEdge('B', 'F')
    graph.addEdge('E', 'I')

    //4.輸出結(jié)果
    console.log(graph.toString());

測(cè)試結(jié)果：

2.5.圖的遍歷

圖的遍歷思想：

• 圖的遍歷思想與樹(shù)的遍歷思想一樣，意味著需要將圖中所有的頂點(diǎn)都訪問(wèn)一遍，并且不能有重復(fù)的訪問(wèn)（上面的toString方法會(huì)重復(fù)訪問(wèn)）；

遍歷圖的兩種算法：

• 廣度優(yōu)先搜索（Breadth - First Search，簡(jiǎn)稱BFS）;
• 深度優(yōu)先搜索（Depth - First Search，簡(jiǎn)稱DFS）;
• 兩種遍歷算法都需要指定第一個(gè)被訪問(wèn)的頂點(diǎn)；

為了記錄頂點(diǎn)是否被訪問(wèn)過(guò)，使用三種顏色來(lái)表示它們的狀態(tài)

• 白色：表示該頂點(diǎn)還沒(méi)有被訪問(wèn)過(guò)；
• 灰色：表示該頂點(diǎn)被訪問(wèn)過(guò)，但其相鄰頂點(diǎn)并未完全被訪問(wèn)過(guò)；
• 黑色：表示該頂點(diǎn)被訪問(wèn)過(guò)，且其所有相鄰頂點(diǎn)都被訪問(wèn)過(guò)；

首先封裝initializeColor方法將圖中的所有頂點(diǎn)初始化為白色，代碼實(shí)現(xiàn)如下：

      //四.初始化狀態(tài)顏色
      Graph.prototype.initializeColor = function(){
        let colors = []
        for (let i = 0; i < this.vertexes.length; i++) {
           colors[this.vertexes[i]] = 'white';
        }
        return colors
      }

廣度優(yōu)先搜索

廣度優(yōu)先搜索算法的思路：

• 廣度優(yōu)先搜索算法會(huì)從指定的第一個(gè)頂點(diǎn)開(kāi)始遍歷圖，先訪問(wèn)其所有的相鄰頂點(diǎn)，就像一次訪問(wèn)圖的一層；
• 也可以說(shuō)是先寬后深地遍歷圖中的各個(gè)頂點(diǎn)；

實(shí)現(xiàn)思路：

基于隊(duì)列可以簡(jiǎn)單地實(shí)現(xiàn)廣度優(yōu)先搜索算法：

• 首先創(chuàng)建一個(gè)隊(duì)列Q（尾部進(jìn)，首部出）；
• 調(diào)用封裝的initializeColor方法將所有頂點(diǎn)初始化為白色；
• 指定第一個(gè)頂點(diǎn)A，將A標(biāo)注為灰色（被訪問(wèn)過(guò)的節(jié)點(diǎn)），并將A放入隊(duì)列Q中；
• 循環(huán)遍歷隊(duì)列中的元素，只要隊(duì)列Q非空，就執(zhí)行以下操作：
  • 先將灰色的A從Q的首部取出；
  • 取出A后，將A的所有未被訪問(wèn)過(guò)（白色）的相鄰頂點(diǎn)依次從隊(duì)列Q的尾部加入隊(duì)列，并變?yōu)榛疑?。以此保證，灰色的相鄰頂點(diǎn)不重復(fù)加入隊(duì)列；
  • A的全部相鄰節(jié)點(diǎn)加入Q后，A變?yōu)楹谏?，在下一次循環(huán)中被移除Q外；

代碼實(shí)現(xiàn)：

      //五.實(shí)現(xiàn)廣度搜索(BFS)
      //傳入指定的第一個(gè)頂點(diǎn)和處理結(jié)果的函數(shù)
      Graph.prototype.bfs = function(initV, handler){
        //1.初始化顏色
        let colors = this.initializeColor()

        //2.創(chuàng)建隊(duì)列
        let que = new Queue()

        //3.將頂點(diǎn)加入到隊(duì)列中
        que.enqueue(initV)

        //4.循環(huán)從隊(duì)列中取出元素，隊(duì)列為空才停止
        while(!que.isEmpty()){
          //4.1.從隊(duì)列首部取出一個(gè)頂點(diǎn)
          let v = que.dequeue()

          //4.2.從字典對(duì)象edges中獲取和該頂點(diǎn)相鄰的其他頂點(diǎn)組成的數(shù)組
          let vNeighbours = this.edges.get(v)

          //4.3.將v的顏色變?yōu)榛疑?/span>
          colors[v] = 'gray'

          //4.4.遍歷v所有相鄰的頂點(diǎn)vNeighbours,并且加入隊(duì)列中
          for (let i = 0; i < vNeighbours.length; i++) {
            const a = vNeighbours[i];
            //判斷相鄰頂點(diǎn)是否被探測(cè)過(guò)，被探測(cè)過(guò)則不加入隊(duì)列中；并且加入隊(duì)列后變?yōu)榛疑?，表示被探測(cè)過(guò)
            if (colors[a] == 'white') {
              colors[a] = 'gray'
              que.enqueue(a)
            }
          }

          //4.5.處理頂點(diǎn)v
          handler(v)

          //4.6.頂點(diǎn)v所有白色的相鄰頂點(diǎn)都加入隊(duì)列后，將頂點(diǎn)v設(shè)置為黑色。此時(shí)黑色頂點(diǎn)v位于隊(duì)列最前面，進(jìn)入下一次while循環(huán)時(shí)會(huì)被取出
          colors[v] = 'black'
        }
      }

過(guò)程詳解：

下為指定的第一個(gè)頂點(diǎn)為A時(shí)的遍歷過(guò)程：

• 如 a 圖所示，將在字典edges中取出的與A相鄰的且未被訪問(wèn)過(guò)的白色頂點(diǎn)B、C、D放入隊(duì)列que中并變?yōu)榛疑S后將A變?yōu)楹谏⒁瞥鲫?duì)列；
• 接著，如圖 b 所示，將在字典edges中取出的與B相鄰的且未被訪問(wèn)過(guò)的白色頂點(diǎn)E、F放入隊(duì)列que中并變?yōu)榛疑?，隨后將B變?yōu)楹谏⒁瞥鲫?duì)列；

• 如 c 圖所示，將在字典edges中取出的與C相鄰的且未被訪問(wèn)過(guò)的白色頂點(diǎn)G（A，D也相鄰不過(guò)已變?yōu)榛疑圆患尤腙?duì)列）放入隊(duì)列que中并變?yōu)榛疑?，隨后將C變?yōu)楹谏⒁瞥鲫?duì)列；
• 接著，如圖 d 所示，將在字典edges中取出的與D相鄰的且未被訪問(wèn)過(guò)的白色頂點(diǎn)H放入隊(duì)列que中并變?yōu)榛疑?，隨后將D變?yōu)楹谏⒁瞥鲫?duì)列。

如此循環(huán)直到隊(duì)列中元素為0，即所有頂點(diǎn)都變黑并移出隊(duì)列后才停止，此時(shí)圖中頂點(diǎn)已被全部遍歷。

測(cè)試代碼：

    //測(cè)試代碼
    //1.創(chuàng)建圖結(jié)構(gòu)
    let graph = new Graph()

    //2.添加頂點(diǎn)
    let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
    for (let i = 0; i < myVertexes.length; i++) {
      graph.addVertex(myVertexes[i])
    }

    //3.添加邊
    graph.addEdge('A', 'B')
    graph.addEdge('A', 'C')
    graph.addEdge('A', 'D')
    graph.addEdge('C', 'D')
    graph.addEdge('C', 'G')
    graph.addEdge('D', 'G')
    graph.addEdge('D', 'H')
    graph.addEdge('B', 'E')
    graph.addEdge('B', 'F')
    graph.addEdge('E', 'I')
    
    //4.測(cè)試bfs遍歷方法
    let result = ""
    graph.bfs(graph.vertexes[0], function(v){
      result += v + "-"
    })
    console.log(result);

測(cè)試結(jié)果：

可見(jiàn)，安裝了廣度優(yōu)先搜索的順序不重復(fù)地遍歷了所有頂點(diǎn)。

深度優(yōu)先搜索

廣度優(yōu)先算法的思路：

• 深度優(yōu)先搜索算法將會(huì)從指定的第一個(gè)頂點(diǎn)開(kāi)始遍歷圖，沿著一條路徑遍歷直到該路徑的最后一個(gè)頂點(diǎn)都被訪問(wèn)過(guò)為止；
• 接著沿原來(lái)路徑回退并探索下一條路徑，即先深后寬地遍歷圖中的各個(gè)頂點(diǎn)；

實(shí)現(xiàn)思路：

• 可以使用棧結(jié)構(gòu)來(lái)實(shí)現(xiàn)深度優(yōu)先搜索算法；
• 深度優(yōu)先搜索算法的遍歷順序與二叉搜索樹(shù)中的先序遍歷較為相似，同樣可以使用遞歸來(lái)實(shí)現(xiàn)（遞歸的本質(zhì)就是函數(shù)棧的調(diào)用）。

基于遞歸實(shí)現(xiàn)深度優(yōu)先搜索算法：定義dfs方法用于調(diào)用遞歸方法dfsVisit，定義dfsVisit方法用于遞歸訪問(wèn)圖中的各個(gè)頂點(diǎn)。

在dfs方法中：

• 首先，調(diào)用initializeColor方法將所有頂點(diǎn)初始化為白色；
• 然后，調(diào)用dfsVisit方法遍歷圖的頂點(diǎn)；

在dfsVisit方法中：

• 首先，將傳入的指定節(jié)點(diǎn)v標(biāo)注為灰色；
• 接著，處理頂點(diǎn)V；
• 然后，訪問(wèn)V的相鄰頂點(diǎn)；
• 最后，將頂點(diǎn)v標(biāo)注為黑色；

代碼實(shí)現(xiàn)：

      //六.實(shí)現(xiàn)深度搜索(DFS)
      Graph.prototype.dfs = function(initV, handler){
        //1.初始化頂點(diǎn)顏色
        let colors = this.initializeColor()

        //2.從某個(gè)頂點(diǎn)開(kāi)始依次遞歸訪問(wèn)
        this.dfsVisit(initV, colors, handler)
      }

      //為了方便遞歸調(diào)用，封裝訪問(wèn)頂點(diǎn)的函數(shù)，傳入三個(gè)參數(shù)分別表示：指定的第一個(gè)頂點(diǎn)、顏色、處理函數(shù)
      Graph.prototype.dfsVisit = function(v, colors, handler){
        //1.將顏色設(shè)置為灰色
        colors[v] = 'gray'

        //2.處理v頂點(diǎn)
        handler(v)

        //3.訪問(wèn)V的相鄰頂點(diǎn)
        let vNeighbours = this.edges.get(v)
        for (let i = 0; i < vNeighbours.length; i++) {
          let a = vNeighbours[i];
          //判斷相鄰頂點(diǎn)是否為白色，若為白色，遞歸調(diào)用函數(shù)繼續(xù)訪問(wèn)
          if (colors[a] == 'white') {
            this.dfsVisit(a, colors, handler)
          }
          
        }

        //4.將v設(shè)置為黑色
        colors[v] = 'black'
      }

過(guò)程詳解：

這里主要解釋一下代碼中的第3步操作：訪問(wèn)指定頂點(diǎn)的相鄰頂點(diǎn)。

• 以指定頂點(diǎn)A為例，先從儲(chǔ)存頂點(diǎn)及其對(duì)應(yīng)相鄰頂點(diǎn)的字典對(duì)象edges中取出由頂點(diǎn)A的相鄰頂點(diǎn)組成的數(shù)組：

• 第一步：A頂點(diǎn)變?yōu)榛疑S后進(jìn)入第一個(gè)for循環(huán)，遍歷A白色的相鄰頂點(diǎn)：B、C、D；在該for循環(huán)的第1次循環(huán)中（執(zhí)行B），B頂點(diǎn)滿足：colors == “white”，觸發(fā)遞歸，重新調(diào)用該方法；
• 第二步：B頂點(diǎn)變?yōu)榛疑?，隨后進(jìn)入第二個(gè)for循環(huán)，遍歷B白色的相鄰頂點(diǎn)：E、F；在該for循環(huán)的第1次循環(huán)中（執(zhí)行E），E頂點(diǎn)滿足：colors == “white”，觸發(fā)遞歸，重新調(diào)用該方法；
• 第三步：E頂點(diǎn)變?yōu)榛疑?，隨后進(jìn)入第三個(gè)for循環(huán)，遍歷E白色的相鄰頂點(diǎn)：I；在該for循環(huán)的第1次循環(huán)中（執(zhí)行I），I頂點(diǎn)滿足：colors == “white”，觸發(fā)遞歸，重新調(diào)用該方法；
• 第四步：I頂點(diǎn)變?yōu)榛疑?，隨后進(jìn)入第四個(gè)for循環(huán)，由于頂點(diǎn)I的相鄰頂點(diǎn)E不滿足：colors == “white”，停止遞歸調(diào)用。過(guò)程如下圖所示：

• 第五步：遞歸結(jié)束后一路向上返回，首先回到第三個(gè)for循環(huán)中繼續(xù)執(zhí)行其中的第2、3…次循環(huán)，每次循環(huán)的執(zhí)行過(guò)程與上面的同理，直到遞歸再次結(jié)束后，再返回到第二個(gè)for循環(huán)中繼續(xù)執(zhí)行其中的第2、3…次循環(huán)…以此類推直到將圖的所有頂點(diǎn)訪問(wèn)完為止。

下圖為遍歷圖中各頂點(diǎn)的完整過(guò)程：

• 發(fā)現(xiàn)表示訪問(wèn)了該頂點(diǎn)，狀態(tài)變?yōu)?strong>灰色；
• 探索表示既訪問(wèn)了該頂點(diǎn)，也訪問(wèn)了該頂點(diǎn)的全部相鄰頂點(diǎn)，狀態(tài)變?yōu)?strong>黑色；
• 由于在頂點(diǎn)變?yōu)榛疑缶驼{(diào)用了處理函數(shù)handler，所以handler方法的輸出順序?yàn)榘l(fā)現(xiàn)頂點(diǎn)的順序即：A、B、E、I、F、C、D、G、H 。

測(cè)試代碼：

    //測(cè)試代碼
    //1.創(chuàng)建圖結(jié)構(gòu)
    let graph = new Graph()

    //2.添加頂點(diǎn)
    let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
    for (let i = 0; i < myVertexes.length; i++) {
      graph.addVertex(myVertexes[i])
    }

    //3.添加邊
    graph.addEdge('A', 'B')
    graph.addEdge('A', 'C')
    graph.addEdge('A', 'D')
    graph.addEdge('C', 'D')
    graph.addEdge('C', 'G')
    graph.addEdge('D', 'G')
    graph.addEdge('D', 'H')
    graph.addEdge('B', 'E')
    graph.addEdge('B', 'F')
    graph.addEdge('E', 'I')
    
    //4.測(cè)試dfs遍歷頂點(diǎn)
    let result = ""
    graph.dfs(graph.vertexes[0], function(v){
      result += v + "-"
    })
    console.log(result);
    

測(cè)試結(jié)果：

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-755095.html

2.6.完整實(shí)現(xiàn)

    //封裝圖結(jié)構(gòu)
    function Graph (){
      //屬性：頂點(diǎn)(數(shù)組)/邊(字典)
      this.vertexes = []  //頂點(diǎn)
      this.edges = new Dictionary() //邊

      //方法
      //添加方法
      //一.添加頂點(diǎn)
      Graph.prototype.addVertex = function(v){
        this.vertexes.push(v)
        this.edges.set(v, []) //將邊添加到字典中，新增的頂點(diǎn)作為鍵，對(duì)應(yīng)的值為一個(gè)存儲(chǔ)邊的空數(shù)組
      }
      //二.添加邊
      Graph.prototype.addEdge = function(v1, v2){//傳入兩個(gè)頂點(diǎn)為它們添加邊
        this.edges.get(v1).push(v2)//取出字典對(duì)象edges中存儲(chǔ)邊的數(shù)組，并添加關(guān)聯(lián)頂點(diǎn)
        this.edges.get(v2).push(v1)//表示的是無(wú)向表，故要添加互相指向的兩條邊
      }

      //三.實(shí)現(xiàn)toString方法:轉(zhuǎn)換為鄰接表形式
      Graph.prototype.toString = function (){
        //1.定義字符串，保存最終結(jié)果
        let resultString = ""

        //2.遍歷所有的頂點(diǎn)以及頂點(diǎn)對(duì)應(yīng)的邊
        for (let i = 0; i < this.vertexes.length; i++) {//遍歷所有頂點(diǎn)
          resultString += this.vertexes[i] + '-->'
          let vEdges = this.edges.get(this.vertexes[i])
          for (let j = 0; j < vEdges.length; j++) {//遍歷字典中每個(gè)頂點(diǎn)對(duì)應(yīng)的數(shù)組
            resultString += vEdges[j] + '  ';
          }
          resultString += '\n'
        }
        return resultString
      }

      //四.初始化狀態(tài)顏色
      Graph.prototype.initializeColor = function(){
        let colors = []
        for (let i = 0; i < this.vertexes.length; i++) {
           colors[this.vertexes[i]] = 'white';
        }
        return colors
      }

      //五.實(shí)現(xiàn)廣度搜索(BFS)
      //傳入指定的第一個(gè)頂點(diǎn)和處理結(jié)果的函數(shù)
      Graph.prototype.bfs = function(initV, handler){
        //1.初始化顏色
        let colors = this.initializeColor()

        //2.創(chuàng)建隊(duì)列
        let que = new Queue()

        //3.將頂點(diǎn)加入到隊(duì)列中
        que.enqueue(initV)

        //4.循環(huán)從隊(duì)列中取出元素
        while(!que.isEmpty()){
          //4.1.從隊(duì)列中取出一個(gè)頂點(diǎn)
          let v = que.dequeue()

          //4.2.獲取和頂點(diǎn)相相鄰的其他頂點(diǎn)
          let vNeighbours = this.edges.get(v)

          //4.3.將v的顏色變?yōu)榛疑?/span>
          colors[v] = 'gray'

          //4.4.遍歷v所有相鄰的頂點(diǎn)vNeighbours,并且加入隊(duì)列中
          for (let i = 0; i < vNeighbours.length; i++) {
            const a = vNeighbours[i];
            //判斷相鄰頂點(diǎn)是否被探測(cè)過(guò)，被探測(cè)過(guò)則不加入隊(duì)列中；并且加入隊(duì)列后變?yōu)榛疑?，表示被探測(cè)過(guò)
            if (colors[a] == 'white') {
              colors[a] = 'gray'
              que.enqueue(a)
            }
          }

          //4.5.處理頂點(diǎn)v
          handler(v)

          //4.6.頂點(diǎn)v所有白色的相鄰頂點(diǎn)都加入隊(duì)列后，將頂點(diǎn)v設(shè)置為黑色。此時(shí)黑色頂點(diǎn)v位于隊(duì)列最前面，進(jìn)入下一次while循環(huán)時(shí)會(huì)被取出
          colors[v] = 'black'
        }
      }

      //六.實(shí)現(xiàn)深度搜索(DFS)
      Graph.prototype.dfs = function(initV, handler){
        //1.初始化頂點(diǎn)顏色
        let colors = this.initializeColor()

        //2.從某個(gè)頂點(diǎn)開(kāi)始依次遞歸訪問(wèn)
        this.dfsVisit(initV, colors, handler)
      }

      //為了方便遞歸調(diào)用，封裝訪問(wèn)頂點(diǎn)的函數(shù)，傳入三個(gè)參數(shù)分別表示：指定的第一個(gè)頂點(diǎn)、顏色、處理函數(shù)
      Graph.prototype.dfsVisit = function(v, colors, handler){
        //1.將顏色設(shè)置為灰色
        colors[v] = 'gray'

        //2.處理v頂點(diǎn)
        handler(v)

        //3.訪問(wèn)v相連的其他頂點(diǎn)
        let vNeighbours = this.edges.get(v)
        for (let i = 0; i < vNeighbours.length; i++) {
          let a = vNeighbours[i];
          //判斷相鄰頂點(diǎn)是否為白色，若為白色，遞歸調(diào)用函數(shù)繼續(xù)訪問(wèn)
          if (colors[a] == 'white') {
            this.dfsVisit(a, colors, handler)
          }
          
        }

        //4.將v設(shè)置為黑色
        colors[v] = 'black'
      }
    }

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】JavaScript實(shí)現(xiàn)圖結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！