建图
- 第一种是基础课里面的,用数组表示多个单链表,每个单链表都是一个有向边。无向图可以看做双向联通的有向图。
参考基础课截图:
// 邻接表
let idx = 0
const h = new Array(100010).fill(-1) // h[a]表示每个链表的头结点,a就是当前节点的值
const e = new Array(200020).fill(0) // e[idx]表示当前节点的值
const ne = new Array(200020).fill(0) // ne[idx]表示当前节点的next节点的值
// 状态数组,存储是否遍历过
const st = new Array(100010).fill(false)
// 添加边,即一般是在链表头结点插入新的节点
const add = (a, b) =>{
e[idx] = b // 先创建b节点
ne[idx] = h[a] // 将b节点的next指向head[a]
h[a] = idx++ // 将head[a]指向b,再移动idx
}
// 初始化数据
for(let i = 1; i<inputs.length; i++){
const [a, b] = inputs[i].split(" ").map(ele=>+ele)
add(a, b) // 添加a -> b的边
add(b, a) // 添加b -> a的边
}
// 找下一个节点
let t = node //假设t是当前的节点,需要找到t连接的后续节点
for(let i = h[t]; i !== -1; i = ne[i]){
const j = e[i] // j就是下一个节点
}
- 第二种,则更简单,通过嵌套数组实现
const g = Array.from({length: N}, () => []) // ver1: [ver1, ver2, ...]
const degree = Array.from({length: N}, () => 0) // 如果是拓扑排序,需要记录入度
const dist = Array,from({length: N}, () => Infinity) // 如果是dijkstra,需要记录当前距离
const st = Array.from({length: N}, () => false) // 是否走过之类的状态记录
// 初始化数据
for(let i = 1; i< inputs.length; i++){
const [a, b] = inputs[i]
g[a].push(b) // 添加a -> b的边
}
BFS
在 无权图 中,由于广度优先遍历本身的特点,假设源点为 source,只有在遍历到 所有 距离源点 source 的距离为 d 的所有结点以后,才能遍历到所有 距离源点 source 的距离为 d + 1 的所有结点。
特别注意📢:将结点添加到队列以后,一定要马上标记为「已经访问」,否则相同结点会重复入队。
经典例题:Flood-Fill
LC 695. 岛屿的最大面积
var maxAreaOfIsland = function(grid) {
const m = grid.length
const n = grid[0].length
const dx = [1, 0, -1, 0]
const dy = [0, 1, 0, -1]
const bfs = (i, j) => {
const queue = []
let size = 0
queue.push([i, j])
grid[i][j] = 0 // 入队之后马上标记!
while(queue.length){
const [x, y] = queue.shift()
size += 1
for(let i = 0; i < 4; i++){
const nx = x + dx[i]
const ny = y + dy[i]
if(nx < 0 || nx >= m || ny < 0 || ny >= n || !grid[nx][ny]) continue
queue.push([nx, ny])
grid[nx][ny] = 0 // 入队之后马上标记!
}
}
return size
}
let res = 0
for(let i = 0; i < m; i++){
for(let j = 0; j < n; j++){
if(grid[i][j]){
res = Math.max(res, bfs(i, j))
}
}
}
return res
};
下面这几种都是BFS的思想延伸。
拓扑排序
拓扑排序要解决的问题是给一个有向无环图的所有节点排序。
主要步骤是:
- 建图,并且记录入度
- 将所有入度为0的点加入queue
- 针对弹出queue的节点,遍历将其连接的点入度减一,如果减后入度为0,则加入queue中
- 最后可以通过记录弹出queue的节点数与题目给的n是否相等,如果不等说明不是拓扑序,存在环
const isTopsort = () => {
// 建图
for (const [a, b] of inputs) {
add(a, b);
degree[b]++;
}
const queue = [];
for (let i = 1; i <= n; i++) {
// 如果入度为0,则可以加入队列
if (!degree[i]) {
queue.push(i);
}
}
while (queue.length) {
let t = queue[0];
topSort.push(t); // 记录拓扑序
// 如果需要记录层数,则最好先试用size记录,再在内部循环里弹出
queue.shift();
for (const ver of degree) {
// 将子节点的入度-1
degree[ver]--;
// 如果减少后,入度为0,则加入队列
if (degree[ver] === 0) {
queue.push(ver);
}
}
}
return topSort.length === n;
};
Floyd(多源最短路)
一个图的所有节点对的最短路径问题。
// 初始化邻接矩阵,自己到自己的距离为0
const g = new Array(n+1).fill(Infinity).map(ele=>new Array(n+1).fill(Infinity))
for(let i = 1; i<=n; i++){
for(let j = 1; j<=n; j++){
if(i === j){
g[i][j] = 0 // 注意 自己到自己 是0
}
}
}
for(const [a, b, w] of inputs){
// 读入距离,又或者自己计算
// 记得处理重边!!!
g[a][b] = Math.min(g[a][b], w) // 这里需要取Min!
}
// dist[i,j]表示i到j的最短距离,K是穷举i,j的断点。
const floyd = () =>{
// 外层枚举从i到j的路径中的中间节点k
for(let k = 1; k <= n; k++){
// 内层 双重循环求最短路
for(let i = 1; i <= n; i++){
for(let j = 1; j <= n; j++){
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]) // 记得取min
}
}
}
}
Dijkstra
定义 g[i][j]
表示节点 i 到节点 j 这条边的边权。如果没有 i 到 j 的边,则 g[i][j] = Infinity
定义 dist[i]
表示节点 0 到节点 i 的最短路长度,一开始 dis[0] = 0
,其余 dis[i] = Infinity
表示尚未计算出。
我们的目标是计算出最终的 dist
数组。
- 首先更新节点 0 到其邻居 y 的最短路,即更新 dis[y] 为 g[0][y]。
-
然后取除了节点 0 以外的 dis[i] 的最小值,假设最小值对应的节点是 3。此时可以断言:dis[3] 已经是 0 到 3 的最短路长度,不可能有其它 0 到 3 的路径更短!
反证法:假设存在更短的路径,那我们一定会从 000 出发经过一个点 uuu,它的 dis[u]\textit{dis}[u]dis[u] 比 dis[3]\textit{dis}[3]dis[3] 还要小,然后再经过一些边到达 333,得到更小的 dis[3]\textit{dis}[3]dis[3]。但 dis[3]\textit{dis}[3]dis[3] 已经是最小的了,并且图中没有负数边权,所以 uuu 是不存在的,矛盾。故原命题成立,此时我们得到了 dis[3]\textit{dis}[3]dis[3] 的最终值。
用节点 3 到其邻居 y 的边权 g[3][y] 更新 dis[y]:如果 dis[3]+g[3][y]<dis[y]\textit{dis}[3] + g[3][y] < \textit{dis}[y]dis[3]+g[3][y]<dis[y],那么更新 dis[y]\textit{dis}[y]dis[y] 为 dis[3]+g[3][y]\textit{dis}[3] + g[3][y]dis[3]+g[3][y],否则不更新。
然后取除了节点 0,30,30,3 以外的 dis[i]\textit{dis}[i]dis[i] 的最小值,重复上述过程。
由数学归纳法可知,这一做法可以得到每个点的最短路。当所有点的最短路都已确定时,算法结束。