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

萌萌哒草头将军大约 7 分钟

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

认识图

图是由节点集合和边（路径）集合组成的图形

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

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

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

最小生成树

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

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

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

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，例如上图中的每个节点的邻接表如下所示：

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

你可能习惯性的想在节点上标记每个节点相关边的信息，这样的是可以的，
但是对于后续的查询和变更，会消耗很大的性能，
同样，你如果想单独定义一个边的类描述边信息，也是一样的损耗性能。

实现图

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

属性

首先是定义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'

此时的树为下图所示

深度优先和广度优先

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

深度优先

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

这里为了避免标记混乱，使用了单独的变量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)是指每次兄弟节点优先遍历，没有兄弟节点时，在遍历子节点的兄弟节点，以此类推

它是通过队列实现的：

先初始化一个空队列
将起始节点放入队列
弹出队列第一个节点，并且访问它子节点
如果没有被标记，那就标记它，并放入队列
开始循环第三步，直到队列为空

 // 广度优先搜索
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

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

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

# 认识图

# 最小生成树

# kruskal（克鲁斯卡尔）算法

# prim（普里姆）

# 描述节点

# 定义边

# 实现图

# 属性

# addNodes方法

# addEdges方法

# showGraoh方法

# 深度优先和广度优先

# 深度优先

# 广度优先

# 测试

# 最短路径