图是网络结构的抽象模型，是一组由边连接的节点。
图可以表示任何二元关系，比如道路、航班...
image.png
image.png
- 深度优先遍历/广度优先遍历
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}
//深度优先
const visited = new Set() //用来标记访问过得节点
const dfs = (node) => {
console.log(node)
visited.add(node)
graph[node].forEach(val => {
if (!visited.has(val)) {
dfs(val)
}
})
}
dfs(2)
// 2
// 0
// 1
// 3
//广度优先
const visited = new Set() //用来标记访问过得节点
visited.add(2)
const bfs = (node) => {
const queue = [node]
while (queue.length) {
const head = queue.shift()
console.log(head)
graph[head].forEach(val => {
if (!visited.has(val)) {
queue.push(val)
visited.add(val)
}
})
}
}
bfs(2)
// 2
// 0
// 3
// 1
