数据结构--笔记-图

[lulusir]

图

typescript实现版本

图是网络结构的抽象，图是一组由边连接的节点。

G = (V, E)

• V: 一组顶点
• E: 一组边，连接V中的顶点

相关术语

• 相邻顶点：由一条边连接在一起的顶点称为相邻顶点
• 度：一个顶点的度是其相邻顶点的数量
• 路径：路径是顶点v1，v2...vk的一个连续序列，其中vi和vi+1是相邻的。
• 简单路径： 简单路径要求不包含重复的顶点
• 如果途中不存在环，则成为无环的图
• 连通的图： 图中的每两个顶点都存在路径
• 有向，无向，有无权重

图的表示

邻接矩阵

用二维数组来表示图的关系，如果索引为i的节点和索引为j的节点相邻，则array[i][j] = 1 ,否则 array[i][j] = 0
不是强连接的图（稀疏图）用邻接矩阵来表示会存放很多的0，造成空间浪费。而且二维数组不够灵活。

邻接表

边表，存储的是顶点的序号，和指向下一个的指针

关联矩阵

关联矩阵一般用于边的数量比顶点多的情况下，可以节省空间和内存
在关联矩阵中，矩阵的行表示顶点，列表示边。

创建图类

class Graph {
  constructor () {
    this._veritices = [] // 用一个数组来储存所有顶点的名字
    this._adjList = new Map() // 用字典来储存邻接表，字典使用顶点的名字为键，邻接顶点列表为值
  }
  addVertex (v) {
    this._veritices.push(v) // 存入顶点
    this._adjList.set(v, []) // 初始化顶点对应的列表
  }
  addEdge (v, w) {
    this._adjList.get(v).push(w) // 将w顶点添加到v的邻接表中
    this._adjList.get(w).push(v) // 如果是无向图，则把v顶点也添加到w的邻接表中
  }
  toString () {
    let s = ''
    this._veritices.forEach(ver => {
      s += `${ver} ==> `
      this._adjList.get(ver).forEach(neibor => {
        s += neibor + ' '
      })
      s += '\n'
    })
    return s
  }
}
var graph = new Graph()
var myVeritices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
myVeritices.forEach(v => {
  graph.addVertex(v)
})
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')

// 输出结果
A ==> B C D 
B ==> A E F 
C ==> A D G 
D ==> A C G H 
E ==> B I 
F ==> B 
G ==> C D 
H ==> D 
I ==> E

图的遍历

广度优先搜索（BFS）

class Graph {
  ...
  bfs (v, cb) {
    const color = this.initializeColor()
    const queue = new Queue()
    queue.enqueue(v)

    while (!queue.isEmpty()) {
      const u = queue.dequeue()
      const neighbors = this._adjList.get(u)
      color[u] = 'grey'
      neighbors.forEach(v => {
        if (color[v] === 'white') {
          color[v] = 'grey'
          queue.enqueue(v)
        }
      })
      color[u] = 'back'

      if (cb) {
        cb(u)
      }
    }
  }
}

// 返回路径和追溯点
  bfs2 (v, cb) {
    const color = this.initializeColor()
    const queue = new Queue()
    const d = [] // v到u的距离
    const pred = [] // 钱说点
    queue.enqueue(v)
    // 初始化
    this._veritices.forEach(v => {
      d[v] = 0
      pred[v] = null
    })

    while (!queue.isEmpty()) {
      const u = queue.dequeue()
      const neighbors = this._adjList.get(u)
      color[u] = 'grey'
      neighbors.forEach(v => {
        if (color[v] === 'white') {
          color[v] = 'grey'
          d[v] = d[u] + 1
          pred[v] = u
          queue.enqueue(v)
        }
      })
      color[u] = 'back'

      if (cb) {
        cb(u)
      }
    }

    return {
      distances: d,
      predecessors: pred
    }
  }

寻找最短路径

// 路径追溯
var fromVertex = myVeritices[0]
myVeritices.forEach(toVertex => {
  var path = new Stack()
  for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
    path.push(v)
  }
  path.push(fromVertex)
  var s = path.pop()
  while (!path.isEmpty()) {
    s += ' - ' + path.pop()
  }
  console.log(s)
})
// 输出结果
A
A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I

深度优先搜索

  dfs (cb) {
    const color = this.initializeColor()
    this._veritices.forEach(v => {
      if (color[v] === 'white') {
        this._dfsVisit(v, color, cb)
      }
    })
  }
  
  _dfsVisit (u, color, cb) {
    color[u] = 'grey'
    if (cb) {
      cb(u)
    }
    const neighbors = this._adjList.get(u)
    neighbors.forEach(v => {
      if (color[v] === 'white') {
        this._dfsVisit(v, color, cb)
      }
    })
    color[u] = 'black'
  }

// 探索深度优先算法
  DFS () {
    const color = this.initializeColor(),
      d = {},
      f = {},
      p = {}
    let time = 0
    this._veritices.forEach(v => {
      f[v] = 0
      d[v] = 0
      p[v] = null
    })

    this._veritices.forEach(v => {
      if (color[v] === 'white') {
        _DFSVisit.call(this, v, color, d, f, p)
      }
    })
    function _DFSVisit (v, color, d, f, p) {
      console.log('discovered ' + v)
      color[v] = 'grey'
      d[v] = ++time
      const neighbors = this._adjList.get(v)
      neighbors.forEach(w => {
        if (color[w] === 'white') {
          p[w] = v
          _DFSVisit.call(this, w, color, d, f, p)
        }
      })
      color[v] = 'black'
      f[v] = ++time
      console.log('explored ' + v)
    }
    return {
      discovery: d,
      finished: f,
      predecessors: p
    }
  }