### 图

1. 邻接矩阵
2. 邻接表
3. 关联矩阵
• 邻接矩阵

• 邻接表

• 关联矩阵

function Graph() {  this.topPointArr = []    // 存储顶点, 笔者认为图的顶点是不会重复的  this.edgeMap = new Map() // 存储边}
// 往图里添加顶点Graph.prototype.addTopPoint = function(point) {  this.topPointArr.push(point)  this.edgeMap.set(point, [])}
// 往指定的点添加相邻的点Graph.prototype.addEdge = function(point1, point2) {  this.edgeMap.get(point1).push(point2)  this.edgeMap.get(point2).push(point1) // 这里默认没有方向, 所以两个点互相指向}
// 将图给打印出来Graph.prototype.log = function() {  let str = ''  let neighbour  for (let i of this.topPointArr) {    str += i + ' -> '    neighbour = this.edgeMap.get(i).join(' ')    str += neighbour + '\n'  }  return str}

var graph = new Graph()var topArr = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']for (let i of topArr) {  graph.addTopPoint(i)}
graph.addEdge('A', 'B')graph.addEdge('A', 'C')graph.addEdge('A', 'D')graph.addEdge('B', 'E')graph.addEdge('B', 'F')graph.addEdge('C', 'D')graph.addEdge('C', 'G')graph.addEdge('D', 'G')graph.addEdge('D', 'H')graph.addEdge('E', 'I')

A -> B C DB -> A E FC -> A D GD -> A C G HE -> B IF -> BG -> C DH -> DI -> E

### 广度优先遍历(BFS)

• 创建队列 u, 将标灰的顶点插入队列;
• 若队列 u 不为空;
• 从队列取出值 v;
• 将 v 的相邻节点标灰并插入队列 u;

Queue实现
function Queue() {  this.items = []}
Queue.prototype.push = function(item) {  this.items.push(item)}
Queue.prototype.shift = function() {  return this.items.shift()}
Queue.prototype.isEmpty = function() {  return this.items.length === 0}
Queue.prototype.size = function() {  return this.items.length}
Queue.prototype.clear = function() {  this.items = []}
Graph.prototype.bfs = function(v, callback) {  const obj = {}
for (let i of this.topPointArr) { // 初始化颜色    obj[i] = 'white'  }
const queue = new Queue()  obj[v] = 'gray'
queue.push(v)
let shiftQueue, neighbour
while (!queue.isEmpty()) {    shiftQueue = queue.shift()    neighbour = this.edgeMap.get(shiftQueue)
for (let i of neighbour) {      if (obj[i] === 'white') {        obj[i] = 'gray'        queue.push(i)      }    }
if (callback) {      callback(shiftQueue)    }  }}

graph.bfs('A', (shiftQueue) => {  console.log(shiftQueue)})

#### 广度优先遍历求最短路径

Graph.prototype.BFS = function(v) {  const obj = {}
const d = {}    // 新加入的变量存储距离  const prev = {} // 新加入的变量存储最短路径上先前的点
for (let i of this.topPointArr) { // 初始化颜色    obj[i] = 'white'    d[i] = 0    prev[i] = null  }
const queue = new Queue()  obj[v] = 'gray'
queue.push(v)
let shiftQueue, neighbour
while (!queue.isEmpty()) {    shiftQueue = queue.shift()    neighbour = this.edgeMap.get(shiftQueue)
for (let i of neighbour) {      if (obj[i] === 'white') {        obj[i] = 'gray'        queue.push(i)        d[i] = d[shiftQueue] + 1  // 这个地方卡主了~~~, 思路: 第二行的点距离第一行的点相差为 1, 第三行的点距离第二行的点相差为 1, 以此类推。        prev[i] = shiftQueue      }    }  }
return {    distance: d,    prev: prev  }}

{  distance: { A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3 }  prev: { A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E" }}

Graph.prototype.logMinPath = function(v) {  const { distance, prev } = this.BFS(v)  let path = ''  const arr = []  Object.keys(distance).map(r => {    path = r    while (prev[r]) { // 终止条件为 prev 中值为 null 时      path = prev[r] + ' - ' + path      r = prev[r]    }    arr.push(path)  })  return arr.join('\n')}

AA - BA - CA - DA - B - EA - B - FA - C - GA - D - HA - B - E - I

### 深度优先遍历(DFS)

Graph.prototype.dfs = function (v, callback) {  const obj = {}
for (let i of this.topPointArr) { // 初始化颜色    obj[i] = 'white'  }
let neighbour  const that = this  const find = function (v, color, cb) {    color[v] = 'gred'    if (cb) {      cb(v)    }    neighbour = that.edgeMap.get(v)    for (let i of neighbour) {      if (color[i] === 'white') {        find(i, color, cb)      }    }  }
find(v, obj, callback)}

graph.dfs('A', (shiftQueue) => {  console.log(shiftQueue)  // 打印结果: A B E I F C D G H})