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

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

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

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

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

注意：頂點(diǎn)有時(shí)也稱(chēng)為節(jié)點(diǎn)或者交點(diǎn)，邊有時(shí)也稱(chēng)為鏈接。

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

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

鄰接列表：在鄰接列表實(shí)現(xiàn)中，每一個(gè)頂點(diǎn)會(huì)存儲(chǔ)一個(gè)從它這里開(kāi)始的邊的列表。比如，如果頂點(diǎn)A 有一條邊到B、C和D，那么A的列表中會(huì)有3條邊

鄰接列表只描述了指向外部的邊。A 有一條邊到B，但是B沒(méi)有邊到A，所以 A沒(méi)有出現(xiàn)在B的鄰接列表中。查找兩個(gè)頂點(diǎn)之間的邊或者權(quán)重會(huì)比較費(fèi)時(shí)，因?yàn)楸闅v鄰接列表直到找到為止。

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

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

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

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

首先我們先定義兩個(gè)輔助類(lèi)

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 字典類(lèi)來(lái)輔助存貯鍵值對(duì)
Queue 隊(duì)列類(lèi)來(lái)存貯隊(duì)列

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

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

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

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

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

到這一個(gè)基本的類(lèi)就完成了，我們可以通過(guò)測(cè)試代碼來(lái)測(cè)試

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")

得到的圖

下面我們來(lái)定義一個(gè)功能來(lá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->

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

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

先上代碼

  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.初始化各個(gè)頂點(diǎn)的顏色（白色 - 未訪問(wèn)；灰色 - 已發(fā)現(xiàn)；黑色 - 已經(jīng)探索完）
2.初始化一個(gè)隊(duì)列
3.首先隊(duì)列入頂點(diǎn) v
4.如果隊(duì)列不會(huì)空，則取隊(duì)列第一個(gè)進(jìn)行探索
5.探索過(guò)程中獲取當(dāng)前頂點(diǎn)的所有鄰接頂點(diǎn)，并推進(jìn)隊(duì)列
6.完成5后，標(biāo)記當(dāng)前為黑色

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

直到所有頂點(diǎn)探索完

深度優(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.初始化各個(gè)頂點(diǎn)的顏色（白色 - 未訪問(wèn)；灰色 - 已發(fā)現(xiàn)；黑色 - 已經(jīng)探索完）
2.對(duì)頂點(diǎn)進(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為以探索
回到上個(gè)分支遍歷接著執(zhí)行探索F
完成
標(biāo)記F為以探索
。。。
直到返回到頂點(diǎn)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/...

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/101821.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

qqlcbb

男|高級(jí)講師

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

TA的文章

手把手教你學(xué)Dapr

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

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

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

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

閱讀 2464·2019-08-29 15:08
前端純?cè)a實(shí)現(xiàn)2048

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

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

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

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

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

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

相關(guān)文章

**【你該懂一點(diǎ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ā)表評(píng)論

0條評(píng)論

qqlcbb

男|高級(jí)講師

TA的文章

手把手教你學(xué)Dapr

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

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

white-space:nowrap 的妙用

彈性布局示例

前端純?cè)a實(shí)現(xiàn)2048

CSS盒模型完整介紹

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

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

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

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

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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