打卡51天------图论(深搜/广搜应用题)

注意深搜的两种写法，熟练掌握这两种写法 以及 知道区别在哪里，才算掌握的深搜。

代码随想录

const r1 = require('readline').createInterface({ input: process.stdin });
// 创建readline接口
let iter = r1[Symbol.asyncIterator]();
// 创建异步迭代器
const readline = async () => (await iter.next()).value;let graph
let N, M
let visited
let result = 0
const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]// 读取输入，初始化地图
const initGraph = async () => {let line = await readline();[N, M] = line.split(' ').map(Number);graph = new Array(N).fill(0).map(() => new Array(M).fill(0))visited = new Array(N).fill(false).map(() => new Array(M).fill(false))for (let i = 0; i < N; i++) {line = await readline()line = line.split(' ').map(Number)for (let j = 0; j < M; j++) {graph[i][j] = line[j]}}
}/*** @description: 从节点x,y开始深度优先遍历* @param {*} graph 是地图，也就是一个二维数组* @param {*} visited 标记访问过的节点，不要重复访问* @param {*} x 表示开始搜索节点的下标* @param {*} y 表示开始搜索节点的下标* @return {*}*/
const dfs = (graph, visited, x, y) => {for (let i = 0; i < 4; i++) {const nextx = x + dir[i][0]const nexty = y + dir[i][1]if (nextx < 0 || nextx >= N || nexty < 0 || nexty >= M) continueif (!visited[nextx][nexty] && graph[nextx][nexty] === 1) {visited[nextx][nexty] = truedfs(graph, visited, nextx, nexty)}}
}(async function () {// 读取输入，初始化地图await initGraph()// 统计岛屿数for (let i = 0; i < N; i++) {for (let j = 0; j < M; j++) {if (!visited[i][j] && graph[i][j] === 1) {// 标记已访问visited[i][j] = true// 遇到没访问过的陆地，+1result++// 深度优先遍历，将相邻陆地标记为已访问dfs(graph, visited, i, j)}}}console.log(result);
})()

二、岛屿数量 广搜

注意广搜的两种写法，第一种写法为什么会超时， 如果自己做的录友，题目通过了，也要仔细看第一种写法的超时版本，弄清楚为什么会超时，因为你第一次 幸运 没那么想，第二次可就不一定了。

代码随想录

const r1 = require('readline').createInterface({ input: process.stdin });
// 创建readline接口
let iter = r1[Symbol.asyncIterator]();
// 创建异步迭代器
const readline = async () => (await iter.next()).value;let graph
let N, M
let visited
let result = 0
const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]// 读取输入，初始化地图
const initGraph = async () => {let line = await readline();[N, M] = line.split(' ').map(Number);graph = new Array(N).fill(0).map(() => new Array(M).fill(0))visited = new Array(N).fill(false).map(() => new Array(M).fill(false))for (let i = 0; i < N; i++) {line = await readline()line = line.split(' ').map(Number)for (let j = 0; j < M; j++) {graph[i][j] = line[j]}}
}/*** @description: 从(x, y)开始广度优先遍历* @param {*} graph 地图* @param {*} visited 访问过的节点* @param {*} x 开始搜索节点的下标* @param {*} y 开始搜索节点的下标* @return {*}*/
const bfs = (graph, visited, x, y) => {let queue = []queue.push([x, y])visited[x][y] = true  //只要加入队列就立刻标记为访问过while (queue.length) {let [x, y] = queue.shift()for (let i = 0; i < 4; i++) {let nextx = x + dir[i][0]let nexty = y + dir[i][1]if(nextx < 0 || nextx >= N || nexty < 0 || nexty >= M) continueif(!visited[nextx][nexty] && graph[nextx][nexty] === 1){queue.push([nextx, nexty])visited[nextx][nexty] = true}}}}(async function () {// 读取输入，初始化地图await initGraph()// 统计岛屿数for (let i = 0; i < N; i++) {for (let j = 0; j < M; j++) {if (!visited[i][j] && graph[i][j] === 1) {// 遇到没访问过的陆地，+1result++// 广度优先遍历，将相邻陆地标记为已访问bfs(graph, visited, i, j)}}}console.log(result);
})()

三、岛屿的最大面积

本题就是基础题了，做过上面的题目，本题很快。

代码随想录

// 广搜版const r1 = require('readline').createInterface({ input: process.stdin });
// 创建readline接口
let iter = r1[Symbol.asyncIterator]();
// 创建异步迭代器
const readline = async () => (await iter.next()).value;let graph // 地图
let N, M // 地图大小
let visited // 访问过的节点
let result = 0 // 最大岛屿面积
let count = 0 // 岛屿内节点数
const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向// 读取输入，初始化地图
const initGraph = async () => {let line = await readline();[N, M] = line.split(' ').map(Number);graph = new Array(N).fill(0).map(() => new Array(M).fill(0))visited = new Array(N).fill(false).map(() => new Array(M).fill(false))for (let i = 0; i < N; i++) {line = await readline()line = line.split(' ').map(Number)for (let j = 0; j < M; j++) {graph[i][j] = line[j]}}
}/*** @description: 从(x, y)开始广度优先遍历* @param {*} graph 地图* @param {*} visited 访问过的节点* @param {*} x 开始搜索节点的下标* @param {*} y 开始搜索节点的下标* @return {*}*/
const bfs = (graph, visited, x, y) => {let queue = []queue.push([x, y])count++visited[x][y] = true  //只要加入队列就立刻标记为访问过while (queue.length) {let [xx, yy] = queue.shift()for (let i = 0; i < 4; i++) {let nextx = xx + dir[i][0]let nexty = yy + dir[i][1]if(nextx < 0 || nextx >= N || nexty < 0 || nexty >= M) continueif(!visited[nextx][nexty] && graph[nextx][nexty] === 1){queue.push([nextx, nexty])count++visited[nextx][nexty] = true}}}}(async function () {// 读取输入，初始化地图await initGraph()// 统计最大岛屿面积for (let i = 0; i < N; i++) {for (let j = 0; j < M; j++) {if (!visited[i][j] && graph[i][j] === 1) { //遇到没有访问过的陆地// 重新计算面积count = 0// 广度优先遍历，统计岛屿内节点数，并将岛屿标记为已访问bfs(graph, visited, i, j)// 更新最大岛屿面积result = Math.max(result, count)}}}console.log(result);
})()