代码使用ES6语法实现

不讨论图的基本概念

示例使用的顶点为整数顶点,且规则为 0 1 ... n

一、图的初始化

图的存储形式 : 邻接表

数组模拟的邻接表,不解释什么是邻接表

图类由以下几部分组成:

属性:

  • count : 表示顶点的个数
  • edges : 图的边数
  • adj : 邻接表
  • visited : 存储点是否访问
  • dfsArr : 存储深度优先遍历的结果
  • bfsArr :存储广度优先遍历的结果
  • edgeTo : 存储广度优先遍历中某个顶点到下一个顶点存在边

方法:

省略了几个初始化的操作方法,如 initVisited();等,在最后完整代码示例中存在

  • init()

    • 初始化操作
    • 置空邻接表、初始化点的访问状态为false、置空dfs/bfs遍历的结果数组、置空edgeTo
  • addEdge()

    • 增加顶点
  • showGraph()

    • 打印图
  • initDfs(v)

    • 启动深度优先遍历
    • 启动前需要初始化顶点访问状态表和结果表
  • initBfs(v)

    • 启动广度优先遍历
    • 启动前需要初始化顶点访问状态和结果表
  • dfs(v)

    • 递归进行深度优先遍历(在initDfs()中调用)
  • bfs(start)

    • 进行广度优先遍历(在initBfs()中调用)
  • pathTo(start, v)

    • 查找 start - v 的最短路径
    • 前提是经过了Bfs(start)操作

二、关键的几个方法

1、增加点 addEdge(v, w)

无向无权图增加顶点,在邻接表中两者都需要关联

// 向图中增加顶点
addEdge(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
}

2、深度优先遍历

参数 v 表示从当前点开始遍历

遍历的结果存储在 dfsArr[] 中

深度优先是典型的递归

dfs(v) {
    // 当前访问点设置已访问
    this.visited[v] = true;
    if (this.adj[v] != undefined) {
        console.log("visited " + v);
        // 加入结果数组
        this.dfsArr.push(v);
    }
    for (let w of this.adj[v]) {
        // 邻接点未访问继续dfs
        if (!this.visited[w]) {
            this.dfs(w);
        }
    }
}

3、广度优先遍历

广度优先遍历借助队列实现

BFS的理论不解释

实现思想:

  • 将起点入队
  • 每次从队列中出队一个顶点(第一次肯定是出队起点),然后将出队的顶点的所有未访问过的相邻的顶点入队
  • 将出队的顶点加入遍历结果中
  • 循环执行2-3步,直到队列为空

代码:

// 广度优先遍历
bfs(start) {
    // 开一个队列
    const que = [];
    // 将当前点设置已经访问
    this.visited[start] = true;
    // 将起点加入队列
    que.push(start);
    // 如果队列中一直有值
    while (que.length > 0) {
        // 每次出队一个顶点 
        let v = que.shift();
        // 如果存在点 则表示遍历了该点,则加入结果数组中
        if (v != undefined) {
            console.log("visited " + v);
            this.bfsArr.push(v);
        }
        // 遍历当前访问的顶点的所有相邻顶点
        for (let w of this.adj[v]) {
            // 如果相邻的顶点未访问,则加入队列中,并设置访问状态
            if (!this.visited[w]) {
                this.visited[w] = true;
                // 表示从 w -> v 存在一条路径
                this.edgeTo[w] = v;
                // console.log(w + " -> " + v);
                que.push(w);
            }
        }
    }
}

4、借助 edgeTo[] 列表寻找最短路径

最短路径是基于BFS的,如果单纯的BFS,则不需要使用edgeTo[];

上面BFS操作过程中,反向记录着从下个顶点到当前顶点的边:

  • 比如:0 的相邻点中有 1 2 ,则 edgeTo[] 记录的内容是 edgeTo[1] = 0; edgeTo[2] = 0;
  • edgeTo 数组key是绝对不会被覆盖,因为一个邻接表中,上一个顶点是唯一的,而相邻的下面顶点则有很多,并且只有未访问过的才会加入 edgeTo
  • 并且广度优先遍历时的队列决定了,只要出现了起点,这条路径一定是最短的。

需要注意的是,借助 edgeTo 使用的是逆向查找,因此最后返回的结果是 path.reverse();

// 显示不同的点的路径
pathTo(start, v) {
    let source = start;
    if (!this.hasPathTo(v)) {
        return undefined;
    }
    const path = [];
    for (let i = v; i != source; i = this.edgeTo[i]) {
        path.push(i);
    }
    path.push(source);
    return path.reverse();
}
// 判断某个点是否访问过
hasPathTo(v) {
    return this.visited[v];
}

三、完整的示例

// 图
class Graph {
    constructor(count) {
        this.count = count;          // 记录顶点的个数
        this.edges = 0;                 // 记录边的条数
        this.adj = new Array(count);    // 邻接表
        this.visited = new Array(count);// 访问状态表
        this.dfsArr = [];               // dfs遍历结果存储
        this.bfsArr = [];               // bfs遍历结果存储
        this.edgeTo = [];               // 记录一个顶点到下一个顶点的边
        this.init();                    // 初始化操作
    }
    // 初始化操作
    init() {
        this.initVertex(); // 初始化邻接表
        this.initVisited();// 初始化访问状态
        this.initDfsArr(); // 置空dfs结果
        this.initBfsArr(); // 置空bfs结果
        this.initEdgeTo(); // 置空edgeTo
    }
    // 初始化顶点列表
    initVertex() {
        for (let i = 0; i < this.count; i++) {
            this.adj[i] = new Array();
        }
    }
    // 初始化未访问数组
    initVisited() {
        for (let i = 0; i < this.count; i++) {
            this.visited[i] = false;
        }
    }
    // 清空dfs结果
    initDfsArr() {
        this.dfsArr = [];
    }
    // 清空bfs结果
    initBfsArr() {
        this.bfsArr = []
    }
    // 清空 edgeTo
    initEdgeTo() {
        this.edgeTo = [];
    }
    // 向图中增加顶点
    addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
    // 打印邻接表
    showGraph() {
        let str = '';
        for (let i = 0; i < this.count; i++) {
            str += (i + " -> ");
            for (let j = 0, len = this.adj[i].length; j < len; j++) {
                if (this.adj[i][j] != undefined) {
                    str += (this.adj[i][j] + ' ');
                }
            }
            str += "\n";
        }
        return str;
    }
    // 调用dfs
    initDfs(v) {
        this.initVisited();
        this.initDfsArr();
        this.dfs(v);
    }
    // 调用bfs
    initBfs(v) {
        this.initVisited();
        this.initBfsArr();
        this.initEdgeTo();
        this.bfs(v);
    }
    // 深度优先遍历 
    dfs(v) {
        // 置空结果
        // 当前访问点设置已访问
        this.visited[v] = true;
        if (this.adj[v] != undefined) {
            console.log("visited " + v);
            // 加入结果数组
            this.dfsArr.push(v);
        }
        for (let w of this.adj[v]) {
            // 邻接点未访问继续dfs
            if (!this.visited[w]) {
                this.dfs(w);
            }
        }
    }
    // 广度优先遍历
    bfs(start) {
        // 开一个队列
        const que = [];
        // 将当前点设置已经访问
        this.visited[start] = true;
        // 将起点加入队列
        que.push(start);
        // 如果队列中一直有值
        while (que.length > 0) {
            // 每次出队一个顶点 
            let v = que.shift();
            // 如果存在点 则表示遍历了该点,则加入结果数组中
            if (v != undefined) {
                console.log("visited " + v);
                this.bfsArr.push(v);
            }
            // 遍历当前访问的顶点的所有相邻顶点
            for (let w of this.adj[v]) {
                // 如果相邻的顶点未访问,则加入队列中,并设置访问状态
                if (!this.visited[w]) {
                    this.visited[w] = true;
                    // 表示从 w -> v 存在一条路径
                    this.edgeTo[w] = v;
                    // console.log(w + " -> " + v);
                    que.push(w);
                }
            }
        }
    }
    // 显示不同的点的路径
    pathTo(start, v) {
        let source = start;
        if (!this.hasPathTo(v)) {
            return undefined;
        }
        const path = [];
        for (let i = v; i != source; i = this.edgeTo[i]) {
            path.push(i);
        }
        path.push(source);
        return path.reverse();
    }
    // 判断某个点是否访问过
    hasPathTo(v) {
        return this.visited[v];
    }
}

const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(1, 4);
g.addEdge(3, 4);
console.log(g.adj);
let str = g.showGraph();
console.log(str);
console.log(g.visited);
console.log("---------------------------------------------- DFS");
g.initDfs(0, 4);
console.log(g.dfsArr);
console.log("---------------------------------------------- DFS");
g.initDfs(4);
console.log(g.dfsArr);
console.log("---------------------------------------------- BFS");
g.initBfs(0);
console.log(g.bfsArr);
console.log(g.edgeTo);
// console.log("---------------------------------------------- BFS");
// g.initBfs(4);
// console.log(g.bfsArr);
let arr = g.pathTo(0, 4);
console.log(arr);

1.png

注代码参考《数据结构与算法javascript表示》,但有不同