跳至主要內容

【数据结构】超级简单的图算法,图文并茂,学不会你来打我

萌萌哒草头将军大约 7 分钟前端JavaScript数据结构和算法

未经允许禁止转载, 微信公众号:「萌萌哒草头将军」
超级简单的图算法,图文并茂,学不会,你来打我

认识图

图是由节点集合和边(路径)集合组成的图形

如果图是有方向的,那就称为有序图,否则称为无序图

image.png
image.png

如果每条路径成本或者权重,那么图就是有权图

image.png
无权图可以认为是权重相同的有权图

最小生成树

在描述时,我们通常根据边的权重将图转为最小生成树,因为最小生成树可以包含所有节点信息和最少的边,可以使计算量缩减到最小

例如上图的最小生成树如下

image.png
image.png

有两种方法将图转为最小生成树

kruskal(克鲁斯卡尔)算法

思路:根据权重,将边排序,每次从边中选择权重最小的边,如果使图连通(形成环)了,那就放弃这条边

上图中加入边的顺序以此为:(2->5, 1)、(5->6, 2)、(6->3, 3)、(4->1, 3)、(5->4, 5)

prim(普里姆)

思路:从一个节点出发,在所有连接的可选值只保留代价最小的边,例如上图,从节点1开始经过该算法后最小生成树是这样的

节点1:可选边为(1->2, 6)、(1->4, 3),只能选:(1->4, 3)

节点1、4:可选边为(1->2, 6)、(4->5, 5)只能选:(4->5, 5)

节点1、4、5:可选边为(5->2, 1)、(1->2, 6)、(5->6, 2)只能选(5->2, 1)

节点1、4、5、2:可选边为(5->6, 2)、(1->2, 6)、(2->3, 4)只能选(5->6, 2)

节点1、4、5、2、6:可选边为(1->2, 6)、(2->3, 4)、(6->3, 3)只能选(6->3, 3)

好了现在可以按照树的形式表示图了

描述节点

描述每个节点需要唯一标识,这样方便后续对每个节点的操作,所以我们先定义下面的类来描述节点

class Vertex {
    constructor (uuid) {
        this.uuid = uuid
        // ...你可以在这里添加others props
    }
}

定义边

描述边成熟的做法是使用邻接表或者邻接数组

邻接表是一个描述每个节点相关边的对象,它以每个节点的ID为key,与之相连的边数组集合作为value,例如上图中的每个节点的邻接表如下所示:

image.png
image.png

邻接数组是用二维数组的方式描述

你可能习惯性的想在节点上标记每个节点相关边的信息,这样的是可以的,
但是对于后续的查询和变更,会消耗很大的性能,

同样,你如果想单独定义一个边的类描述边信息,也是一样的损耗性能。

实现图

现在就让我们开始实现基本的属性和功能吧

属性

首先是定义Graph类,需要vertexs数组存放所有的节点,需要edges对象存放邻接表

class Graph {
    constructor(vertexNumber) {
        this.vertexs = [] // 存放节点
        this.edges = {} // 存放邻接表
        this.marked = {} // 记录标记
    }
}

addNodes方法

增加节点,除了初始化节点之外,需要初始化新节点的邻接表和标记状态

class Graph {
    // 增加节点
    addNodes (uuid) {
        this.vertexs.push(new Vertex(uuid))
        this.edges[uuid] = []
        this.marked[uuid] = false
    }
}

addEdges方法

增加边的本质就是增加邻接表信息

class Graph {
    // 增加边
    addEdges (source, target) {
        // 分别给对方的邻接表添加边
        this.edges[source].push(target)
        this.edges[target].push(source)
    }
}

showGraoh方法

展示图时,我们是通过展示邻接表来展示图的,所以邻接表就是图的精髓所在,后面的方法主要是操作邻接表

class Graph {
    // 展示图
    showGraoh () {
        this.vertexs.forEach(vertex => console.log(
            vertex.uuid,
            '->',
            this.edges[vertex.uuid].toString()
        ))
    }
}

添加测试数据

const graph = new Graph()

[1, 2, 3, 4, 5, 6].forEach((n) => graph.addNodes(n))

graph.addEdges(1, 2)
graph.addEdges(1, 3)
graph.addEdges(1, 4)
graph.addEdges(3, 4)
graph.addEdges(2, 5)
graph.addEdges(5, 6)

graph.showGraoh()

// 1 '->' '2,3,4'
// 2 '->' '1,5'
// 3 '->' '1,4'
// 4 '->' '1,3'
// 5 '->' '2,6'
// 6 '->' '5'

此时的树为下图所示

image.png
image.png

深度优先和广度优先

遍历图中每个节点,根据不同的策略,节点的遍历顺序也不相同,最常见的是深度优先(dfs)广度优先(bfs)

深度优先

深度优先(dfs)是指每次优先遍历子节点,没有子节点时再回到兄弟节点,以此类推

image.png
image.png

这里为了避免标记混乱,使用了单独的变量visited标记深度优先,它和marked一样

// 深度优先搜索
dfs (uuid) {
    this.visited[uuid] = true // 深度优先单独标记,以免影响广度优先算法和最短路径算法
    console.log('dfs', uuid)
    // 循环邻接表中子节点
    this.edges[uuid].forEach(edge => {
        // 如果没有标记,就继续下钻
        if (!this.visited[edge]) this.dfs(edge) // 递归
    })
}

广度优先

广度优先(bfs)是指每次兄弟节点优先遍历,没有兄弟节点时,在遍历子节点的兄弟节点,以此类推

image.png
image.png

它是通过队列实现的:

  1. 先初始化一个空队列
  2. 将起始节点放入队列
  3. 弹出队列第一个节点,并且访问它子节点
  4. 如果没有被标记,那就标记它,并放入队列
  5. 开始循环第三步,直到队列为空
 // 广度优先搜索
bfs (uuid) {
    // 1.先初始化一个空队列
    const queue = []
    this.marked[uuid] = true
    // 2.将起始节点放入队列
    queue.push(uuid)
    console.log('bfs', uuid)
    while (queue.length) {
        // 3.弹出队列第一个节点,并且访问它子节点
        const uuid_ = queue.shift()
        this.edges[uuid_].forEach(edge => {
            // 4.如果没有被标记,那就标记它,并放入队列
            if (!this.marked[edge]) {
                this.marked[edge] = true
                console.log('bfs', edge)
                queue.push(edge)
            }
        })
    }
}

测试

graph.dfs(1)
console.log(`<=========>`)
graph.bfs(1)

// dfs 1
// dfs 2
// dfs 5
// dfs 6
// dfs 3
// dfs 4
// <=========>
// bfs 1
// bfs 2
// bfs 3
// bfs 4
// bfs 5
// bfs 6

最短路径

图经常被用到的地方其实查询从某个节点到另一个节点的最短距离,比如,从你的住处到公司,在四通八达的北京,道路可能不止一条,但是总有一条是最短的

求最短路径的算法有多种,今天介绍bfs最短距离,顾名思义,就是借助广度优先算法实现的

在广度优先算法中,我们遍历节点的每个子节点时,总会遇到一个没有被标记的节点,此时,我们需要记录这个没有被标记的节点的父节点,并将这些信息记录在edgeTo属性中。

完成广度优先算法后,我们就可以知道每个子节点对应的父节点了,接着我们只需要从目标节点,往上逆推,找到它的父节点,然后在往上推,知道源节点或者根节点,下面是以跟节点为例的实现

// 记得添加这个属性
this.edgeTo = {}

// 对广度优先搜索改造
bfs (uuid) {
    const queue = []
    this.marked[uuid] = true
    queue.push(uuid)
    console.log('bfs', uuid)
    while (queue.length) {
        const uuid_ = queue.shift()
        this.edges[uuid_].forEach(edge => {

            if (!this.marked[edge]) {
                this.edgeTo[edge] = uuid_ // 记录每个节点的父节点
                this.marked[edge] = true
                console.log('bfs', edge)
                queue.push(edge)
            }
        })
    }
    console.log(this.edgeTo) // 打印每个节点对应父节点的信息
}
// 找出目标节点到根节点的路径
pathTo (uuid) {
    const source = this.vertexs[0].uuid
    const path = []
    if (this.marked[uuid]) {
        for(let i = uuid; i !== source; i = this.edgeTo[i]) {
            path.push(i)
        }
    }
    path.push(source)
    return path
}
// 格式化展示
printMinPathTo (uuid) {
    const path = this.pathTo(uuid).join('->')
    console.log(path)
}

测试

graph.printMinPathTo(6)

// 依次打印
// {
//   2: 1,
//   3: 1,
//   4: 1,
//   5: 2,
//   6: 5
// }
// 6->5->2->1

好了,分享就到这了,欢迎指正出现的问题