图

🆕简介

• 图是网络结构的抽象模型，是一组由边链接的节点；

• 图可以表示任何二元关系，比如道路和航班；

• eg img:

图的表示法

邻接矩阵

邻接表

深度优先遍历算法

1. 访问节点
2. 对根节点的没访问过得相邻节点挨个进行深度优先遍历

const visited = new Set();

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

广度优先遍历

1. 新建一个队列，入队根节点
2. 把队头出队并访问
3. 把队头没有访问过得相邻节点入队
4. 重复二、三步，直到队列为空；
5. 

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