用js来实现那些数据结构16(图02-图的遍历)

简介:   上一篇文章我们简单介绍了一下什么是图,以及用JS来实现一个可以添加顶点和边的图。按照惯例,任何数据结构都不可或缺的一个point就是遍历。也就是获取到数据结构中的所有元素。那么图当然也不例外。这篇文章我们就来看看如何遍历以及用js来实现图的遍历。

  上一篇文章我们简单介绍了一下什么是图,以及用JS来实现一个可以添加顶点和边的图。按照惯例,任何数据结构都不可或缺的一个point就是遍历。也就是获取到数据结构中的所有元素。那么图当然也不例外。这篇文章我们就来看看如何遍历以及用js来实现图的遍历。

  首先,有两种算法可以对图进行遍历:广度优先搜索(BFS)和深度优先搜索(DFS)。图的遍历可以用来寻找特定的顶点,可以寻找两个顶点之间有哪些路径,检查图是否是联通的,也可以检查图是否含有环等等。

  在开始代码之前,我们需要了解一下图遍历的思想,也就是说,我们要知道如何去遍历一个图,知道了图遍历的方法方式,距离实现代码也就不远了。

  图遍历的思想是:

    1、必须追踪每个第一次访问的节点,并且追踪有哪些节点还没有被完全探索。对于BFS和DFS两种算法,都需要明确给出第一个被访问的顶点。

    2、完全探索一个顶点,要求我们查看该顶点的每一条边。对于每一条边所链接的没有被访问过的顶点,将其标注为被发现的,并将其加入到待访问顶点列表中。

  那么,总结一下上面的两句话,首先,我们在遍历一个图的时候,需要指定第一个被访问的顶点是什么(也就是我们要在方法中传入第一个顶点的值)。然后呢.....我们需要知道三个状态:

    一个是还未被访问的,也就是我还不知道有这么个顶点,也不知道它的边都去向哪里。

    另外一个是已经访问过但未被探索过,就是说,我知道有这个顶点,但是我不知道它的边都去向哪里,连接着哪些顶点。

    最后一个是访问过并且完全探索过。也就是我访问过该顶点,也探索过它有哪些边,它的边连接哪些顶点。

  那么,我们就会在构造函数中用三种颜色来代表上面的三种状态,分别是白色(未被访问),灰色(已经访问过但未被探索过)和黑色(访问过并且完全探索过);

  还有另外一个要注意的地方,BFS和DFS在算法上其实基本上是一样的,但是有一个明显的不同——待访问顶点的数据结构。BFS用队列来存储待访问顶点的列表,DFS用栈来存储待访问顶点的列表。

  好了,下面我们来上代码。(这里不会贴上所有的代码,只会贴上有关BFS和DFS的相关代码。)

  如果你看到了这里,但是并不觉得自己可以耐心的把下面的代码看完,那么你看到这里就可以 结束所有有关于用js来实现数据结构的内容了。如果你还是想继续往下学习,那么希望你一定可以耐心看完整。

  

//引入前面章节学过的栈和队列,因为我们后面会用到。
function Stack () {};
function Queue() {};

function Graph() {
    var vertices = [];
    var adjList = new Map();
    //添加顶点的方法。
    this.addVertices = function (v) {};
    this.addEdge = function (v,w) {};
    this.toString = function () {};

    //初始化图中各顶点的状态(颜色)的私有方法,并返回该状态数组。
    var initializeColor = function () {
        var color = [];
        for (var i = 0; i < vertices.length; i++) {
            color[vertices[i]] = 'white';
        }
        return color;
    };
    //简单的广度优先搜索算法,传入参数v是图中的某一个顶点,从此顶点开始探索整个图。
    this.bfs = function (v,callback) {
        //为color状态数组赋值,初始化一个队列    
        var color = initializeColor(),queue = new Queue();
        //将我们传入的顶点v入队。    
        queue.enqueue(v);
        // 如果队列非空,也就是说队列中始终有已发现但是未探索的顶点,那么执行逻辑。
        while(!queue.isEmpty()) {
            // 队列遵循先进先出的原则,所以我们声明一个变量来暂时保存队列中的第一个顶点元素。
            var u = queue.dequeue();
            // adjList是我们的邻接表,从邻接表中拿到所有u的邻接顶点。
            neighbors = adjList.get(u);
            //并把状态数组中的u的状态设置未已发现但是未完全探索的灰色状态。
            color[u] = 'grey';
            //我们循环当前的u的所有的邻接顶点,并循环访问每一个邻接顶点并改变它的状态为灰色。
            for(var i = 0; i < neighbors.length; i++) {
                var w = neighbors[i];
                if (color[w] === "white") {
                    color[w] = 'grey';
                    //入队每一个w,这样while循环会在队列中没有任何元素,也就是完全访问所有顶点的时候结束。    
                    queue.enqueue(w);
                }
            }
            // 完全访问后设置color状态。
            color[u] = 'black';
            // 如果存在回调函数,那么就执行回掉函数。
            if(callback) {
                callback(u);
            }
        }
    };


    //改进后计算最短路径的BFS
    // 其实这里改进后的BFS并没有什么特别复杂,只是在原有的bfs的基础上,增加了一些需要计算和储存的状态值。
    // 也就是我们在函数结束后所返回的
    this.BFS = function (v) {
        //d是你传入的顶点v距离每一个顶点的距离(这里的距离仅为边的数量)
        //pred就是当前顶点沿着路径找到的前一个顶点是什么。没有就是null
        var color = initializeColor(),queue = new Queue(),d = [],pred = [];
        //我们把v入队。
        queue.enqueue(v);
        //初始化距离和前置点数组。一个都为0,一个都为null,无需解释。
        for(var i = 0; i < vertices.length; i++) {
            d[vertices[i]] = 0;
            pred[vertices[i]] = null;
        }

        while(!queue.isEmpty()) {
            var u = queue.dequeue();
            neighbors = adjList.get(u);
            color[u] = 'grey';

            for(var i = 0; i < neighbors.length; i++) {
                var w = neighbors[i];
                if (color[w] === "white") {
                    color[w] = 'grey';
                    // 到这里都和bfs方法是一样的,只是多了下面这两个。
                    // 这里容易让人迷惑的是w和u分别是啥?弄清楚了其实也就没啥了。
                    // u是队列中出列的一个顶点,也就是通过u来对照邻接表找到所有的w。
                    // 那么因为是d(距离,初始为0)。所以我们只要在d的数组中w的值设为比u大1也就是d[u] + 1就可以了
                    d[w] = d[u] + 1;
                    // 而这个就不用说了,理解了上面的,这个自然就很好懂了。
                    pred[w] = u;
                    // 这里可能大家会问,循环不会重复加入么?不会!
                    // 注意看这里if (color[w] === "white")这句,如果是white状态才会执行后面的逻辑,
                    // 而进入逻辑后,状态就随之改变了,不会再次访问到访问过的顶点。
                    queue.enqueue(w);
                }
            }
            color[u] = 'black';
        }
        return {
            distances:d,
            predecessors:pred
        }

    };


    
    //深度优先搜索
    // 这个没啥东西大家自己看一下就可以了
    this.dfs = function (callback) {
        var color = initializeColor();

        for(var i = 0; i < vertices.length; i++) {
            if(color[vertices[i]] === 'white') {
                // 这里调用我们的私有方法
                dfsVisit(vertices[i],color,callback);
            }
        }

    };
    //深度优先搜索私有方法
    // 从dfs中传入的三个参数
    var dfsVisit = function (u,color,callback) {
        // 改变u的颜色状态
        color[u] = 'grey';

        if(callback) {callback(u);}
        // 获取所有u的邻接顶点
        var neighbors = adjList.get(u);
        // 循环    
        for(var i = 0; i < neighbors.length; i++) {
            //w为u的每一个邻接顶点的变量
            var w = neighbors[i];
            // 如果是白色的我们就递归调用dfsVisit
            if(color[w] === 'white') {
                dfsVisit(w,color,callback);
            }
        }

        color[u] = 'black';
    };

    //改进后的DFS,其实也就是加入了更多的概念和要记录的值
    

    this.DFS = function () {
        // d,发现一个顶点所用的时间。f,完全探索一个顶点所用的时间,p前溯点。
        var color = initializeColor(),d = [],f = [], p = [];
        // 初始化时间为0;
        time = 0;
        //初始化所有需要记录的对象的值/
        for(var i = 0; i < vertices.length; i++) {
            f[vertices[i]] = 0;
            d[vertices[i]] = 0;
            p[vertices[i]] = null;
        }


        for (var i = 0; i < vertices.length; i++) {
            if(color[vertices[i]] === 'white') {
                DFSVisit(vertices[i],color,d,f,p);
            }
        }

        return {
            discovery:d,
            finished:f,
            predecessors:p
        }
    };
    //注意这里我们为什么要在外层定义时间变量,而不是作为参数传递进DFSVisit。
    //因为作为参数传递在每次递归的时候time无法保持一个稳定变化的记录。
    var time = 0;
    //这里个人觉得也没什么好说的了,如果你看不懂,希望你可以数据结构系列的第一篇看起。
    var DFSVisit = function (u,color,d,f,p) {
        console.log('discovered--' + u);
        color[u] = 'grey';
        d[u] = ++time;

        var neighbors = adjList.get(u);
        for (var i = 0; i < neighbors.length; i++) {
            var w = neighbors[i];
            if (color[w] === 'white') {
                p[w] = u;
                DFSVisit(w,color,d,f,p);
            }
        }

        color[u] = 'black';
        f[u] = ++time;
        console.log('explored--' + u);
    };
}

  上面是有关于BFS和DFS的代码及注释。希望大家可以认真耐心的看完。下面我们来看看简单的最短路径算法和拓扑排序。

  1、最短路径算法

//最短路径,也就是说我们在地图上,想要找到两个点之间的最短距离(我们经常会用地图软件来搜索此地与彼地的路径)。
//那么下面我们就以连接两个顶点之间的边的数量的多少,来计算一下各自的路径,从而得到一个最短路径。
// 我们通过改进后的BFS算法,可以得到下面这样的数据,各个顶点距离初始顶点的距离以及前溯点
var shortestPathA = graph.BFS(verticesArray[0]);
console.log(shortestPathA)
/*
distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F:2,G:2,H:2,I:3],
predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F:"B",G:"C",H:"D",I:"E"]
*/
//我们选择数组中的第一个元素为开始的顶点。
var fromVertex = verticesArray[0];
for(var i = 1; i < verticesArray.length;i++) {
    // 到达的定点不定
    var toVertex = verticesArray[i];
    //声明路径为一个初始化的栈。
    path = new Stack();
    //嘿嘿,这个循环比较有趣了,通常大家都会用var i= 0; i < xxx;i++这种。
    //但是这里这么用是几个意思?首先大家要知道for循环中两个“;”所分割的三个语句都是什么意思。
    //语句 1 在循环(代码块)开始前执行,语句 2 定义运行循环(代码块)的条件,语句 3 在循环(代码块)已被执行之后执行
    //所以我们怎么写都是可以的!!当然你要符合你想要的逻辑
    //后面就不说了,没啥好说的。
    for(var v = toVertex;v!== fromVertex;v = shortestPathA.predecessors[v]) {
        path.push(v);
    }
    path.push(fromVertex);
    var s = path.pop();

    while(!path.isEmpty()) {
        s += '-' + path.pop();
    }
    console.log(s)
}

/*
A-B
A-C
A-D
A-B-E
A-B-F
A-C-G
A-D-H
A-B-E-I
*/

  2、拓扑排序  

  拓扑排序,想了想,还是有必要给大家解释一下概念再开始代码,不然真的容易一脸懵逼。

  大家先来看张图:

  那,这是一个什么东西呢?这是一个有向图,因为边是有方向的,这个图没有环,意味着这是一个无环图。所以这个图可以称之为有向无环图。那么有向无环图可以做什么呢?我记得前面某一篇文章说过,所有的实例都有其所面对的要解决的实际问题。而有向无环图可以视作某一个序列的待执行的任务,该任务不是可跳跃的。比如一个产品上线,需要产品经理定需求,画流程图,再到UI出效果图标注图再到开发再到测试再到改bug再到上线。就是这个意思。

  那么我们上面所形容的产品上线的整个流程就成为拓扑排序。拓扑排序只能应用于DAG(有向无环图)。

  那么我们看下代码。

//重新声明一个图并所有的顶点加入图中。
var DFSGraph = new Graph();
var DFSarray = ["a","b","c","d","e","f"];
for (var i = 0; i < DFSarray.length; i++) {
    DFSGraph.addVertices(DFSarray[i]);
}
//我们为图加上边。
DFSGraph.addEdge("a","c");
DFSGraph.addEdge("a","d");
DFSGraph.addEdge("b","d");
DFSGraph.addEdge("b","e");
DFSGraph.addEdge("c","f");
DFSGraph.addEdge("f","e");
var result = DFSGraph.DFS();
console.log(result);
//大家自己去看看打印的结果是什么。

  那么到这里,有关于图的一部分内容基本上就都讲解完毕了。可能大家觉得我有些偷懒,注释写的没有以前那么详细了啊。这是因为我觉得很多的内容前面都已经很详细的说明过了。同样的思路实在是没必要翻来覆去的说来说去。所以反而到后面一些复杂的数据结构并没有前面解释的那么详细。但是我觉得如果你一路看下来,这点东西绝壁难不倒你。

   

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

一只想要飞得更高的小菜鸟
目录
相关文章
|
2月前
|
JavaScript 前端开发 索引
js遍历的方法与区别
js遍历的方法与区别
49 3
|
4天前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
4月前
|
存储 算法
数据结构===图
数据结构===图
|
1月前
|
JavaScript 前端开发
JavaScript基础知识-数组的遍历
关于JavaScript数组遍历基础知识的文章。
32 2
JavaScript基础知识-数组的遍历
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
2月前
|
JavaScript 前端开发
JavaScript基础&实战(5)js中的数组、forEach遍历、Date对象、Math、String对象
这篇文章介绍了JavaScript中的数组、Date对象、Math对象以及包装类(String、Number、Boolean),并详细讲解了数组的创建、方法(如forEach、push、pop、unshift、slice、splice)和遍历操作,以及工厂方法创建对象和原型对象的概念。
JavaScript基础&实战(5)js中的数组、forEach遍历、Date对象、Math、String对象
|
2月前
【数据结构】遍历二叉树(递归思想)-->赋源码
【数据结构】遍历二叉树(递归思想)-->赋源码
49 4
|
2月前
|
机器学习/深度学习 JavaScript
node.js实现遍历所有文件夹里面的js文件,提取所有的url
node.js实现遍历所有文件夹里面的js文件,提取所有的url
|
2月前
|
JavaScript
js之遍历方法
js之遍历方法
31 0
|
3月前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器:DFS 和 BFS。Python 中,图可表示为邻接表或矩阵。DFS 沿路径深入,回溯时遍历所有可达顶点,适合找路径和环。BFS 层次遍历,先近后远,解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习,掌握这些算法,图处理将游刃有余。
53 3