专栏首页多云转晴数据结构——图

数据结构——图

图是一组由边连接的顶点。任何二元关系都可以用图来表示。社交网络、道路等都可以用图来表示。

例如下面的好友关系图:

关系图

图与树的结构相似,他们都是非线性数据结构,而树是图的特殊情况。

图的表示

一个图可以用公式 G = (V, E) 来表示。其中:

  • V 表示一组顶点;
  • E 表示一组边,用以连接 V 中的顶点;

一个顶点的度是其相邻顶点的数量。如上图中的 A 顶点,他与 E 和 B 顶点相邻,度是 2。C 值与 B 相邻,度是 1。

图可分为 有向图无向图

有向图表示有方向性,如果图中每两个顶点间在双向上都存在路径,则该图是强连通的。

图的边还可以加权,这样的图称为加权图。

有向图与加权图

邻接表

图可以用邻接表表示。

邻接表

图的简单实现

首先需要先定义一个数组,用来存储图的顶点;还需要一个字典,用来存储该顶点相邻的其他顶点,相邻顶点用集合存储,以免重复,就像邻接表一样。

class Graph<T> {
    protected vertex: T[];        // 顶点
    protected neighbor: Map<T, Set<T>>;  // 相邻顶点
    protected isDirected: boolean;        // 默认是 false,表示是一个无向图

    constructor(isDirected = false){        // 默认是无向图
        this.isDirected = isDirected;
        this.vertex = [];
        this.neighbor = new Map();
    }
}

添加顶点

vertex 中 push 数据:

addVertex(...vertex: T[]): void{        // 可以一次性添加多个顶点
    vertex.forEach(item => {
        // 数组中没有时才添加
        if(!this.vertex.includes(item)){
            this.vertex.push(item);
            // 设置这个顶点邻居
            this.neighbor.set(item, new Set());
        }
    });
}

添加边

有了顶点,还需要添加相邻的其他顶点构成一条条边。代码如下:

addEdge(vertex: T, ...neighbor: T[]): void{
    const n = this.neighbor;
    if(!n.get(vertex)){
        // 顶点数组中没有该顶点,需要先添加
        this.addVertex(vertex);
    }
    neighbor.forEach(item => {
        // neighbor 也是顶点,也需要添加进数组
        if(!n.get(item)){
            this.addVertex(item);
        }
    });
    // 拿到临边
    neighbor.forEach(item => n.get(vertex)?.add(item));
    // 如果是无向图 还需要把 vertex 作为 neighbor 的临边,无向图相当于是强连通
    if(!this.isDirected){
        neighbor.forEach(item => {
            n.get(item)?.add(vertex);
        });
    }
}

这里可以给顶点一次添加多个边。

toString

可以实现一个 toString 方法,它可以打印出图的邻接表形式。

toString(){
    var neighbor = this.neighbor;
    var vertex = this.vertex;
    for(let i = 0;i < vertex.length;i ++){
        const nSet = neighbor.get(vertex[i]) as Set<T>;
        // Array.from 可以把一个迭代器转变成数组
        var str = Array.from(nSet.values()).join(" ");
        console.log(`${vertex[i]} --> ${str}\n`);
    }
}

OK,实例化测试一下:

let g = new Graph<string>();

g.addVertex('A', 'B', 'C', 'D', 'E', 'F');

g.addEdge('A', 'B', 'E');
g.addEdge('B', 'D', 'F');
g.addEdge('D', 'C', 'F');
g.addEdge('E', 'G', 'C');

g.toString();

控制台输出结果:

toString

图的遍历

图的遍历分为 广度优先搜索深度优先搜索

广度优先搜索(BFS)

广度优先搜索的搜索步骤:

  1. 给定一个顶点,作为搜索入口;
  2. 访问顶点的所有临点,然后再访问每个临点的所有临点;

广度优先搜索一次访问图的一层。

bfs

广度优先搜索会将顶点存入队列中,最先入队的顶点先被探索。

这里有一个注意点,无向图相当于强连通,假如 A 的临点有 B,当遍历完 A 后,开始遍历 B,A 顶点已经被探索过了,在探索 B 时就不需要再探索 A 了,需要有一个状态标记一下 A,表示已经探索过了。

要标记已经访问过的顶点,可以使用三种颜色反应顶点的状态:

  • 白色:表示这个顶点还没有被访问;
  • 灰色:表示这个顶点被访问过,但并没有探索过;
  • 黑色:表示这个顶点已经被探索;

这就需要先标记一下顶点状态。改造一下原来的代码:

const Graph = (function(){
    // 定义状态
    enum Color { WHITE, GRAY, BLACK };

    return class Graph<T>{
        constructor(){
            // ....
        }

        // 初始化顶点状态
        protected initColor(){
            // 用字典保存每个顶点的状态
            let color = new Map<T, Color>();
            this.vertex.forEach(item => {
                color.set(item, Color.WHITE);
            });
            return color;
        }
    }

})();

接下来就编写广度优先搜索算法。

bfs(startVertex: T, callback: (node: T) => any){
    const vertex = this.vertex;
    const neighbor = this.neighbor;
    // 数组中没有传入的顶点
    if(!vertex.includes(startVertex))   return;
    let queue:T[] = [startVertex];     // 设置一个队列,用来存放顶点
    let colorMap = this.initColor();    // 拿到初始化的顶点状态
    // 遍历顶点
    while(queue.length){
        let now = queue.shift() as T;    // 出队
        // 变更状态
        colorMap.set(now, Color.GRAY);
        // 获取到顶点的 临点,添加到队列里
        const neighbors = neighbor.get(now) as Set<T>;
        neighbors.forEach(n => {
            // 判断一下临点是不是已经在队列中了
            // 如果状态还是白色,说明是一个新的顶点
            if(colorMap.get(n) === Color.WHITE){
                colorMap.set(n, Color.GRAY);
                queue.push(n);
            }
        });
        // 别忘了设置状态,表示该顶点已探索
        colorMap.set(now, Color.BLACK);
        // 把探索到的顶点传给回调函数做进一步的操作
        if(typeof callback === "function")
            callback(now);
    }
}

这里直接用数组模拟了队列。测试一下:

let g = new G<string>();
g.addVertex('A', 'B', 'C', 'D', 'E', 'F');

g.addEdge('A', 'B', 'E');
g.addEdge('B', 'D', 'F');
g.addEdge('D', 'C', 'F');
g.addEdge('E', 'G', 'C');

let arr: string[] = [];
g.bfs('A', (node) => {
    arr.push(node);
});

console.log(arr);
  • 以顶点 A 作为起点,B E 两顶点会先入队;
  • 然后探索 B 顶点,把 B 顶点的临点入队;
  • 然后探索 E 顶点,把 E 顶点的临点入队;
  • ...

深度优先搜索(DFS)

深度优先搜索会将顶点存入栈中,函数执行环境就是在栈中进行的,就可以使用递归来实现深度优先搜索,深度优先遍历会往下“深层”的探索。

深度优先搜索

代码如下:

dfs(startVertex: T, callback: (node: T) => any){
    const vertex = this.vertex;
    const neighbor = this.neighbor;
    // 递归函数
    var deepVisit = function(node: T, colorMap: Map<T, Color>, cb: (node: T) => any){
        colorMap.set(node, Color.GRAY);
        // 在这里调用回调
        if(typeof cb === "function")
            cb(node);

        const neighbors = neighbor.get(node) as Set<T>;

        neighbors.forEach(n => {
            // 别忘了做判断,只有白色状态时才执行递归
            if(colorMap.get(n) === Color.WHITE){
                deepVisit(n, colorMap, cb);
            }
        });
        colorMap.set(node, Color.BLACK);
        // 如果在这里调用回调,将是最深层的那个顶点
    }

    if(!vertex.includes(startVertex))   return;
    const colorMap = this.initColor();

    for(let i = 0;i < vertex.length;i ++){
        if(colorMap.get(vertex[i]) === Color.WHITE){
            // 只有是白色时才遍历,这说明这个顶点还没有被访问
            deepVisit(vertex[i], colorMap, callback);
        }
    }
}

寻找最短路径

假设你要去旅游,从 A 地前往 B 地,有好几条路可以到达 B 地,为了节省时间,需要找到一条最短的路径。不考虑加权图,假设每条边的加权值一样。

寻找最短路径

从图中很明显能看出 A 到 B 的最短路径是 A --> C --> B。

实现思路

可以使用广度优先搜索策略,广度优先搜索是“层级”性的搜索。以一个顶点为中心,先遍历它的邻居,然后遍历每个邻居的邻居。这是从中心向四周扫描,逐步扩大,遇到 B 点时就停止遍历。

扫描

代码实现与广度优先搜索类似,它会返回路径值,假如一个边的路径值是 1,则题中 A -> B 的距离值就是 2。如果没有找到就返回 -1。

findSortestPath(start: T, end: T): number{
    const n = this.neighbor;
    if(!n.get(start) || !n.get(end))    return -1;
    if(start === end)   return 0;

    const colorMap = this.initColor();
    const queue = [start];
    const prevVertex = new Map<T, T>();     // 这个是用来追踪顶点
    let distance = 1;       // 距离

    while(queue.length){
        const now = queue.shift() as T;
        colorMap.set(now, Color.GRAY);

        const neighbors = n.get(now) as Set<T>;
        // 获取到所有的邻居
        const vertices = Array.from(neighbors.values());

        for(let i = 0;i < vertices.length;i ++){
            let vertex = vertices[i];
            if(colorMap.get(vertex) === Color.WHITE){
                prevVertex.set(vertex, now);        // vertex 是由 now 节点得到
                if(vertex === end){
                    let node = prevVertex.get(vertex);
                    // 追溯上层节点
                    while(node && node !== start){
                        distance += 1;
                        node = prevVertex.get(node);
                    }   // 返回距离
                    return distance;
                }
                colorMap.set(vertex, Color.GRAY);
                queue.push(vertex);
            }
        }
        colorMap.set(now, Color.BLACK);
    }
    return -1;
}

上面代码中 prevVertex 用来追踪顶点,比如一个图的结构是这样的:

要寻找 A 到 C 的最短路径,广度优先搜索的结果是:

A -> B -> D -> E -> F -> C

但是 E 与 C 并不相邻。这时需要一个办法,用来追踪下层顶点它们的上层顶点是哪一个。当遍历到 C 后,对顶点回溯,再找到 A 点。

prevVertex 就是做这个工作的。每次遍历到顶点的邻居时,每个邻居的追溯点都是该顶点。B 的追溯点是 A,D 和 E 的追溯点是 B。

当遍历到 C 点后,开始追溯:

C => F
F => D
D => B
B => A

最后得出:A 到 C 的最短路径是 4。

加权图

简单的实现一个加权图,可以改造一下上面的类。在 addEdge 时,可以传入四个参数:

  • vertex 顶点;
  • neighbor 临点;
  • forwardLevel 正向的加权值 vertex ---> neighbor,默认值是 0;
  • reverseLevel 返乡的加权值 neighbor ---> vertex(当时无向图时会设置),默认值与 forwardLevel 相等;

把实例的 neighbor 数据类型改造一下:

class Graph<T>{
    isDirected: boolean;
    vertex: Array<T>;
    // 里面的 map 是存放临点和加权值
    neighbor: Map<T, Map<T, number>>

    constructor(isDirected = false){
        this.isDirected = isDirected;
        this.vertex = [];
        this.neighbor = new Map();
    }
}

在访问临边时,就需要遍历 neighborkeys 得到数组。下面是加权图的所有代码:

const Graph = (function(){
    enum Color { WHITE, GRAY, BLACK };

    return class Graph<T>{
        isDirected: boolean;
        vertex: Array<T>;
        // 里面的 map 是存放临点和加权值
        neighbor: Map<T, Map<T, number>>

        constructor(isDirected = false){
            this.isDirected = isDirected;
            this.vertex = [];
            this.neighbor = new Map();
        }

        addVertex(...vertex: T[]){
            const v = this.vertex;
            vertex.forEach(item => {
                if(!v.includes(item)){
                    v.push(item);
                    this.neighbor.set(item, new Map());
                }
            });
        }

        /**
         * 添加边和加权值
         * @param vertex 顶点
         * @param neighbor 临点
         * @param forwardLevel 正向的加权值 vertex ---> neighbor
         * @param reverseLevel 返乡的加权值 neighbor ---> vertex(只有 isDirected = true 时才会设置)
         */
        addEdge(vertex: T, neighbor: T, forwardLevel: number = 0, reverseLevel: number = forwardLevel){
            let n = this.neighbor;
            if(!n.get(vertex)){
                this.addVertex(vertex);
            }
            if(!n.get(neighbor)){
                this.addVertex(neighbor);
            }
            // 设置临点和加权值
            n.get(vertex)?.set(neighbor, forwardLevel);

            if(!this.isDirected){
                // 设置反向的加权值
                n.get(neighbor)?.set(vertex, reverseLevel);
            }
        }

        toString(){
            const v = this.vertex;
            const n = this.neighbor;

            v.forEach(vertex => {
                let neighbor = n.get(vertex)?.keys();
                if(neighbor){
                    console.log(`${vertex} => ${Array.from(neighbor).join(" ")}\n`);
                }
            });
        }

        /**
         * 返回顶点与边的加权值,如果返回值是 -1 表示 vertex 没有 neighbor 这个临点
         * @param vertex 顶点
         * @param neighbor 边
         */
        getLevel(vertex: T, neighbor: T): number{
            const n = this.neighbor;
            const neighborMap = n.get(vertex);
            if(!neighborMap)  return -1;
            let level = neighborMap.get(neighbor);
            return typeof level === "number" ? level : -1;
        }

        initColor(){
            let color = new Map<T, Color>();
            this.vertex.forEach(v => {
                color.set(v, Color.WHITE);
            });
            return color;
        }

        bfs(startVertex: T, callback: (node: T) => any){
            const v = this.vertex;
            const n = this.neighbor;
            if(!n.get(startVertex))     throw Error("图中没有这个顶点");
            const colorMap = this.initColor();
            const queue = [startVertex];
            while(queue.length){
                const now = queue.shift() as T;
                colorMap.set(now, Color.GRAY);

                const neighbors = n.get(now) as Map<T, number>
                Array.from(neighbors.keys()).forEach(i => {
                    // 拿到所有的临边
                    if(colorMap.get(i) === Color.WHITE){
                        colorMap.set(i, Color.GRAY);
                        queue.push(i);
                    }
                });
                colorMap.set(now, Color.BLACK);
                if(typeof callback === "function"){
                    callback(now);
                }
            }

            // 最后把没有探索到的孤立顶点(没有临点的)传给回调函数
            colorMap.forEach((value, key) => {
                if(value === Color.WHITE){
                    callback(key);
                }
            });
        }

        dfs(startVertex: T, callback: (node: T) => any){
            const v = this.vertex;
            const n = this.neighbor;
            if(!n.get(startVertex))     throw Error("图中没有这个顶点");

            const colorMap = this.initColor();

            function deepVisit(now: T, colorMap: Map<T, Color>, cb: (node: T) => any){
                colorMap.set(now, Color.GRAY);
                cb(now);
                const neighbors = n.get(now) as Map<T, number>;
                Array.from(neighbors.keys()).forEach(vertex => {
                    if(colorMap.get(vertex) === Color.WHITE){
                        colorMap.set(vertex, Color.GRAY);
                        deepVisit(vertex, colorMap, cb);
                    }
                });
                colorMap.set(now, Color.BLACK);
            };

            for(let i = 0;i < v.length;i ++){
                if(colorMap.get(v[i]) === Color.WHITE){
                    deepVisit(v[i], colorMap, callback);
                }
            }
        }
    }

})();

本文分享自微信公众号 - Neptune丶(Neptune_mh_0110),作者:多云转晴丶

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • React SSR 简介与 Next.js 使用入门

    React SSR 是什么?React SSR 是 React 服务器端渲染 (SSR: server side render) 技术。传统的服务端渲染方式是使...

    多云转晴
  • 实现一个 EventEmitter 类

    在前端开发中,经常会使用到发布订阅模式,发布订阅模式也被称为观察者模式。最常见的发布订阅模式莫过于给 DOM 绑定事件,当点击一个按钮或者鼠标移动到某个元素上就...

    多云转晴
  • JavaScript 实现二叉搜索树

    这里实现二叉树的方式是使用 ES6 中的 class 类以及立即执行函数的方式实现:

    多云转晴
  • 5种正确处理JS的this指向的方式

    咱们经常会发现自己用的 this 指向不正确。下面的教你如何简单地将 this 绑定到所需的值。

    Fundebug
  • 在 JavaScript 中轻松处理 this [每日前端夜话0xD1]

    我喜欢 JavaScript 中能够更改函数执行上下文(也称为 this)的特性。

    疯狂的技术宅
  • JS 中几种轻松处理’this’指向方式

    现在,当调用execute(agent.getFullName)时,一切工作正常,因为getFullName()方法内 this 总是指向正确的值。

    Javanx
  • CNN卷积神经网络的改进(15年最新paper)

    回归正题,今天要跟大家分享的是一些 Convolutional Neural Networks(CNN)的工作。大家都知道,CNN 最早提出时,是以一定的人眼生...

    深度学习思考者
  • zookeeper快速入门——应用(两种分布式锁)

            在《zookeeper快速入门——简介》一文中,我们介绍了zookeeper的机制。但是还是比较抽象,没有直观感受到它在分布式系统中的应用。本文...

    方亮
  • 重磅发布:2018中国企业创新发展报告(附PDF)

    11月30日,汇丰中国携手第一财经,北京大学汇丰商学院重磅了发布《2018中国企业创新发展报告》。报告选取了包括56个大类行业、31个省份的1500家上市企业作...

    钱塘数据
  • [LeetCode] 64. Minimum Path Sum

    【原题】 Given a m x n grid filled with non-negative numbers, find a path from top...

    用户1148830

扫码关注云+社区

领取腾讯云代金券