数据结构与算法(十一)-图(Graph)_图结构

图结构(Graph)

一、图的介绍

1. 什么是图？

• 图结构是一种与树结构有些相似的数据结构
• 图论是数学的一个分支，并且，在数学中，树是图的一种
• 图论以图为研究对象，研究顶点和边组成的图形的数学理论和方法
• 主要的研究目的为：事物之间的联系，顶点代表事物，边代表两个事物间的关系

2.图的特点

• 一组顶点：通常用 V （Vertex）表示顶点的集合
• 一组边：通常用E（Edge）表示边的集合
  • 边是顶点和顶点之间的连线
  • 边可以是有向的，也可以是无向的。比如A----B表示无向，A —> B 表示有向

3. 图的常用术语：

• 顶点：表示图中的一个节点
• 边：表示顶点和顶点给之间的连线
• 相邻顶点：由一条边连接在一起的顶点称为相邻顶点
• 度：一个顶点的度是相邻顶点的数量
• 路径：
  • **简单路径：**简单路径要求不包含重复的顶点
  • 回路：第一个顶点和最后一个顶点相同的路径称为回路
• 无向图：图中的所有边都是没有方向的
• 有向图：图中的所有边都是有方向的
• **无权图：**无权图中的边没有任何权重意义
• **带权图：**带权图中的边有一定的权重含义

4. 图的表示

4.1 邻接矩阵

表示图的常用方式为：邻接矩阵，如下图所示

• 可以使用二维数组来表示邻接矩阵
• 邻接矩阵让每个节点和一个整数相关联，该整数作为数组的下标值
• 使用一个二维数组来表示顶点之间的连接

邻接矩阵表示法示例，如上图所示：

• 二维数组中的0表示没有连线，1表示有连线
  • 如：A[ 0 ] [ 3 ] = 1，表示 A 和 C 之间有连接
• 邻接矩阵的对角线上的值都为0，表示A - A ，B - B，等自回路都没有连接（自己与自己之间没有连接）
• 若为无向图，则邻接矩阵应为对角线上元素全为0的对称矩阵

邻接矩阵存在的问题：

• 如果图是一个稀疏图，那么邻接矩阵中将存在大量的 0，造成存储空间的浪费

4.2 邻接表

另外一种表示图的常用方式为：邻接表，如下图所示

• 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成
• 这个列表可用多种方式存储，比如：**数组/链表/字典（哈希表）**等都可以

如上图所示：

• 图中可清楚看到A与B、C、D相邻，假如要表示这些与A顶点相邻的顶点（边），可以通过将它们作为A的值（value）存入到对应的数组/链表/字典中
• 之后，通过键（key）A，可以十分方便地取出对应的数据

邻接表的问题：

• 邻接表可以简单地得出出度，即某一顶点指向其他顶点的个数；
• 但是，邻接表计算入度（指向某一顶点的其他顶点的个数称为该顶点的入度）十分困难，此时需要构造逆邻接表才能有效计算入度

二、图结构的封装

这里我们采用邻接表的方式进行封装，使用之前封装过的字典结构（也可以理解为Map）来存储临近表

2.1 图类的创建

function Graph() {
  this.vertexes = []; // 存放顶点
  this.adList = new Dirtioany(); // 使用字典结构存放 边 信息
}
1
2
3
4

2.2 添加顶点和边

• 我们需要创建一个数组对象vertexes存储图的顶点

• 创建一个字典对象edges，来存储图的边，其中key为顶点值，value为存储key顶点相邻顶点的数组

• 如下图所示

// 1.添加顶点
Graph.prototype.addVertex = function (val) {
  this.vertexes.push(val); // 添加顶点
  this.adList.set(val, []); // 初始化顶点对应的边
};

// 2.添加边
Graph.prototype.addEdge = function (val1, val2) {
  // 因为边是相互存在的，所以需要存储关联两个顶点的信息
  // 这里实现的是无向图，所以不考虑方向的问题
  this.adList.get(val1).push(val2);
  this.adList.get(val2).push(val1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 实现toString()方法

为图类Graph添加toString方法，实现以邻接表的形式输出图中各顶点

// 3.toString方法
Graph.prototype.toString = function () {
  var resString = "";
  for (var i = 0; i < this.vertexes.length; i++) {
    resString += this.vertexes[i] + "->";
    var adList = this.adList.get(this.vertexes[i]);
    for (var j = 0; j < adList.length; j++) {
      resString += adList[j] + " ";
    }
    resString += "\n";
  }
  return resString;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

测试代码

// 测试代码
let graph = new Graph();

// 添加顶点
let myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (let i = 0; i < myVertexes.length; i++) {
  graph.addVertex(myVertexes[i]);
}

// 添加边
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());
// 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.4 图的遍历方式

图的遍历思想：

• 图的遍历思想与树的遍历思想一样，意味着需要将图中所有的顶点都访问一遍，并且不能有重复的访问（上面的toString方法会重复访问）

遍历图的两种算法：

• 广度优先搜索（Breadth - First Search，简称BFS）
• 深度优先搜索（Depth - First Search，简称DFS）
• 两种遍历算法都需要指定第一个被访问的顶点

为了记录顶点是否被访问过，这里使用三种颜色来表示它们的状态

• 白色：表示该顶点还没有被访问过
• 灰色：表示该顶点被访问过，但其相邻顶点并未完全被访问过
• 黑色：表示该顶点被访问过，且其所有相邻顶点都被访问过

首先封装initializeColor方法将图中的所有顶点初始化为白色，代码实现如下：

/**
* 4.初始化顶点颜色
* 白色表示该顶点还没有被访问.
* 灰色表示该顶点被访问过, 但并未被探索过.
* 黑色表示该顶点被访问过且被完全探索过.
*/
Graph.prototype._initColors = function () {
  var colors = [];
  for (var i = 0; i < this.vertexes.length; i++) {
    colors[this.vertexes[i]] = "white";
  }
  return colors;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2.5 广度优先搜索(BFS)

思路：

• 广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻顶点，就像一次访问图的一层
• 也可以说是先宽后深地遍历图中的各个顶点

实现思路：

基于队列可以简单地实现广度优先搜索算法：

• 首先创建一个队列Q（尾部进，首部出）
• 调用封装的initializeColor方法将所有顶点初始化为白色
• 指定第一个顶点A，将A标注为灰色（被访问过的节点），并将A放入队列Q中
• 循环遍历队列中的元素，只要队列Q非空，就执行以下操作
  • 先将灰色的A从Q的首部取出
  • 取出A后，将A的所有未被访问过（白色）的相邻顶点依次从队列Q的尾部加入队列，并变为灰色。以此保证，灰色的相邻顶点不重复加入队列
  • A的全部相邻节点加入Q后，A变为黑色，在下一次循环中被移除Q外

代码实现：

// 5.广度优先遍历
Graph.prototype.bfs = function (initV, handler) {
  var colors = this._initColors();
  var queue = new Queue();

  // 将定点放入队列
  queue.enqueue(initV);

  while (!queue.isEmpty()) {
    var qVal = queue.dequeue(); // 拿到队头的顶点
    var qAdj = this.adList.get(qVal); // 拿到队头对应的边
    // 将队头设置正在探索中 灰色
    colors[qVal] = "gray";

    // 将队头顶点相邻的边 全部拿出来遍历一遍，并加入到队列中
    for (var i = 0; i < qAdj.length; i++) {
      var vertexeValue = qAdj[i]; // 取出相邻顶点
      // 如果这个顶点是白色，说明没有被访问过
      if (colors[vertexeValue] === "white") {
        // 正在访问
        colors[vertexeValue] = "gray";
        // 将相邻顶点入队
        queue.enqueue(vertexeValue);
      }
    }

    // 代表该定点已经探索完毕，设置为黑色
    colors[qVal] = "black";

    // 输出
    handler && handler(qVal);
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

测试代码

graph.bfs(graph.vertexes[0], function (value) {
  console.log(value); // A,B,C,D,E,F,G,H,I,
});
1
2
3

过程详解

下为指定的第一个顶点为A时的遍历过程：

• 如 a 图所示，将在字典edges中取出的与A相邻的且未被访问过的白色顶点B、C、D放入队列que中并变为灰色，随后将A变为黑色并移出队列
• 接着，如图 b 所示，将在字典edges中取出的与B相邻的且未被访问过的白色顶点E、F放入队列que中并变为灰色，随后将B变为黑色并移出队列

• 如 c 图所示，将在字典edges中取出的与C相邻的且未被访问过的白色顶点G（A，D也相邻不过已变为灰色，所以不加入队列）放入队列que中并变为灰色，随后将C变为黑色并移出队列
• 接着，如图 d 所示，将在字典edges中取出的与D相邻的且未被访问过的白色顶点H放入队列que中并变为灰色，随后将D变为黑色并移出队列

如此循环直到队列中元素为0，即所有顶点都变黑并移出队列后才停止，此时图中顶点已被全部遍历

为了更好的理解BFS，这里提供一份简版BFS，核心思路都是一样的

简版BFS

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};

const bfs = (root) => {
  const visited = new Set(); // 用来存储，节点是否访问过
  visited.add(root);
  const q = [root]; //新建队列，根结点入队

  while (q.length) {
    let n = q.shift(); // 队列节点出队，拿到队头
    console.log(n); // 访问节点
    // 访问相邻节点，并入队
    graph[n]?.forEach((item) => {
      if (!visited.has(item)) { // 若没被访问过
        q.push(item); // 入队
        visited.add(item); // 表示已经访问过
      }
    });
  }
};

bfs(2); // 2 0 3 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.6深度优先搜索(DFS)

思路：

• 深度优先搜索算法将会从指定的第一个顶点开始遍历图，沿着一条路径遍历直到该路径的最后一个顶点都被访问过为止
• 接着沿原来路径回退并探索下一条路径，即先深后宽地遍历图中的各个顶点

实现思路：

• 可以使用栈结构来实现深度优先搜索算法
• 深度优先搜索算法的遍历顺序与二叉搜索树中的先序遍历较为相似，同样可以使用递归来实现（递归的本质就是函数栈的调用）

基于递归实现深度优先搜索算法：定义dfs方法用于调用递归方法dfsVisit，定义dfsVisit方法用于递归访问图中的各个顶点。

这里实现dfs时，实现一个辅助函数dfsVisit，方便递归实现DFS。

在dfs方法中：

• 首先，调用initializeColor方法将所有顶点初始化为白色
• 然后，调用dfsVisit方法遍历图的顶点

在dfsVisit方法中：

• 首先，将传入的指定节点v标注为灰色
• 接着，处理顶点V
• 然后，访问V的相邻顶点
• 最后，将顶点v标注为黑色

代码实现：

// 6.深度优先遍历
Graph.prototype.dfs = function (initValue, handler) {
  var colors = this._initColors(); // 初始化顶点颜色
  this.dfsVisit(initValue, colors, handler); // 遍历
};

Graph.prototype.dfsVisit = function (v, colors, handler) {
  colors[v] = "gray"; // 访问中

  handler && handler(v); // 访问该顶点

  var vList = this.adList.get(v); // 获取相邻顶点
  for (var i = 0; i < vList.length; i++) {
    if (colors[vList[i]] === "white") {
      this.dfsVisit(vList[i], colors, handler); // 递归访问
    }
  }

  colors[v] = "black"; // 访问结束
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试代码

graph.dfs(graph.vertexes[0], function (value) {
  console.log(value); // A,B,E,I,F,C,D,G,H
});
1
2
3

过程详解

这里主要解释一下代码中的第3步操作：访问指定顶点的相邻顶点。

• 以指定顶点A为例，先从储存顶点及其对应相邻顶点的字典对象edges中取出由顶点A的相邻顶点组成的数组

• 第一步：A顶点变为灰色，随后进入第一个for循环，遍历A白色的相邻顶点：B、C、D；在该for循环的第1次循环中（执行B），B顶点满足：colors == “white”，触发递归，重新调用该方法
• 第二步：B顶点变为灰色，随后进入第二个for循环，遍历B白色的相邻顶点：E、F；在该for循环的第1次循环中（执行E），E顶点满足：colors == “white”，触发递归，重新调用该方法
• 第三步：E顶点变为灰色，随后进入第三个for循环，遍历E白色的相邻顶点：I；在该for循环的第1次循环中（执行I），I顶点满足：colors == “white”，触发递归，重新调用该方法
• 第四步：I顶点变为灰色，随后进入第四个for循环，由于顶点I的相邻顶点E不满足：colors == “white”，停止递归调用。过程如下图所示：

• 第五步：递归结束后一路向上返回，首先回到第三个for循环中继续执行其中的第2、3…次循环，每次循环的执行过程与上面的同理，直到递归再次结束后，再返回到第二个for循环中继续执行其中的第2、3…次循环…以此类推直到将图的所有顶点访问完为止。

下图为遍历图中各顶点的完整过程：

• 发现表示访问了该顶点，状态变为灰色；
• 探索表示既访问了该顶点，也访问了该顶点的全部相邻顶点，状态变为黑色；
• 由于在顶点变为灰色后就调用了处理函数handler，所以handler方法的输出顺序为发现顶点的顺序即：A、B、E、I、F、C、D、G、H 。

为了更好的理解DFS，这里也提供一份简版DFS

简版DFS

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};

let set = new Set();
const dfs = (n) => {
  console.log(n);
  set.add(n);
  graph[n]?.forEach((item) => {
    if (!set.has(item)) {
      dfs(item);
    }
  });
};

dfs(2); // 2 0 1 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.7 完整代码

const Dirtioany = require("./dict");
const Queue = require("../03-队列结构/01-queue");

function Graph() {
  this.vertexes = []; // 存放顶点
  this.adList = new Dirtioany(); // 使用字典结构存放 边 信息

  // 1.添加顶点
  Graph.prototype.addVertex = function (val) {
    this.vertexes.push(val); // 添加顶点
    this.adList.set(val, []); // 初始化顶点对应的边
  };

  // 2.添加边
  Graph.prototype.addEdge = function (val1, val2) {
    // 因为边是相互存在的，所以需要存储关联两个顶点的信息
    // 这里实现的是无向图，所以不考虑方向的问题
    this.adList.get(val1).push(val2);
    this.adList.get(val2).push(val1);
  };

  // 3.toString方法
  Graph.prototype.toString = function () {
    var resString = "";
    for (var i = 0; i < this.vertexes.length; i++) {
      resString += this.vertexes[i] + "->";
      var adList = this.adList.get(this.vertexes[i]);
      for (var j = 0; j < adList.length; j++) {
        resString += adList[j] + " ";
      }
      resString += "\n";
    }
    return resString;
  };

  /**
   * 4.初始化顶点颜色
   * 白色表示该顶点还没有被访问.
   * 灰色表示该顶点被访问过, 但并未被探索过.
   * 黑色表示该顶点被访问过且被完全探索过.
   */
  Graph.prototype._initColors = function () {
    var colors = [];
    for (var i = 0; i < this.vertexes.length; i++) {
      colors[this.vertexes[i]] = "white";
    }
    return colors;
  };

  // 5.广度优先遍历
  Graph.prototype.bfs = function (initV, handler) {
    var colors = this._initColors();
    var queue = new Queue();

    // 将定点放入队列
    queue.enqueue(initV);

    while (!queue.isEmpty()) {
      var qVal = queue.dequeue(); // 拿到队头的顶点
      var qAdj = this.adList.get(qVal); // 拿到队头对应的边
      // 将队头设置正在探索中 灰色
      colors[qVal] = "gray";

      // 将队头顶点相邻的边 全部拿出来遍历一遍，并加入到队列中
      for (var i = 0; i < qAdj.length; i++) {
        var vertexeValue = qAdj[i]; // 取出相邻顶点
        // 如果这个顶点是白色，说明没有被访问过
        if (colors[vertexeValue] === "white") {
          // 正在访问
          colors[vertexeValue] = "gray";
          // 将相邻顶点入队
          queue.enqueue(vertexeValue);
        }
      }

      // 代表该定点已经探索完毕，设置为黑色
      colors[qVal] = "black";

      // 输出
      handler && handler(qVal);
    }
  };

  // 6.深度优先遍历
  Graph.prototype.dfs = function (initValue, handler) {
    var colors = this._initColors(); // 初始化顶点颜色
    this.dfsVisit(initValue, colors, handler); // 遍历
  };

  Graph.prototype.dfsVisit = function (v, colors, handler) {
    colors[v] = "gray"; // 访问中

    handler && handler(v); // 访问该顶点

    var vList = this.adList.get(v); // 获取相邻顶点
    for (var i = 0; i < vList.length; i++) {
      if (colors[vList[i]] === "white") {
        this.dfsVisit(vList[i], colors, handler); // 递归访问
      }
    }

    colors[v] = "black"; // 访问结束
  };
}

// 测试代码
let graph = new Graph();

// 添加顶点
let myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (let i = 0; i < myVertexes.length; i++) {
  graph.addVertex(myVertexes[i]);
}

// 添加边
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());
// 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

graph.bfs(graph.vertexes[0], function (value) {
  console.log(value); // A,B,C,D,E,F,G,H,I,
});

graph.dfs(graph.vertexes[0], function (value) {
  console.log(value); // A,B,E,I,F,C,D,G,H
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

往期精彩文章

• leetcode-js刷题记录&数据结构
• docker下YApi部署教程-支持swagger数据导入
• 带你深入理解什么叫js闭包
• 使用Object.defineProperty进行数据劫持,实现响应式原理-剖析vue2.0
• 前端性能优化之rel=“prefetch“预/懒加载功能
• 前端唤起相机的方法H5+JS