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

qqlcbb 發布于2019-08-23 15:17 / 1340人閱讀

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

圖
github直達地址 https://github.com/fanshyiis/...

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

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

一個圖可以表示一個社交網絡，每一個人就是一個頂點，互相認識的人之間通過邊聯系。

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

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

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

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

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

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

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

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

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類并且在構造函數里初始化字段
vertices 存儲點信息
adjList 存儲頂點間的鏈接關系

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

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

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

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

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
  }

執行文件 node graph.js

得到結果

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

好到這就基本完成類的結構了，下面進行圖的遍歷

廣度優先 - 數據結構 隊列

先上代碼

  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.初始化各個頂點的顏色（白色 - 未訪問；灰色 - 已發現；黑色 - 已經探索完）
2.初始化一個隊列
3.首先隊列入頂點 v
4.如果隊列不會空，則取隊列第一個進行探索
5.探索過程中獲取當前頂點的所有鄰接頂點，并推進隊列
6.完成5后，標記當前為黑色

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

直到所有頂點探索完

深度優先 - 數據結構 棧

先上代碼

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

深度優先的原則以棧為數據結構

基本思想如下
1.初始化各個頂點的顏色（白色 - 未訪問；灰色 - 已發現；黑色 - 已經探索完）
2.對頂點進行遍歷并進行dfsVisit函數探索
3.優先進行最新探索的邊進行深度探索，完成后標記探索完成

基本步驟如下
探索A
發現BCD
探索B
發現EF
探索E
發現I
探索I，完畢標記I為以探索
回到上個分支遍歷接著執行探索F
完成
標記F為以探索
。。。
直到返回到頂點A

完成探索

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

/*
* @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直達地址 https://github.com/fanshyiis/...

云服務器 GPU云服務器廣度優先搜索算法代碼最佳優先搜索算法廣度優先搜索深度優先搜索

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101821.html

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

摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。 Javascript算法系列 - 單源最短路徑 - Dijkstra算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有...

SoapEye 2019-08-23 15:04 評論0 收藏0
學習JavaScript數據結構與算法 — 圖

摘要：圖關聯矩陣在關聯矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數是，邊的數量是，用鄰接矩陣表示圖需要的空間是，而使用關聯矩陣表示圖需要的空間是。廣度優先搜索算法數據結構是隊列。深度優先搜索算法數據結構是棧。定義圖和散列表、二叉樹一樣，是一種非線性數據結構。如圖1所示，圖由一系列頂點以及連接頂點的邊構成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和...

yiliang 2019-08-22 11:09 評論0 收藏0
學習JavaScript數據結構與算法 — 深度優先搜索算法

摘要：深度優先搜索上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。用深度優先搜索算法對圖中的任務圖進行拓撲排序最終各頂點的發現和探索完成時間會保存在中。深度優先搜索（DFS）上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中深度優先搜索算法會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最后一個頂點，接著原路回退并探索下一條路徑。換句話說，它是先深度后廣...

李增田 2019-08-22 11:09 評論0 收藏0
算法-圖和圖算法

摘要：圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模比如對交通流量建模頂點可以表示街道的十字路口邊可以表示街道加權的邊可以表示限速或者車道的數量建模人員可以用這個系統來判斷最佳路線及最有可能堵車的街道任何運輸系統都可以用圖來建模比如圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模. 比如對交通流量建模, 頂點可以表示街道的十字路口, 邊可以表示街道. 加權的邊...

Anshiii 2019-08-23 12:15 評論0 收藏0
學習JavaScript數據結構與算法 — 廣度優先搜索算法

摘要：廣度優先搜索上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。其它最短路徑算法對于加權圖的最短路徑，廣度優先算法可能并不合適。廣度優先搜索（BFS）上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的...

eternalshallow 2019-08-22 11:09 評論0 收藏0