图的深度优先遍历和广度优先遍历

x33g5p2x  于2022-03-11 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(227)

一、写在前面
图的深度优先遍历和广度优先遍历,也是我们必须要明白的算法。下面我们以有向图为了,来总结一下,图是如何做到深度优先遍历和广度优先遍历的。

使用数组表示如下所示

let graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
}

二、深度优先遍历

const graph = require('./database')

let set = new Set()   //使用Set数据结构来保存已经访问了的node节点。
const dfs = (node) => {
  console.log(node)
  set.add(node)     //将访问好的node节点,放入set中
  graph[node].forEach(item => {
    if(!set.has(item)) { //如果当前节点没有被访问,则进行递归访问
      dfs(item)
    }
  })
}

dfs(2)
//2 0 1 3

二、广度优先遍历

const graph = require('./database')

const bfs = (node) => {
  let set = new Set()
  let queue = [node]
  while(queue.length) {
    let cur = queue.shift()
    set.add(cur)
    console.log(cur)
    graph[cur].forEach(item => {
      if(!set.has(item)) {
        queue.push(item)
      }
    })    
  }
}

bfs(2)  //2031

下面代码为广度优先遍历,我们使用的数据结构是Set(集合)和queue的 数据结构。

相关文章

微信公众号

最新文章

更多