图
- 图是网络结构的抽象模型，是一组由边连接的节点
- 图可以表示任何二元关系，比如道路、航班
- JS中没有图，但是可以用Object和Array构建图
- 图的表示法：邻接矩阵、邻接表、关联矩阵…
邻接矩阵
邻接表
图的深度/广度优先遍历
- 深度优先遍历：尽可能深的搜索图的分支
- 广度优先遍历：先访问离根节点最近的节点
深度优先遍历算法口诀
- 访问根节点
- 对根节点的没访问过的相邻节点挨个进行深度优先遍历
深度优先遍历
// 图，后面不会重复写
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}
const visited = new Set()
const dfs = n => {
console.log(n)
visited.add(n)
graph[n].forEach(c => {
if (!visited.has(c)) {
dfs(c)
}
})
}
dfs(2) // 2 0 1 3
广度优先遍历算法口诀
- 新建一个队列，把根节点入队
- 把队头出队并访问
- 把队头的没访问过的相邻节点入队
- 重复第二、三步，直到队列为空
广度优先遍历
const visited = new Set()
visited.add(2)
const q = [2]
while (q.length) {
const n = q.shift()
console.log(n) // 2 0 3 1
graph[n].forEach(c => {
if (!visited.has(c)) {
q.push(c)
visited.add(c)
}
})
}
有效数字
- 构建一个表示状态的图
- 遍历字符串，并沿着图走，如果到了某个节点无路可走就返回false
- 遍历结束，如走到3/5/6，就返回true，否则返回false
有效数字邻接表图
/**
* @param {string} s
* @return {boolean}
* @description 难点在于画出邻接表图，循环遍历输入，将每一个字符转化为对应属性，用于获取当前状态
*/
const isNumber = function(s) {
const graph = {
0: { blank: 0, sign: 1, dot: 2, digit: 6 },
1: { digit: 6, dot: 2 },
2: { digit: 3 },
3: { digit: 3, e: 4 },
4: { digit: 5, sign: 7 },
5: { digit: 5 },
6: { digit: 6, dot: 3, e: 4 },
7: { digit: 5 },
}
let state = 0 // 初始状态都是0
for (c of s.trim()) { // 题目中前后括号不影响判断，所以先去除前后空格
if (c === ' ') {
c = 'blank'
} else if (c === '+' || c === '-') {
c = 'sign'
} else if (c === '.') {
c = 'dot'
} else if (c.toLowerCase() === 'e') {
c = 'e'
} else if (!isNaN(c)) {
c = 'digit'
}
state = graph[state][c]
if (state === undefined) return false
}
// 合法的三个状态
const validState = [3, 5, 6]
return validState.includes(state)
}
// "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"
const testArr = ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
testArr.forEach(item => {
console.log(isNumber(item))
})
太平洋大西洋水流问题
- 把矩阵想象成图
- 从海岸线逆流而上遍历图，所到之处就是可以流到某个大洋的坐标
- 新建两个矩阵，分别记录能流到两个大洋的坐标
- 从海岸线，多管齐下，同事深度优先遍历图，过程中填充上述矩阵
- 遍历两个矩阵，找出能流到两个大洋的坐标
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
const pacificAtlantic = function(matrix) {
if (!matrix || !matrix[0]) return []
// 生成两个空白矩阵
const m = matrix.length
const n = matrix[0].length
const flow1 = Array.from({length: m}, () => new Array(n).fill(false))
const flow2 = Array.from({length: m}, () => new Array(n).fill(false))
const dfs = (r, c, flow) => {
flow[r][c] = true
const location = [[r - 1, c], [r + 1, c], [r, c -1], [r, c + 1]]
location.forEach(([nr, nc]) => {
if (
// 保证在矩阵中
nr >= 0 && nr < m &&
nc >= 0 && nc < n &&
// 防止死循环
!flow[nr][nc] &&
//保证逆流而上
matrix[nr][nc] >= matrix[r][c]
) {
dfs(nr, nc, flow)
}
})
}
// 沿着海岸线逆流而上
for (let r = 0; r < m; r++) {
dfs(r, 0, flow1)
dfs(r, n - 1, flow2)
}
for (let c = 0; c < n; c++) {
dfs(0, c, flow1)
dfs(m - 1, c, flow2)
}
// 收集能流到两个大洋里的坐标
let res = []
for (let r = 0; r < m; r += 1) {
for (let c = 0; c < n; c += 1) {
if (flow1[r][c] && flow2[r][c]) {
res.push([r, c])
}
}
}
return res
}
const matrix = [
[1, 2, 2, 3, 5],
[3, 2, 3, 4, 4],
[2, 4, 5, 3, 1],
[6, 7, 1, 4, 5],
[5, 1, 1, 2, 4]
]
console.log(pacificAtlantic(matrix))
克隆图
- 拷贝所有节点
- 拷贝所有的边
- 将拷贝的节点，按照原图的连接方法进行连接
这道题没法模拟，dfs中会丢失原索引值，导致填充都为0，但如果将索引一起放进去leeCode又跑不过，只能去leeCode上测试
深度优先解法：
const cloneGraph = function(node) {
if (!node) return
const visited = new Map()
const dfs = n => {
const nCopy = new Node(n.val)
visited.set(n, nCopy)
const neighbors = n.neighbors || []
neighbors.forEach(ne => {
if (!visited.has(ne)) { // 已被记录的邻接边不再记录
dfs(ne)
}
nCopy.neighbors.push(visited.get(ne))
})
}
dfs(node)
return visited.get(node)
}
广度优先解法：
const cloneGraph = function(node) {
if (!node) return
const visited = new Map()
visited.set(node, new Node(node.val))
const q = [node]
while (q.length) {
const n = q.shift()
const neighbors = n.neighbors || []
neighbors.forEach(ne => {
if (!visited.has(ne)) {
q.push(ne)
visited.set(ne, new Node(ne.val))
}
visited.get(n).neighbors.push(visited.get(ne))
})
}
return visited.get(node)
}
