前言
图是一个非线性数据结构，本文将讲解图的基本运用，将图巧妙运用，并用TypeScript将其实现，欢迎各位感兴趣的开发者阅读本文。
写在前面
本文着重讲解图的实现思路，对图的基础概念不了解的开发者，请移步我的另一篇文章：图的认识。
实现思路
图是网络结构的抽象模型，图是由一组边连接的顶点。任何二元关系都可以用图来表示，例如：社交网络、道路、航班以及通信。
基本概念
一个图G = (V, E)由以下元素组成。
- V：一组顶点
- E：一组边，连接V中的顶点
下图描述了一个图。
通过上图我们来讲解下图的一些术语。
- 相邻顶点，即由一条边连接在一起的顶点。如上图所示，A和B是相邻的，A和D是相邻的，A和C是相邻的，A和E不是相邻的。
- 度，即一个顶点与其相邻顶点的数量，如上图所示，A和其他三个顶点相连接，因此A的度为3；E和其他两个顶点相连，因此E的度为2。
- 路径，即顶点v1，v2，…，vn的一个连续序列，其中v1和vn+1是相邻的。如上图所示，包含路径A B E I和A C D G
- 简单路径，即不包含重复的顶点。如上图所示，ADG就是一条简单路径，除去最后一个顶点，因为它与A是同一个顶点。
- 环，它也是一个简单路径，如上图所示，A D C A，最后一个顶点重新回到A。
有向图与无向图
图可以是无向（没有方向）的或是有向（有向图）的。上面我们画的是无向图，下图描述了一个有向图。
- 强连通，即图中每两个顶点间在双向上都存在路径。如上图所示，C和D就是强连通的，而A和B不是强联通的。
- 加权，如果给图上每条边都标上权重，那么这个图就是一个加权图，否则就是不加权的，加权图如下所示。
图的表示
图可以用多种数据结构来表示，不存在绝对正确的方式。图的正确表示法取决于待解决的问题和图的类型。
邻接矩阵
图最常见的实现是邻接矩阵，每个节点都和一个种整数相关联，该整数将作为数组的索引。我们可以用一个二维数组来表示顶点之间的的连接。如果索引为i的节点和索引为j的节点相邻，则 array[i][j] = 1，否则 array[i][j] = 0，如下图所示
不是强联通的图（稀疏图）如果用邻接矩阵来表示，则矩阵中将会有很多0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。例如，找给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。邻接矩阵表示法不够好的一个理由是：图中顶点的数量可能会改变，而二维数组不太灵活。
临接表
我们可以使用临接表这种动态数据结构来表示图，临接表由图中每个顶点的相邻顶点列表所组成。我们可以使用数组、链表、散列表或字典来表示相邻顶点列表，如下图所示描述了临接表这种数据结构。
临接表对大多数问题来说是比较好的选择，以上两种表示法都很有用，他们有着不同的性质（例如，要找出v和w是否相邻，使用邻接矩阵会比较快）。
关联矩阵
我们还可以使用关联矩阵来表示图。在关联矩阵中，矩阵的行表示顶点，列表示边。
如下图所示，使用二维数组来表示两者之间的连通性，如果顶点v是边e的入射点，则 array[v][e] = 1；否则， array[v][e] = 0。
关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存。
使用临接表实现图
创建图所需的基础变量
- 创建Grap类，构造器接收一个参数用于判断图是否有向，默认情况图是无向的。
- 类内部，声明一个数组用来存储图中所有顶点的名字（vertices），声明一个字典来存储临接表（adjList）。
- 字典会使用顶点的名字作为键，邻接顶点列表作为值。
实现图所需的两种方法
接下来我们需要实现两个方法：一个用来向图中添加一个新的顶点，另一个用来添加顶点之间的边。
向图中添加顶点（addVertex）
- addVertex方法接收一个参数：要添加的顶点(v)
- 首先，判断要添加的顶点是否在图（顶点列表）中
- 如果不存在，将该顶点添加到顶点列表中
- 在临接表中设置顶点v作为键，对应的字典值为一个空数组
向图中添加边（addEdge）
- addEdge方法接收两个参数: 要进行连接的两个顶点（v，w）
- 添加顶点前，验证要添加的两个顶点是否在图中，如果不存在则需要先调用addVertex方法将其添加到图中
- 获取顶点v的临接表，将w添加进v的临接表中，这样我们就得到了一条来自顶点v到顶点w的边
- 如果是无向图则需要添加一条自w到v的边
实现图的获取方法
上面我们实现了向图中插入值，我们还需要获取图中的值以及将图转换成比较友好的字符串。
获取图的顶点列表（getVertices）
-
直接返回vertices即可
-
获取图的临接表（getAdjList）
-
直接返回adjList即可
将图转换为字符串（toString）
- 首先，遍历图的所有顶点，将顶点的名字加入字符串中
- 然后，获取当前遍历到顶点的临接表
- 然后，遍历获取到的临接表，将临街表中的每个顶点加入到字符串中
- 最后，临接表遍历完成后向字符串中添加一个换行符
实现代码
前面我们分析了图的实现思路，接下来我们将上述思路转换为代码。
- 新建Graph.ts文件，创建类以及实现图所需要的变量。
export default class Graph {
// 存储图的顶点
private vertices: (number | string)[] = [];
// 存储临接表
private adjList: Dictionary<string | number, (string | number)[]> = new Dictionary();
constructor(private isDirected: boolean = false) {}
}
- 实现添加顶点和添加边的方法
// 添加顶点
addVertex(v: string | number): void {
// 顶点不存在于图中
if (!this.vertices.includes(v)) {
// 将该顶点添加到顶点列表中
this.vertices.push(v);
// 在临接表中设置顶点v作为键，对应的字典值为一个空数组
this.adjList.set(v, []);
}
}
// 添加线，连接顶点
addEdge(v: string | number, w: string | number): void {
// 添加顶点之前需要验证顶点v和w是否在图中，不存在就追加
if (!this.adjList.get(v)) {
this.addVertex(v);
}
if (!this.adjList.get(w)) {
this.addVertex(w);
}
// 将w加入到v的临接表中，我们就得到了一条来自顶点v到顶点w的边
this.adjList.get(v)?.push(w);
if (!this.isDirected) {
// 如果是无向图则需要添加一条自w到v的边
this.adjList.get(w)?.push(v);
}
}
- 实现图的获取方法
// 获取顶点列表
getVertices(): (string | number)[] {
return this.vertices;
}
// 获取临接表
getAdjList(): Dictionary<string | number, (string | number)[]> {
return this.adjList;
}
// 将图转为字符串
toString(): string {
let s = "";
for (let i = 0; i < this.vertices.length; i++) {
s += `${this.vertices[i]} -> `;
const neighbors = <Array<string | number>>this.adjList.get(this.vertices[i]);
for (let j = 0; j < neighbors.length; j++) {
s += `${neighbors[j]} `;
}
s += "\n";
}
return s;
}
完整代码请移步：Graph.ts
编写测试代码
接下来我们通过一个例子来测试下我们上述图的实现是否正确，我们还是以基本概念中所用的图为例。
为了方便起见，我们创建了一个数组，这个数组包含了图中的所有顶点，我们遍历数组，将数组中的每个顶点添加进我们的图中。
const graph = new Graph();
const vertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (let i = 0; i < vertices.length; i++) {
graph.addVertex(vertices[i]);
}
然后，调用addEdge方法添加我们想要的边。
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");
最后，调用toString方法将图转换为字符串，将其打印到控制台。
console.log("图的关系对应如下");
console.log(graph.toString());
运行结果如下，我们发现图的对应关系与基本概念中的示例图一样。
完整代码请移步：GraphTest.js
图的遍历
与树结构类似，我们可以访问图的所有节点，有两种算法可以实现对图进行遍历：广度优先搜索和深度优先搜索。
图遍历可以用来寻找特定的顶点或寻找连个顶点之间的路径，检查图是否联通，检查图是否含有环。
由于本篇文章主要讲解的是图的实现，有关图的遍历，请移步我的另外两篇文章：广度优先搜索的理解与实现 & 深度优先搜索的理解与实现
写在最后
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于掘金，未经许可禁止转载💌
评论区