用JavaScript实现图的广度优先和深度优先遍历

Hydrogen 发布于2019-08-23 17:11 / 3346人阅读

摘要：图的相关术语有一条边相连的顶点叫相邻顶点一个顶点的度就是该顶点的相邻顶点数路径指顶点组成的连续序列简单路径没有重复顶点有向图和无向图图的表示邻接矩阵代表节点和节点相邻，否则不相邻邻接表相当于把每个节点的相邻节点一一列举出来。

1.图的相关术语

1.1.有一条边相连的顶点叫相邻顶点；
1.2.一个顶点的度就是该顶点的相邻顶点数；
1.3.路径指顶点组成的连续序列；
1.4.简单路径没有重复顶点；
1.5.有向图和无向图

2.图的表示 2.1.邻接矩阵

arrayi ===1代表i节点和j节点相邻，否则不相邻

2.2.邻接表

相当于把每个节点的相邻节点一一列举出来。

2.3.关联矩阵

形式和邻接矩阵一样，只是把邻接矩阵的直接维度换成对应的边，适用于边比顶点多的情况。

3.创建图类

接下来就采用邻接表的方式创建上面的图并且采用字典来表示：

3.1.创建字典类

/创建字典类
    function Dictionary(){
    var items = {};
    
    //set(key,value)向字典里添加新元素，这里主要用来添加边
    this.set = function(key,value){
        items[key] = value;
    }

    //has(key)如果存在就返回true，否则false
    this.has = function(key){
        return key in items;
    }

    //get(key)通过key查找特定的数值并返回，这里主要用来查找顶点对应的边数组
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
}

3.2.创建图类

//创建图类Graph()
function Graph(){
    var vertices = [];    //用来储存顶点
    var adjList = new Dictionary();    //用来储存边

    //创建initializeColor用来初始化各个顶点的颜色，为遍历过程中的标记做准备
    var initializeColor = function(){
        var color = [];
        for (var i=0; i";
            var neighbors = adjList.get(vertices[i]);
            for(var j=0; j
3.3.创建实例
//创建实例
var graph = new Graph();
var myVertices = ["A","B","C","D","E","F","G","H","I"];
//添加顶点
for(var i=0; i
输出的结果为：
A->B C D 
B->A E F 
C->A G D 
D->A C G H 
E->B I 
F->B 
G->C D 
H->D 
I->E 

4.图的遍历
4.1.广度优先遍历

采用队列的方式，先添加节点的先被探索；
采用三种颜色来反应节点的状态：
白色：还没被访问；
灰色：被访问但未被探索；
黑色：被访问且探索过；
思路：
首先搜索节点A，探索A节点的相邻节点B,C,D,把其加入队列中，再逐一出队列进行探索，从而实现广度遍历。
添加bfs方法
//广度优先遍历，在Graph()类中添加以下方法
    this.bfs = function(v, callback){
        var color = initializeColor();    //初始化节点，都标记为白色
        var queue = [];    //创建队列用来顶点的入队；
        queue.push(v);    //访问的节点入队列
        while(!queue.length==0){    //如果队列非空就执行以下
            var u = queue.shift();    //节点出队列
            var neighbors = adjList.get(u);  //探索节点对应的边
            color[u] = "grey";    //把搜索过的节点变成灰色
            for (var i=0; i
创建bfs实例
//bfs实例
function printNode(value){
    console.log("Visited vertex:"+value);
}
graph.bfs(myVertices[0],printNode);

bfs输出结果
Visited vertex:A
Visited vertex:B
Visited vertex:C
Visited vertex:D
Visited vertex:E
Visited vertex:F
Visited vertex:G
Visited vertex:H
Visited vertex:I

使用BFS寻找最短路径

this.BFS = function(v){
        var color = initializeColor(),
        queue = [],
        d = [],    //用来储存从v到u的距离
        pred = [];    //用来储存节点的前溯点
        queue.push(v);

        for(var i=0; i
创建BFS实例
//BFS实例
var shortestPathA = graph.BFS(myVertices[0]);//需要输入头节点myVertices[0]
//console.log(shortestPathA);

//搜索路径BFS
var fromVertex = myVertices[0];
for (var i=1; i
BFS输出结果
A-B
A-C
A-D
A-B-E
A-B-F
A-C-G
A-D-H
A-B-E-I

4.2.深度优先遍历

采用栈的方式，先添加节点的先被探索；
由递归实现。

思路：
从节点A开始，探索到A的相邻节点B,C,D压入栈中（这里的代码采用for循环，所以没有实质上的栈，但是用栈更容易理解），接着搜索B，探索到B的相邻节点E,F压入栈中，以此递归。
添加dfs方法
this.dfs = function(callback){
var color = initializeColor();
for (var i=0; i
}
var dfsVisit = function(u, color, callback){
color[u] = "grey";
if(callback){
    callback(u);
}
var neighbors = adjList.get(u);
for(var i=0; i
}
创建dfs实例
graph.dfs(printNode);

dfs输出结果
Visited vertex:A
Visited vertex:B
Visited vertex:E
Visited vertex:I
Visited vertex:F
Visited vertex:C
Visited vertex:G
Visited vertex:D
Visited vertex:H

关注微信公众号“厦猿”，获取更多前端学习资料！

私有云 GPU服务器广度优先遍历广度优先搜索 python广度优先广度优先搜索算法代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103940.html

图的JS实现

摘要：图的实现如下采用邻接表结构实现。由于本次示例的是无向图，因此每个顶点都互相增加为邻接点。然而由于本次示例的图为无向图，会出现重复遍历的情况，例如顶点的邻接点有，的邻接点有。图的定义图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明，例如人际关系，或者地图。其中图还分为有向图和无向图。如下就是有向图图的数据结构对于图这种关系，可以通过两种方式来存储。领接表将...

LeanCloud 2019-08-21 17:00 评论0 收藏0
Javascript的数据结构与算法(三)

摘要：存在好几种方式来表示这种数据结构。下面的示意图展示了邻接表数据结构。在关联矩阵中矩阵的行表示顶点列表示边。广度优先搜索算法和深度优先搜索算法基本上是相同的只有一点不同那就是待访问顶点列表的数据结构。 1 树一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点(11)。它没有父节点。树中的每个元素都叫作...

MasonEast 2019-08-21 11:24 评论0 收藏0
JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

摘要：算法之深度优先遍历和广度优先遍历背景在开发页面的时候，我们有时候会遇到这种需求在页面某个节点中遍历，找到目标节点，我们正常做法是利用选择器，或者，但在本文，我们从算法的角度去查找节点，同时理解一下深度优先遍历和广度优先遍历的原理。 JS算法之深度优先遍历(DFS)和广度优先遍历(BFS) 背景在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，...

roadtogeek 2019-08-23 16:33 评论0 收藏0
算法系列——JavaScript中广度优先搜索思想实现

摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。什么是广度优先搜索？如果只是是背概念，幼儿园的小朋友都能背下来念给你听。假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...

everfly 2019-08-21 17:36 评论0 收藏0