web前端开发技术博客
当前位置: 壹题 > 第5题:分别介绍什么是深度优先遍历和广度优先遍历 如何实现这两种遍历算法

第5题:分别介绍什么是深度优先遍历和广度优先遍历 如何实现这两种遍历算法

2019-06-05 分类:壹题 作者:码云 阅读(2443)

本文主要介绍了JavaScript树的深度优先遍历和广度优先遍历算法,结合实例形式分析了JavaScript树的深度优先遍历、广度优先遍历递归与非递归相关实现技巧,需要的朋友可以参考下

什么是图?

图是一种复杂的非线性结构,它由边(边Edge)和点(顶点Vertex)组成。一条边连接的两个点称为相邻顶点。

1
G = (V, E)

图分为:

  • 有向图
  • 无向图

本文探讨的是无向图

图的表示

图的表示一般有以下两种:

  • 邻接矩阵:使用二维数组来表示点与点之间是否有边,如arr<i>[j]=1表示节点i与节点j之间有边,arr<i>[j]=0表示节点i与节点j之间没有边
  • 邻接表:邻接表是图的一种链式储存结构,这种结构类似树的子链表,对于图中的每一个顶点Vi,把所有邻接于Vi的顶点Vj链成一个单链表,这个单链表就是顶点Vi的邻接表,单链表一般由数组或字典结构表示。

创建图

下面声明图类,Vertex用数组结构表示,Edge用map结构表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function Graph() {
    this.vertices = [] // 顶点集合
    this.edges = new Map() // 边集合
}
Graph.prototype.addVertex = function(v) { // 添加顶点方法
    this.vertices.push(v)
    this.edges.set(v, [])
}
Graph.prototype.addEdge = function(v, w) { // 添加边方法
    let vEdge = this.edges.get(v)
    vEdge.push(w)
    let wEdge = this.edges.get(w)
    wEdge.push(v)
    this.edges.set(v, vEdge)
    this.edges.set(w, wEdge)
}
Graph.prototype.toString = function() {
    var s = ''
    for (var i=0; i&lt;this.vertices.length; i++) {
        s += this.vertices[i] + ' -&gt; '
        var neighors = this.edges.get(this.vertices[i])
        for (var j=0; j&lt;neighors.length; j++) {
            s += neighors[j] + ' '
        }
        s += '\n'
    }
    return s
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var graph = new Graph()
var vertices = [1, 2, 3, 4, 5]
for (var i=0; i&lt;vertices.length; i++) {
    graph.addVertex(vertices[i])
}
graph.addEdge(1, 4); //增加边
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);

console.log(graph.toString())
// 1 -&gt; 4 3
// 2 -&gt; 3 5
// 3 -&gt; 1 2
// 4 -&gt; 1
// 5 -&gt; 2

测试成功

图的遍历

两种遍历算法:

  • 深度优先遍历
  • 广度优先遍历

深度优先遍历(DFS)

深度优先遍历(Depth-First-Search),是搜索算法的一种,它沿着树的深度遍历树的节点,尽可能深地搜索树的分支。当节点v的所有边都已被探寻过,将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止,如果还有未被发现的节点,则选择其中一个未被发现的节点为源节点并重复以上操作,直到所有节点都被探寻完成。

简单的说,DFS就是从图中的一个节点开始追溯,直到最后一个节点,然后回溯,继续追溯下一条路径,直到到达所有的节点,如此往复,直到没有路径为止。

DFS可以产生相应图的拓扑排序表,利用拓扑排序表可以解决很多问题,例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。

注意:深度DFS属于盲目搜索,无法保证搜索到的路径为最短路径,也不是在搜索特定的路径,而是通过搜索来查看图中有哪些路径可以选择。

步骤:

  • 访问顶点v;
  • 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
  • 若此时途中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到所有顶点均被访问过为止。

实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Graph.prototype.dfs = function() {
   var marked = []
   for (var i=0; i&lt;this.vertices.length; i++) {
       if (!marked[this.vertices[i]]) {
           dfsVisit(this.vertices[i])
       }
   }

   function dfsVisit(u) {
       let edges = this.edges
       marked[u] = true
       console.log(u)
       var neighbors = edges.get(u)
       for (var i=0; i&lt;neighbors.length; i++) {
           var w = neighbors[i]
           if (!marked[w]) {
               dfsVisit(w)
           }
       }
   }
}

测试:

1
2
3
4
5
6
graph.dfs()
// 1
// 4
// 3
// 2
// 5

测试成功。

广度优先遍历(BFS)

广度优先遍历(Breadth-First-Search)是从根节点开始,沿着图的宽度遍历节点,如果所有节点均被访问过,则算法终止,BFS同样属于盲目搜索,一般用队列数据结构来辅助实现BFS。

BFS从一个节点开始,尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的,首先检查最靠近第一个节点的层,再逐渐向下移动到离起始节点最远的层。

步骤:

  • 创建一个队列,并将开始节点放入队列中;
  • 若队列非空,则从队列中取出第一个节点,并检测它是否为目标节点;
  • 若是目标节点,则结束搜寻,并返回结果;若不是,则将它所有没有被检测过的字节点都加入队列中;
  • 若队列为空,表示图中并没有目标节点,则结束遍历。

实现方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Graph.prototype.bfs = function(v) {
   var queue = [], marked = []
   marked[v] = true
   queue.push(v) // 添加到队尾
   while(queue.length &gt; 0) {
       var s = queue.shift() // 从队首移除
       if (this.edges.has(s)) {
           console.log('visited vertex: ', s)
       }
       let neighbors = this.edges.get(s)
       for(let i=0;i&lt;neighbors.length;i++) {
           var w = neighbors[i]
           if (!marked[w]) {
               marked[w] = true
               queue.push(w)
           }
       }
   }
}

测试:

1
2
3
4
5
6
graph.bfs(1)
// visited vertex:  1
// visited vertex:  4
// visited vertex:  3
// visited vertex:  2
// visited vertex:  5

测试成功。

「如果觉得我的文章对您有用,请帮助本站成长」

赞(0) 打赏

觉得文章有用就打赏一下文章作者

支付宝
微信
0

觉得文章有用就打赏一下文章作者

支付宝
微信

上一篇:

下一篇:

共有 0 条评论 - 第5题:分别介绍什么是深度优先遍历和广度优先遍历 如何实现这两种遍历算法

博客简介

码云笔记: mybj123.com,一个关注Web前端开发技术的博客,主要记录和总结前端工作中常用的知识及我的生活。
更多博客详情请看关于博客

圈子

关注微信公众号
关注微信公众号

精彩评论

服务热线:
 13888888888

 QQ在线交流