TypeScript实现图-灵析社区

前言

图是一个非线性数据结构，本文将讲解图的基本运用，将图巧妙运用，并用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;
    }