【你該懂一點Javascript算法系列】之【圖類】的定義及深度優(yōu)先與廣度優(yōu)先搜索算法

qqlcbb 發(fā)布于2019-08-23 15:17 / 1396人閱讀

摘要：鄰接矩陣在鄰接矩陣實現(xiàn)中，由行和列都表示頂點，由兩個頂點所決定的矩陣對應(yīng)元素表示這里兩個頂點是否相連如果相連這個值表示的是相連邊的權(quán)重。直到返回到頂點完成探索具體還有版的深度和廣度優(yōu)先的算法，具體代碼奉上直達(dá)地址

圖
github直達(dá)地址 https://github.com/fanshyiis/...

在計算機(jī)科學(xué)中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結(jié)對（連接）。頂點用圓圈表示，邊就是這些圓圈之間的連線。頂點之間通過邊連接。

注意：頂點有時也稱為節(jié)點或者交點，邊有時也稱為鏈接。

一個圖可以表示一個社交網(wǎng)絡(luò)，每一個人就是一個頂點，互相認(rèn)識的人之間通過邊聯(lián)系。

理論上，圖就是一堆頂點和邊對象而已，但是怎么在代碼中來描述呢？
有兩種主要的方法：鄰接列表和鄰接矩陣。

鄰接列表：在鄰接列表實現(xiàn)中，每一個頂點會存儲一個從它這里開始的邊的列表。比如，如果頂點A 有一條邊到B、C和D，那么A的列表中會有3條邊

鄰接列表只描述了指向外部的邊。A 有一條邊到B，但是B沒有邊到A，所以 A沒有出現(xiàn)在B的鄰接列表中。查找兩個頂點之間的邊或者權(quán)重會比較費時，因為遍歷鄰接列表直到找到為止。

鄰接矩陣：在鄰接矩陣實現(xiàn)中，由行和列都表示頂點，由兩個頂點所決定的矩陣對應(yīng)元素表示這里兩個頂點是否相連、如果相連這個值表示的是相連邊的權(quán)重。例如，如果從頂點A到頂點B有一條權(quán)重為 5.6 的邊，那么矩陣中第A行第B列的位置的元素值應(yīng)該是5.6：

往這個圖中添加頂點的成本非常昂貴，因為新的矩陣結(jié)果必須重新按照新的行/列創(chuàng)建，然后將已有的數(shù)據(jù)復(fù)制到新的矩陣中。
所以使用哪一個呢？大多數(shù)時候，選擇鄰接列表是正確的。下面是兩種實現(xiàn)方法更詳細(xì)的比較。
假設(shè) V 表示圖中頂點的個數(shù)，E 表示邊的個數(shù)。

“檢查相鄰性” 是指對于給定的頂點，嘗試確定它是否是另一個頂點的鄰居。在鄰接列表中檢查相鄰性的時間復(fù)雜度是O(V)，因為最壞的情況是一個頂點與每一個頂點都相連。
在稀疏圖的情況下，每一個頂點都只會和少數(shù)幾個頂點相連，這種情況下相鄰列表是最佳選擇。如果這個圖比較密集，每一個頂點都和大多數(shù)其他頂點相連，那么相鄰矩陣更合適。

了解了圖的基本定義后我們來看下如何用es6的類class思想來實現(xiàn)圖類

首先我們先定義兩個輔助類

class Dictionary {
  constructor () {
    this.items = {}
  }

  has (key) {
    return key in this.items
  }

  set (key, val) {
    this.items[key] = val
  }

  delete (key) {
    if (this.has(key)) {
      delete this.items[key]
      return true
    } else {
      return false
    }
  }

  get (key) {
    return this.has(key)? this.items[key] : undefined
  }

  values () {
    let values = []
    for (let k in this.items) {
      if (this.has(k)) {
        values.push(this.items[k])
      }
    }
    return values
  }
}

class Queue {
  constructor () {
    this.items = []
  }

  enqueue (element) {
    this.items.push(element)
  }

  dequeue () {
    return this.items.shift()
  }

  isEmpty() {
    return this.items.length === 0
  }
}

Dictionary 字典類來輔助存貯鍵值對
Queue 隊列類來存貯隊列

//定義class Graph
class Graph {
  constructor () {
    this.vertices = []
    this.adjList = new Dictionary()
  }
}

定義Graph類并且在構(gòu)造函數(shù)里初始化字段
vertices 存儲點信息
adjList 存儲頂點間的鏈接關(guān)系

  addVertex (v) {
    this.vertices.push(v)
    this.adjList.set(v, [])
  }

  addEdge (v, w) {
    this.adjList.get(v).push(w)
  }

addVertex 添加頂點的方法，存貯在數(shù)組vertices，并且初始化adjList字典里的值
addEdge 添加單向邊 接收兩個值 在鄰接字典里加上從第一個頂點到第二個的關(guān)系

到這一個基本的類就完成了，我們可以通過測試代碼來測試

et graph = new Graph()
let mv = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
mv.map(val => {
  graph.addVertex(val)
})
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")

得到的圖

下面我們來定義一個功能來打印圖

  toString () {
    let s = ""
    for (let i = 0; i < this.vertices.length; i++) {
      s += this.vertices[i] + "->"
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        s += neighbors[j] + " "
      }
      s += "
"
    }
    return s
  }

執(zhí)行文件 node graph.js

得到結(jié)果

A->B C D 
B->E F 
C->D G 
D->G H 
E->I 
F->
G->

好到這就基本完成類的結(jié)構(gòu)了，下面進(jìn)行圖的遍歷

廣度優(yōu)先 - 數(shù)據(jù)結(jié)構(gòu) 隊列

先上代碼

  BFS (v, callback) {
    let color = this.initializeColor(),
        queue = new Queue()
    queue.enqueue(v)

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      color[u] = "grey"
      neighbors.map(val => {
        if (color[val] === "white") {
          color[val] = "grey"
          queue.enqueue(val)
        }
      })
      color[u] = "black"
      if (callback) {
        callback(u)
      }
    }
  }

基本思想如下
1.初始化各個頂點的顏色（白色 - 未訪問；灰色 - 已發(fā)現(xiàn)；黑色 - 已經(jīng)探索完）
2.初始化一個隊列
3.首先隊列入頂點 v
4.如果隊列不會空，則取隊列第一個進(jìn)行探索
5.探索過程中獲取當(dāng)前頂點的所有鄰接頂點，并推進(jìn)隊列
6.完成5后，標(biāo)記當(dāng)前為黑色

圖示例
A 探索隊列入 B - C - D
完成 A探索
出B 探索B 隊列再入 E - F 當(dāng)前 CDEF
完成 B探索
出C 探索隊列再入 G 當(dāng)前DEFG
。。。

直到所有頂點探索完

深度優(yōu)先 - 數(shù)據(jù)結(jié)構(gòu) 棧

先上代碼

  DFS (callback) {
    let color = this.initializeColor()
    this.vertices.map(val => {
      if (color[val] === "white") {
        this.dfsVisit(val, color, callback)
      }
    })
  }

  dfsVisit (u, color, callback) {
    color[u] = "grey"
    if (callback) {
      callback(u)
    }
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === "white") {
        this.dfsVisit(val, color, callback)
      }
    })
    color[u] = "black"
  }

深度優(yōu)先的原則以棧為數(shù)據(jù)結(jié)構(gòu)

基本思想如下
1.初始化各個頂點的顏色（白色 - 未訪問；灰色 - 已發(fā)現(xiàn)；黑色 - 已經(jīng)探索完）
2.對頂點進(jìn)行遍歷并進(jìn)行dfsVisit函數(shù)探索
3.優(yōu)先進(jìn)行最新探索的邊進(jìn)行深度探索，完成后標(biāo)記探索完成

基本步驟如下
探索A
發(fā)現(xiàn)BCD
探索B
發(fā)現(xiàn)EF
探索E
發(fā)現(xiàn)I
探索I，完畢標(biāo)記I為以探索
回到上個分支遍歷接著執(zhí)行探索F
完成
標(biāo)記F為以探索
。。。
直到返回到頂點A

完成探索

具體還有PLus版的深度和廣度優(yōu)先的算法，具體代碼奉上

/*
* @Author: koala_cpx
* @Date:   2019-01-24 10:48:01
* @Last Modified by:   koala_cpx
* @Last Modified time: 2019-01-24 10:56:33
*/
class Dictionary {
  constructor () {
    this.items = {}
  }

  has (key) {
    return key in this.items
  }

  set (key, val) {
    this.items[key] = val
  }

  delete (key) {
    if (this.has(key)) {
      delete this.items[key]
      return true
    } else {
      return false
    }
  }

  get (key) {
    return this.has(key)? this.items[key] : undefined
  }

  values () {
    let values = []
    for (let k in this.items) {
      if (this.has(k)) {
        values.push(this.items[k])
      }
    }
    return values
  }
}

class Queue {
  constructor () {
    this.items = []
  }

  enqueue (element) {
    this.items.push(element)
  }

  dequeue () {
    return this.items.shift()
  }

  isEmpty() {
    return this.items.length === 0
  }
}

class Graph {
  constructor () {
    this.vertices = []
    this.adjList = new Dictionary()
    this.time = 0
  }

  addVertex (v) {
    this.vertices.push(v)
    this.adjList.set(v, [])
  }

  addEdge (v, w) {
    this.adjList.get(v).push(w)
    // this.adjList.get(w).push(v)
  }

  BFS (v, callback) {
    let color = this.initializeColor(),
        queue = new Queue()
    queue.enqueue(v)

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      color[u] = "grey"
      neighbors.map(val => {
        if (color[val] === "white") {
          color[val] = "grey"
          queue.enqueue(val)
        }
      })
      color[u] = "black"
      if (callback) {
        callback(u)
      }
    }
  }

  BFSPlus (v) {
    let color = this.initializeColor(),
        queue = new Queue(),
        d = [],
        pred = []

    queue.enqueue(v)
    this.vertices.map(val => {
      d[val] = 0
      pred[val] = null
    })

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      
      color[u] = "grey"
      neighbors.map(val => {
        if (color[val] === "white") {
          color[val] = "grey"
          d[val] = d[u] + 1
          pred[val] = u
          queue.enqueue(val)
        }
      })
      color[u] = "black"
    }

    return {
      distances: d,
      predecessors: pred
    }
  }

  DFS (callback) {
    let color = this.initializeColor()
    this.vertices.map(val => {
      if (color[val] === "white") {
        this.dfsVisit(val, color, callback)
      }
    })
  }

  DFSPlus () {
    let color = this.initializeColor(),
        d = [],
        f = [],
        p = []

    this.time = 0
    this.vertices.map(val => {
      f[val] = 0
      d[val] = 0
      p[val] = null
    })

    this.vertices.map(val => {
      if (color[val] === "white") {
        this.dfsPlusVisit(val, color, d, f, p)
      }
    })

    return {
      discovery: d,
      finished: f,
      predecessors: p
    }
  }

  dfsPlusVisit (u, color, d, f, p) {
    console.log("discovery" + u)
    color[u] = "grey"
    d[u] = ++this.time
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === "white") {
        p[val] = u
        this.dfsPlusVisit(val, color, d, f, p)
      }
    })
    color[u] = "black"
    f[u] = ++this.time
    console.log("explored" + u)
  }

  dfsVisit (u, color, callback) {
    color[u] = "grey"
    if (callback) {
      callback(u)
    }
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === "white") {
        this.dfsVisit(val, color, callback)
      }
    })
    color[u] = "black"
  }

  outPut(obj) {
    let fromVertex = this.vertices[0],
        { predecessors } = obj
    this.vertices.map(val => {
      let path = new Array()
      for (var v = val; v !== fromVertex; v = predecessors[v]) {
        path.push(v)
      }
      path.push(fromVertex)
      let s = path.pop()
      while (path.length !== 0) {
        s += " -- " + path.pop()
      }
      console.log(s)
    })
  }

  initializeColor () {
    let color = []
    this.vertices.map(val => {
      color[val] = "white"
    })
    return color
  }

  toString () {
    let s = ""
    for (let i = 0; i < this.vertices.length; i++) {
      s += this.vertices[i] + "->"
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        s += neighbors[j] + " "
      }
      s += "
"
    }
    return s
  }
}

let a = new Dictionary()
a.set("ss", 1111)
a.set("s1", 1111)
a.set("s2", 1112)
a.set("s3", 1114)

a.delete("s2")
console.log(a.has("s3"))

console.log(a.values())

let graph = new Graph()
let mv = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
mv.map(val => {
  graph.addVertex(val)
})
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")

console.log(graph.toString())

function print(val) {
  console.log("vis" + val)
}

graph.BFS("A", print)
console.log(graph.BFSPlus("A"))
graph.outPut(graph.BFSPlus("A"))
graph.DFS(print)
console.log(graph.DFSPlus())

let graph2 = new Graph()
let mv2 = ["A", "B", "C", "D", "E", "F"]
mv2.map(val => {
  graph2.addVertex(val)
})
graph2.addEdge("A", "C")
graph2.addEdge("A", "D")
graph2.addEdge("B", "D")
graph2.addEdge("B", "E")
graph2.addEdge("C", "F")
graph2.addEdge("F", "E")

let r = graph2.DFSPlus()
console.log(r)

github直達(dá)地址 https://github.com/fanshyiis/...

云服務(wù)器 GPU云服務(wù)器廣度優(yōu)先搜索算法代碼最佳優(yōu)先搜索算法廣度優(yōu)先搜索深度優(yōu)先搜索

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/101821.html

發(fā)表評論

登陸后可評論

0條評論

qqlcbb

男|高級講師

我要關(guān)注我要私信

TA的文章

手把手教你學(xué)Dapr

閱讀 2202·2021-11-18 10:07
DMIT：國外高端VPS雲(yún)服務(wù)器特價優(yōu)惠，美國/香港/日本可選，高端CN2 GIA優(yōu)質(zhì)線路大帶寬不限

閱讀 3598·2021-09-04 16:48
CSS 黑魔法小技巧，讓你少寫不必要的JS，代碼更優(yōu)雅

閱讀 3303·2019-08-30 15:53
white-space:nowrap 的妙用

閱讀 1313·2019-08-30 12:55
彈性布局示例

閱讀 2515·2019-08-29 15:08
前端純原生代碼實現(xiàn)2048

閱讀 3221·2019-08-29 15:04
CSS盒模型完整介紹

閱讀 2952·2019-08-29 14:21
[學(xué)習(xí)css系列]純css實現(xiàn)移入移出效果

閱讀 2972·2019-08-29 11:21

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

【你該懂一點Javascript算法系列】之【圖類】的定義及深度優(yōu)先與廣度優(yōu)先搜索算法

相關(guān)文章

**【你該懂一點Javascript算法系列】之單源最短路徑 - Dijkstra算法**

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 圖**

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 深度優(yōu)先搜索算法**

算法-圖和圖算法

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 廣度優(yōu)先搜索算法**

發(fā)表評論

0條評論

qqlcbb

男|高級講師

TA的文章

手把手教你學(xué)Dapr

DMIT：國外高端VPS雲(yún)服務(wù)器特價優(yōu)惠，美國/香港/日本可選，高端CN2 GIA優(yōu)質(zhì)線路大帶寬不限

CSS 黑魔法小技巧，讓你少寫不必要的JS，代碼更優(yōu)雅

white-space:nowrap 的妙用

彈性布局示例

前端純原生代碼實現(xiàn)2048

CSS盒模型完整介紹

[學(xué)習(xí)css系列]純css實現(xiàn)移入移出效果

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

【你該懂一點Javascript算法系列】之【圖類】的定義及深度優(yōu)先與廣度優(yōu)先搜索算法

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！