图

是什么

• 图是网络结构的抽象模型。
• 图是一组由边连接的节点（或顶点）。 因为任何二元关系都可以用图来表示，所以图的学习就显得尤为重要。

一个图 G = (V, E)由以下元素组成。

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

图的相关术语

• 相邻顶点：由一条边连接在一起的顶点。上图中，A 和 B 是相邻的，A 和 D 是相邻的，A 和 C 是相邻的，A 和 E 不是相邻的。
• 度：一个顶点的度是其相邻顶点的数量。上图中，A 和其他三个顶点相连接，因此 A 的度为 3；E 和其他两个顶点相连，因此 E 的度为 2。
• 路径：是顶点 v1, v2, …, vk 的一个连续序列，其中 vi 和 vi+1 是相邻的。在上图中，其中包含路径 A B E I 和 A C D G。
• 简单路径要求不包含重复的顶点 比如，上图中的 A D G 就是一条简单路径。
• 环也是一个简单路径，因为环的最后一个顶点和第一个顶点是同一个顶点。比如说上图中的 A D C A 环。
• 如果图中不存在环，则称该图是无环的。
• 如果图中每两个顶点间都存在路径，则该图是连通的。

怎么做

class Dictionary{
  constructor(){
    this.items = {}
  }
  // 查:
  has(key){
    // return !!this.items[key]
    return key in this.items
  }
  // 查:
  size(){
    return Object.values(this.items).length
  }
  get(key){
    if(this.has(key)){
       return this.items[key]
    }
    return undefined
  }
  keys(){
    return Object.keys(this.items)
  }
  values(){
    return Object.values(this.items)
  }
  // 增
  set(key,value){
    this.items[key] = value
  }
  // 删
  remove(key){
    if(this.has(key)){
          delete this.items[key]
          return true
    }
    return false
  }
}

class Graph {
  constructor() {
    // 顶点列表
    this.vertices = []
    // 字典，用来存储邻接表
    this.adjList = new Dictionary()
  }

  // 增:添加顶点
  addVertex(vertex) {
    // 接受顶点作为参数，将该顶点添加到顶点列表中
    this.vertices.push(vertex)
    // 在邻接表中设置该顶点作为键对应的字典值为一个空数组
    this.adjList.set(vertex, [])
  }
  // 增:添加边（连接 vertex 中的顶点）
  addEdge(v1, v2) {
    // 首先，通过将v2加入到v1的邻接表中，我们添加了一条自顶点v1到顶点v2的边。
    this.adjList.get(v1).push(v2)
    // 由于我们做的是无向图，所以还需要添加一条自w向v的边
    this.adjList.get(v2).push(v1)
  }
  // 查:获取每个顶点的相邻点
  toString() {
    let str = ''
    for (let i = 0; i < this.vertices.length; i++) {
      str += `${this.vertices[i]} =>`
      // 然后，取该顶点的邻接表，并进行迭代，同样将迭代结果加入字符串中，
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        str += `${neighbors[j]} `
      }
      // 迭代完成后末尾加换行符，用于将每个顶点和它的邻接表在一行显示，最终得到一个漂亮的邻接表类型的图
      str += '\n'
    }
    return str
  }
  // 改
}

// 首先我们实例化一个图
let graph = new Graph();


// 循环将下面的顶点添加到实例化的图中
let myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (let i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i])
}
console.log(graph)
// // 接下来，我们添加边, 随意添加
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())

解决了什么问题

参考

• 数据结构之图的创建