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

36次阅读

共计 393 个字符，预计需要花费 1 分钟才能阅读完成。

图构造

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

深度优先


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)

广度优先

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)

正文完