图.md

图

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

图可以表示任何二元关系：道路，航班。。。

道路，航班----四通八达

js 中没有图，但可以用对象和数组构建

图的表示法：邻接矩阵，邻接表，关联矩阵

图常用操作：深度优先遍历，广度优先遍历

65. 有效数字

深度、广度优先遍历

深度优先遍历口诀

访问根节点

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

// 深度优先遍历口诀

// 访问根节点

// 对根节点的没有访问过的相邻节点挨个进行深度优先遍历

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

// 深度优先遍历 // 记录哪些节点访问过 // const visited = new Set() // const dfs = (n) => { // console.log(n); // 2 0 1 3 // // 对没有访问的深度优先遍历 // visited.add(n); // graph[n].forEach((c) => { // if(!visited.has(c)) { // dfs(c) // } // }) // }

// dfs(2);

// 广度优先遍历 // 新建一个队列，把根节点入队 // 把队头出队并访问 // 把队头的没访问过的相邻节点入队 // 重读2，3，直到队列为空 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);
    }
})

}