侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 135 篇文章
  • 累计创建 25 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

图的实现

神奇的程序员
2020-07-24 / 0 评论 / 0 点赞 / 16 阅读 / 4,380 字

前言

图是一个非线性数据结构,本文将讲解图的基本运用,将图巧妙运用,并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文。

写在前面

本文着重讲解图的实现思路,对图的基础概念不了解的开发者,请移步我的另一篇文章:图的认识

实现思路

图是网络结构的抽象模型,图是由一组边连接的顶点。任何二元关系都可以用图来表示,例如:社交网络、道路、航班以及通信。

基本概念

一个图G = (V, E)由以下元素组成。

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

下图描述了一个图。
image.png

通过上图我们来讲解下图的一些术语。

  • 相邻顶点,即由一条边连接在一起的顶点。如上图所示,A和B是相邻的,A和D是相邻的,A和C是相邻的,A和E不是相邻的。
  • ,即一个顶点与其相邻顶点的数量,如上图所示,A和其他三个顶点相连接,因此A的度为3;E和其他两个顶点相连,因此E的度为2。
  • 路径,即顶点v1,v2,…,vn的一个连续序列,其中v1和vn+1是相邻的。如上图所示,包含路径A B E IA C D G
  • 简单路径,即不包含重复的顶点。如上图所示,ADG就是一条简单路径,除去最后一个顶点,因为它与A是同一个顶点。
  • ,它也是一个简单路径,如上图所示,A D C A,最后一个顶点重新回到A。

有向图与无向图

图可以是无向(没有方向)的或是有向(有向图)的。上面我们画的是无向图,下图描述了一个有向图。
image.png

  • 强连通,即图中每两个顶点间在双向上都存在路径。如上图所示,C和D就是强连通的,而A和B不是强联通的。
  • 加权,如果给图上每条边都标上权重,那么这个图就是一个加权图,否则就是不加权的,加权图如下所示。

image.png

图的表示

图可以用多种数据结构来表示,不存在绝对正确的方式。图的正确表示法取决于待解决的问题和图的类型。

邻接矩阵

图最常见的实现是邻接矩阵,每个节点都和一个种整数相关联,该整数将作为数组的索引。我们可以用一个二维数组来表示顶点之间的的连接。如果索引为i的节点和索引为j的节点相邻,则 array[i][j] = 1,否则 array[i][j] = 0,如下图所示
image.png

不是强联通的图(稀疏图)如果用邻接矩阵来表示,则矩阵中将会有很多0,这意味着我们浪费了计算机存储空间来表示根本不存在的边。例如,找给定顶点的相邻顶点,即使该顶点只有一个相邻顶点,我们也不得不迭代一整行。邻接矩阵表示法不够好的一个理由是:图中顶点的数量可能会改变,而二维数组不太灵活。

临接表

我们可以使用临接表这种动态数据结构来表示图,临接表由图中每个顶点的相邻顶点列表所组成。我们可以使用数组、链表、散列表或字典来表示相邻顶点列表,如下图所示描述了临接表这种数据结构。
image.png

临接表对大多数问题来说是比较好的选择,以上两种表示法都很有用,他们有着不同的性质(例如,要找出v和w是否相邻,使用邻接矩阵会比较快)。

关联矩阵

我们还可以使用关联矩阵来表示图。在关联矩阵中,矩阵的行表示顶点,列表示边。


如下图所示,使用二维数组来表示两者之间的连通性,如果顶点v是边e的入射点,则 array[v][e] = 1;否则, array[v][e] = 0
image.png

关联矩阵通常用于边的数量比顶点多的情况,以节省空间和内存。

使用临接表实现图

我们选用临接表来表示图,接下来我们来分析下如何来实现图。

创建图所需的基础变量

  • 创建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());

运行结果如下,我们发现图的对应关系与基本概念中的示例图一样。
image.png
完整代码请移步:GraphTest.js

图的遍历

与树结构类似,我们可以访问图的所有节点,有两种算法可以实现对图进行遍历:广度优先搜索和深度优先搜索。


图遍历可以用来寻找特定的顶点或寻找连个顶点之间的路径,检查图是否联通,检查图是否含有环。


由于本篇文章主要讲解的是图的实现,有关图的遍历,请移步我的另外两篇文章:广度优先搜索的理解与实现 & 深度优先搜索的理解与实现

写在最后

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于掘金,未经许可禁止转载💌
0

评论区