是什么

图： 抽象的数据结构

• 有向图： 顶点v,w 只能v向w，不能反向， 则v是起始点，w是终点
• 无向图： 顶点v,w， v到w，和w到v是完全相同的

表达图

• 邻接矩阵
• 邻接表

邻接矩阵

邻接表

操作

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

深度

const visited = new Set()
const dfs = (n) => {
  console.log(n)
  visited.add(n) // 访问过添加记录
  graph[n].forEach(c => {
    if(!visited.has(c)){ // 判断是否访问呢过
      dfs(c)
    }
  })
}

广度

const visited = new Set()
const dfs = (n) => {
  visited.add(n)
  const q = [n]
  while(q.length){
    const n = q.shift()
    console.log(n)
    graph[n].forEach(c => {
      if(!visited.has(c)){
        q.push(c)  
        visited.add(c)
      }
    })
  }
}