数据结构|图-一一网

这是我参与更文挑战的第1天，活动详情查看：更文挑战

什么是”图”?

图是一种非常重要，且跟现实息息相关的数据结构，它是网络结构的抽象模型。

举个非常常见的例子:

我们每天在使用百度、高德地图进行导航时，城市的地图就是一种图的结构。

我们使用QQ、微信、Twitter、Facebook等社交软件，我们的好友关系网也是一种图的结构。

不仅如此，我们还可以使用图来表示道路、航班以及通信。

图的相关术语

一个图由 G = (V,E)组成。

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

顶点:

图最基本的单元，也就是图中的节点。

边:

顶点之间的关联关系，被称为边。

相邻顶点:

由一条边连接在一起的顶点，被称为相邻顶点。

度:

一个顶点包含的相邻顶点的数量，被称为度。

权重和带权图:

有些图中，每一条边并不是完全等同的。如在地铁线路组成的图中，A站到B站的距离是3km，B站到C站的距离是5km，则该数值便是图的权重，而这种图，则被称为带权图。

有向图:

如果图中节点之间的边线是单向的，则被称为有向图。

无向图:

如果图中节点之间的边线是双向的，或者没有一个明确的指向，则被称为无向图。

常用代码实现图的几种方法

邻接矩阵

图最常见的实现是邻接矩阵，也就是使用二维数组，表达各个顶点之间的关联关系。

如上图所示，顶点1到顶点2之间有边关联，则矩阵中的元素[0][1]的值为1;顶点3到顶点1没有关联，则矩阵[2][0]的值为0。

图上的邻接矩阵的代码表示:

let graphMatrix = [
    [
        0,1,1
    ],
    [
        0,0,0
    ],
    [
        0,1,0
    ]
]
复制代码

邻接表

邻接矩阵虽然能表示图结构，但是占用了太多的空间。而邻接表，是图结构的另外一种表示函数。邻接表由图中每个顶点的相邻顶点列表所组成，可以使用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。

代码实现

这里以邻接表为例，实现一个图(Graph)。

import Dictionary from "../Dictionary/app.js";

export default class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // 接收isDirected表示图是否有向,默认情况下图是无向的
    this.vertices = []; //初始化一个数组，用于存储图中所有顶点的名字
    this.adjList = new Dictionary(); // 创建一个字典实例，用来存储邻接表(字典将会使用顶点的名字作为键-key，邻接顶点列表作为值-value)
  }
  /**
   * 向图中添加一个新顶点
   * @param {string} v 需要向图中添加的顶点
   */
  addVertex(v) {
    if (!this.vertices.includes(v)) {
      // 如果这个顶点不存在图中 Array.prototype.includes() 判断数组是否包含特定的元素
      this.vertices.push(v); // 则将该顶点添加到顶点列表中
      this.adjList.set(v, []); // 并且在邻接表中，设置新插入的顶点(v)作为键(key),对应的字典值(value)为一个空数组
    }
  }
  /**
   * 向图中添加两点之间的边
   * @param {string} a 传入要添加边的顶点a
   * @param {string} b 传入要添加边的顶点b
   */
  addEdge(a, b) {
    // 先校验两个顶点是否存在图中
    if (!this.adjList.get(a)) {
      //如果图中不存在顶点a，则将它加入顶点列表
      this.addVertex(a);
    }
    if (!this.adjList.get(b)) {
      // 如果图中不存在顶点b，则将它加入顶点列表
      this.addVertex(b);
    }
    this.adjList.get(a).push(b); // 将顶点a加入到顶点b的邻接表(等于添加了一条自顶点a到顶点b的边)
    if (this.isDirected !== true) {
      // 如果图为无向图
      this.adjList.get(b).push(a); // 还要加将顶点b加入到顶点a的领接表
    }
  }
  /**
   * 返回图的顶点列表
   * @returns {array}
   */
  getVertices() {
    return this.vertices;
  }
  /**
   * 返回图的邻接表
   * @returns {any}
   */
  getAdjList() {
    return this.adjList;
  }
  /**
   * 将图以字符串的方式输出
   * @returns {string}
   */
  toString() {
    let s = "";
    for (let i = 0; i < this.vertices.length; i++) { // 迭代图的顶点列表(vertices)
      s += `${this.vertices[i]} -> `; // 将顶点的名字加入字符串中
      const neighbors = this.adjList.get(this.vertices[i]); // 接着取得该顶点对应的邻接表
      for (let j = 0; j < neighbors.length; j++) { //遍历该邻接表(neighbors)
        s += `${neighbors[j]} `; // 将相邻顶点加入我们的字符串
      }
      s += "\n"; // 邻接表迭代完成后，给我们的字符串添加一个换行符
    }
    return s; // 输入打印成字符串的图
    /**
     *  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 
     */
  }
}

复制代码