文章目录
第一节：深度和广度优先究竟是指啥
刚开始介绍了什么是图，以及深度和广度如何遍历图
讲的已经是非常细致了。可以多读几遍体会以下二者的区别
图的存储：邻接矩阵存储法
深度遍历图
// 初始化二维矩阵
let n = 5, m = 5;
let e = [];
for (let i = 0; i <= n; i++) {
e[i] = [];
for (let j = 0; j <= m; j++) {
e[i][j] = i === j ? 0 : '∞';
}
}
// 输入图中的边
let eage = [[1, 2], [1, 3], [1, 5], [2, 4], [3, 5]];
for (let i = 0; i < eage.length; i++) {
let x = eage[i][0];
let y = eage[i][1];
// 无向图的对称
e[x][y] = 1;
e[y][x] = 1;
}
console.log(e);
console.table(e)
// 辅助数组
let book = new Array(2 * n).fill(0);
let sum = 0;
const dfs = (cur) => {
// cur 为当前所在顶点编号
console.log(cur);
sum++;
// 如果已经访问所有的点了，就退出
if (sum === n) {
return;
}
for (let i = 1; i <= n; i++) {
if (e[cur][i] === 1 && book[i] === 0) {
book[i] = 1;
dfs(i);
}
}
return;
}
book[1] = 1;
dfs(1);
console.log("book:>>", book);
广度遍历图
广度需要一个队列~
// 初始化二维矩阵
let n = 5,
m = 5;
let e = [];
for (let i = 0; i <= n; i++) {
e[i] = [];
for (let j = 0; j <= m; j++) {
e[i][j] = i === j ? 0 : "∞";
}
}
// 输入图中的边
let eage = [
[1, 2],
[1, 3],
[1, 5],
[2, 4],
[3, 5],
];
for (let i = 0; i < eage.length; i++) {
let x = eage[i][0];
let y = eage[i][1];
// 无向图的对称
e[x][y] = 1;
e[y][x] = 1;
}
console.log(e);
console.table(e);
// 辅助数组
let book = new Array(2 * n).fill(0);
// 队列
let head = 1,
tail = 1;
let que = new Array(100);
// 1入队
que[tail] = 1;
book[1] = 1;
tail++;
while (head < tail && tail <= n) {
for (let i = 1; i <= n; i++) {
if (e[que[head]][i] === 1 && book[i] === 0) {
que[tail] = i;
tail++;
book[i] = 1;
}
if (tail > n) {
break;
}
}
head++;
}
console.log('que:>>', que.slice(1,tail));
第二节：城市地图—图的深度优先遍历
很开心啊，这个也是我慢慢憋出来的，跟书上写的差不多，我写的少了if (dis > min) return;这步算是优化。
// eg. e[1][2] = 3 代表从1城市到2城市的距离是3，单项的
let road = [
[1, 2, 2],
[1, 5, 10],
[2, 3, 3],
[2, 5, 7],
[3, 1, 4],
[3, 4, 4],
[4, 5, 5],
[5, 3, 3],
];
let e = [];
let n = 5; // 城市的个数
for (let i = 0; i <= n; i++) {
let eChild = new Array(n + 1);
e[i] = eChild;
}
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= n; j++) {
e[i][j] = i === j ? 0 : "∞";
}
}
// 初始化图
road.forEach((i) => {
let start = i[0];
let end = i[1];
let dis = i[2];
e[start][end] = dis;
});
console.table(e);
// 初始化辅助数组：标记哪些城市已经走过了
let book = new Array(n + 1).fill(0);
let min = 999;
// 深度优先遍历
const dfs = (cur, dis) => {
if (dis > min) {
// 我自己写的版本没有这个
return;
}
if (cur === n) {
min = Math.min(min, dis);
return;
}
for (let i = 1; i <= n; i++) {
if (e[cur][i] !== "∞" && book[i] === 0) {
book[i] = 1;
dfs(i, dis + e[cur][i]);
book[i] = 0;
}
}
};
dfs(1, 0);
console.log(min);
第三节：最小转机—图的广度优先遍历
class Queue {
constructor() {
this.x;
this.s;
}
}
// 初始化二维矩阵
let n = 5,
m = 5;
let e = [];
for (let i = 0; i <= n; i++) {
e[i] = [];
for (let j = 0; j <= m; j++) {
e[i][j] = i === j ? 0 : "∞";
}
}
// 输入图中的边
let eage = [
[1, 2],
[1, 3],
[2, 3],
[2, 4],
[3, 4],
[3, 5],
[4, 5],
];
for (let i = 0; i < eage.length; i++) {
let x = eage[i][0];
let y = eage[i][1];
// 无向图的对称
e[x][y] = 1;
e[y][x] = 1;
}
console.log(e);
console.table(e);
// 辅助数组
let book = new Array(2 * n).fill(0);
// 队列
let head = 1,
tail = 1;
let que = [];
for (let i = 0; i < 100; i++) {
let queChild = new Queue();
que[i] = queChild;
}
// 1入队
que[tail].x = 1;
que[tail].s = 0;
book[1] = 1;
tail++;
let end = 5;
let flag = 0;
while (head < tail) {
let start = que[head].x;
for (let i = 1; i <= n; i++) {
if (e[start][i] === 1 && book[i] === 0) {
que[tail].x = i;
que[tail].s = que[head].s+1;
tail++;
book[i] = 1;
}
if (que[tail - 1].x === end) {
flag = 1;
break;
}
}
if (flag === 1) {
break;
}
head++;
}
console.log("que:>>", que[tail-1].s);