原文来自我的个人博客
1. 认识图结构
- 图是网络结构的抽象模型，是一组由边连接的节点。
- 图可以表示任何二元关系。
js中没有图，但是可以用Object构建图- 图的表示法有：邻接矩阵、邻接表、关联矩阵......
2. 图结构常见术语
1. 顶点
- 表示图中的某一节点
- 比如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人
2. 边
- 表示顶点到顶点的连线
- 比如地铁站中两个站点之间的直接连线，就是一个边
3. 相邻顶点
- 表示由一条边连接在一起的顶点
4. 度
- 一个顶点的度表示相邻顶点的数量
- 比如上图中
0顶点和其他两个顶点相连，所以0顶点的度是2
5. 路径
- 路径是顶点之间的一个连续序列，比如上图中0 1 5 9就是一条路径
- 简单路径： 要求不包含重复的顶点，比如 0 1 5 9
- 回路： 第一个顶点和最后一个顶点相同的路径，比如 0 1 5 6 3 0
5. 无向图
- 表示所有边都没有方向
- 比如上图中 0 - 1 之间有边且没有方向，说明这条边可以保证 0 -> 1，也可以保证 1 -> 0
6. 有向图
- 表示图中的边是有方向的
7. 无权图
- 表示边没有携带权重
8. 带权图
- 带权图表示边有一定的权重
- 这里的权重可以是任意你希望表示的数据
3. 邻接矩阵和邻接表
我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线（边），这两个都是非常重要的图信息，因此都需要在程序中体现出来
- 顶点的表示：顶点可以使用数组来存储
- 边的表示：边的表示会稍微麻烦一些，下面我们具体讨论一下边常见的表示方式
3.1 邻接矩阵
邻接矩阵是一种常见的表示图的方式
- 邻接矩阵让每个节点和一个整数项关联，该整数作为数组的下标值
- 我们用一个二维数组来表示顶点之间的连接
- 比如下图，二维数组
[0][2]表示A -> C
图片解析：
- 在二维数组中，
0表示没有连线，1表示有连线 - 通过二维数组，我们可以很快的找到一个顶点和哪些顶点有连线。（比如
A顶点，只需要遍历第一行即可） - 另外
A - A,B - B（也就是顶点到自己的连线），通常使用0表示
邻接矩阵的问题：
邻接矩阵还有一个比较严重的问题，就是如果图是一个稀疏图，那么矩阵中将存在大量的 0 ，这意味着我们浪费了计算机存储空间来表示不存在的边
3.2 邻接表
邻接表是另一种常用的表示图的方式
- 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成
- 这个列表有很多种方式来存储： 数组/链表/字典（哈希表） 都可以
邻接表的问题
邻接表计算 “出度” 是比较简单的，但是如果计算有向图的 “入度”，就是一件非常麻烦的事情，它必须构造一个 “逆邻接表”，才能有效的计算 “入度”
出度：指向别人的数量入度：指向自己的数量
4. 图结构的封装
4.1 图的基础框架 v1 版
class Graph<T> {
verteces: T[] = [];
adjList: Map<T, T[]> = new Map();
constructor() {}
}解析：
verteces：用于存储所有的顶点，adjList：adj是adjoin的缩写，邻接的意思。adjList用于存储所有的边，我们这里采用邻接表的形式。
4.2 添加基础方法 V2 版本
addVertex：添加顶点的方法
/* 添加顶点的方法 */
addVertex(vertex: T) {
// 将顶点添加数组中保存
this.verteces.push(vertex);
// 创建一个邻接表中的数组
this.adjList.set(vertex, []);
}addEdge：添加边的方法
/* 添加边的方法 */
addEdge(v1: T, v2: T) {
this.adjList.get(v1)?.push(v2);
this.adjList.get(v2)?.push(v1);
}traverse：一个打印的方法，方便我们看结构
traverse() {
this.verteces.forEach((vertex) => {
const edges = this.adjList.get(vertex);
console.log(`${vertex} -> ${edges?.join(" ")}`);
});
}测试:
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addEdge("A", "B");
graph.addEdge("A", "D");
graph.addEdge("B", "B");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("C", "D");
graph.addEdge("F", "A");
graph.traverse();打印结果：
A -> B D F
B -> A B B
C -> E D
D -> A E C
E -> C D
F -> A4.3 深度优先遍历 v3 版
深度优先搜索（Depth-First Search，简称DFS）
思想：基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
dfs() {
// 1. 判断是否有顶点
if (this.verteces.length === 0) return;
// 2. 创建队列结构访问每一个顶点
const stack: T[] = [];
stack.push(this.verteces[0]);
// 3. 创建 Set 结构，记录某一个顶点是否被访问过
const visited = new Set<T>();
visited.add(this.verteces[0]);
// 4. 从第一个顶点开始访问
while (stack.length) {
const vertex = stack.pop()!;
console.log(vertex);
const neighbors = this.adjList.get(vertex);
if (!neighbors) continue;
for (let i = neighbors.length - 1; i >= 0; i--) {
const nei = neighbors[i];
if (!visited.has(nei)) {
visited.add(nei);
stack.push(nei);
}
}
}
}4.4 广度优先遍历 v4 版
广度优先搜索（Breadth-First Search，简称BFS）
思想：基于队列，入队列的顶点先被探索
bsf() {
// 1. 判断是否有顶点
if (this.verteces.length === 0) return;
// 2. 创建队列结构访问每一个顶点
const queue: T[] = [];
queue.push(this.verteces[0]);
// 3. 创建 Set 结构，记录某一个顶点是否被访问过
const visited = new Set<T>();
visited.add(this.verteces[0]);
// 4. 遍历队列中每一个顶点
while (queue.length) {
// 访问队列中第一个顶点
const vertex = queue.shift()!;
console.log(vertex);
// 相邻的顶点
const neighbors = this.adjList.get(vertex);
if (!neighbors) continue;
for (const nei of neighbors) {
if (!visited.has(nei)) {
visited.add(nei);
queue.push(nei);
}
}
}
}
