关于javascript:图的深度与广度优先遍历

图构造

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

  1. 深度优先

const dfs = (root) => {
    const visited = new Set()
    const fn = (n) => {
        console.log(n)
        visited.add(n)
        graph[n].forEach(c => {
            if (!visited.has(c)) {
                fn(c)
            }
        })
    }
    fn(root)
}

dfs(0)

  1. 广度优先
const bfs = (root) => {
    const visited = new Set()
    const q = [root]
    visited.add(root)
    while(q.length) {
        const n = q.shift()
        console.log(n)
        graph[n].forEach(c => {
            if (!visited.has(c)) {
                q.push(c)
                visited.add(c)
            }
        })
    }

}
bfs(0)

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年50元

阿里云限时活动-2核2G-5M带宽-60G SSD-1000G月流量 ,特惠价99元/年(原价1234.2元/年,可以直接买3年),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据