## 图论做题笔记：dfs

news/2024/4/19 13:07:48/文章来源:https://blog.csdn.net/2301_76612880/article/details/137182764

### Leetcode - 797：所有可能的路径

#### 题目：

`graph[i]` 是一个从节点 `i` 可以访问的所有节点的列表（即从节点 `i` 到节点 `graph[i][j]`存在一条有向边）。

```输入：graph = [[1,2],[3],[3],[]]

```

```输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]

#### 笔记：

dfs就是递归加回溯所以和我们的递归三部曲差不多也有深搜三部曲：

1.确定参数：我们传入的参数有graph和当前节点的下标x

2.确定终止条件：如果我们遍历到了租后一个节点就返回

3.处理目前搜索节点出发的路径：

``````class Solution {
public:vector<int> path;vector<vector<int>> res;void dfs(vector<vector<int>>& graph, int x){if(x == graph.size() - 1){res.push_back(path);return;}for(int i = 0; i < graph[x].size(); i++){path.push_back(graph[x][i]);dfs(graph, graph[x][i]);path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);dfs(graph, 0);return res;}
};``````

### Leetcode - 200：岛屿数量

#### 笔记：

``````class Solution {
public:int opt[4][2] = {1,0,0,-1,0,1,-1,0};void dfs(vector<vector<char>>& graph, vector<vector<bool>>& visited, int x, int y){if(graph[x][y] == '0' || visited[x][y] == true){return;}visited[x][y] = true;for(int i = 0; i < 4; i++){int nextx = x + opt[i][0];int nexty = y + opt[i][1];if(nextx >= 0 && nexty >= 0 && nextx < graph.size() && nexty < graph[0].size()){dfs(graph, visited, nextx, nexty);}else continue;}}int numIslands(vector<vector<char>>& grid) {vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));int count = 0;for(int i = 0; i < grid.size(); i++){for(int j = 0; j < grid[0].size(); j++){if(grid[i][j] == '1' && !visited[i][j]){count++;dfs(grid, visited, i, j);}}}return count;}
};``````

### Leetcode - 547:省份数量

#### 题目：

```输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]

```

```输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]

#### 笔记：

``````class Solution {
public:void dfs(vector<vector<int>>& graph, vector<bool>& visited, int x){for(int i = 0; i < graph.size(); i++){if(graph[x][i] == 1 && !visited[i]){visited[i] = true;dfs(graph, visited, i);}}}int findCircleNum(vector<vector<int>>& isConnected) {int count = 0;vector<bool> visited(isConnected.size(), false);for(int i = 0; i < isConnected.size(); i++){if(!visited[i]){visited[i] = true;count++;dfs(isConnected, visited, i);}}return count;}
};``````

``[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]``

`dfs` 函数中，我们在遍历与城市 `x` 相连的城市时，使用的是 `for` 循环来遍历整个图的每个节点。在每次调用 `dfs` 时，我们从第一个城市开始遍历，即 `i``0` 开始。这是因为我们需要确保遍历整个图，以便找到与给定城市 `x` 相连的所有城市。

### Leetcode - 802: 找到安全的路径：

#### 题目：

```输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]

```

```输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

#### 笔记：

``````class Solution {
public:bool dfs(vector<vector<int>>& graph, vector<int>& visited, int x){if(visited[x] == 1) return false;if(visited[x] == 2) return true;visited[x] = 1;// 检查当前节点的所有连接节点中是否有不安全节点，如果有就返回。for(int i = 0; i < graph[x].size(); i++){if(!dfs(graph, visited, graph[x][i])){return false;}// 假如例题中的2相连的节点有3和5，那么在第一层循环就会直接返回false// 假如3是安全节点而5不是安全节点，那么检查完3会进行i++的操作来检查5并在检查之后返回false}// 顺利通过检查visited[x] = 2;return true;}vector<int> eventualSafeNodes(vector<vector<int>>& graph) {unordered_set<int> res;vector<int> result;vector<int> visited(graph.size());for(int i = 0; i < graph.size(); i++){if(dfs(graph, visited, i)){res.insert(i);}}result.assign(res.begin(), res.end());sort(result.begin(), result.end());return result;}
};``````

### Leetcode - 841:钥匙和房间

#### 题目：

```输入：rooms = [[1],[2],[3],[]]

```

```输入：rooms = [[1,3],[3,0,1],[2],[0]]

#### 笔记：

``````class Solution {
public:void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node){visited[node] = true;for(int i = 0; i < graph[node].size(); i++){if(!visited[graph[node][i]]){dfs(graph, visited, graph[node][i]);}}}bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visited(rooms.size(), false);dfs(rooms, visited, 0);for(int i = 0; i < rooms.size(); i++){if(!visited[i]){return false;}}return true;}
};``````

### Leetcode - 1376:通知所有员工所需的时间：

#### 题目:

```输入：n = 1, headID = 0, manager = [-1], informTime = [0]

```

```输入：n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]

#### 笔记：

``for(int i = 0; i < n; i++){if(manager[i] != -1){mng[manager[i]].push_back(i);}}``

dfs函数思路：

``````class Solution {
public:int dfs(vector<vector<int>>& mng, vector<int>& informTime, vector<bool>& visited, int node){visited[node] = true;int time = 0;for(int i = 0; i < mng[node].size(); i++){if(!visited[mng[node][i]]){time = max(time, dfs(mng, informTime, visited, mng[node][i]));}}return time + informTime[node];}int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {vector<vector<int>> mng(n);for(int i = 0; i < n; i++){if(manager[i] != -1){mng[manager[i]].push_back(i);}}vector<bool> visited(n, false);return dfs(mng, informTime, visited, headID);}
};``````

### Leetcode - 1466:重新规划路线

#### 题目：

`n` 座城市，从 `0` 到 `n-1` 编号，其间共有 `n-1` 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。

```输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]

```输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]

```输入：n = 3, connections = [[1,0],[2,0]]

#### 笔记：

（1）创建pair数组类型：

``````// 我们在这里需要对边进行标记，这里我们需要出发的节点到下一节点：
// [start] --> (end, index)
// 这里用到的就不再是标准的队列结构了，因为这是一个一对二的关系，而队列只是一一对应的关系，所以就要用到pair重组类型来表示：
vector<vector<pair<int, bool>>> a
// 对该结构进行插入操作：
a[i].push_back(make_pair(int, bool))// 对组成pair类型中的特定一个元素进行操作：
a[i] -> first || a[i] -> second``````

``````class Solution {
public:void dfs(vector<vector<pair<int, bool>>>& graph, vector<bool>& visited, int node, int& count){visited[node] = true;for(vector<pair<int, bool>>::iterator it = graph[node].begin(); it != graph[node].end(); it++){if(!visited[it -> first]){if(it -> second){it -> second = false;count++;}dfs(graph, visited, it -> first, count);}}}int minReorder(int n, vector<vector<int>>& connections) {vector<bool> visited(n, false);// 获取graph数组vector<vector<pair<int, bool>>> graph(n);for(int i = 0; i < connections.size(); i++){graph[connections[i][0]].push_back(make_pair(connections[i][1], true));graph[connections[i][1]].push_back(make_pair(connections[i][0], false));}int count = 0;dfs(graph, visited, 0, count);return count;}
};``````

### HTTPS跟HTTP有区别吗？

HTTPS和HTTP的区别&#xff0c;白话一点说就是&#xff1a; 1. 安全程度&#xff1a; - HTTP&#xff1a;就像是你和朋友面对面聊天&#xff0c;说的话大家都能听见&#xff08;信息明文传输&#xff0c;容易被偷听&#xff09;。 - HTTPS&#xff1a;就像是你们俩戴着加密耳机…

### AI 论道｜极狐GitLab 客户私享会上海站成功举办

3 月 22 日下午&#xff0c;极狐GitLab 在上海办公室举办了客户私享会&#xff0c;邀请了来自多个行业的多家客户&#xff0c;围绕 AI 提升研发效率的道法术器进行了充分交流。整个交流时长达两个多小时。 极狐GitLab 战略业务与区域发展副总裁何庆出席了此次活动并致开场辞。他…

### Day65-企业级防火墙iptables精讲1

Day65-企业级防火墙iptables精讲1 补充&#xff1a;1.什么是防火墙&#xff1f;2.防火墙种类2.1 商用防火墙介绍2.2 Linux下防火墙介绍 3.选择何种防火墙&#xff1f;4.企业级架构最佳防火墙场景5.学好iptables的技术栈基础6.Iptables是什么&#xff1f;7.Iptables企业常用场景…

### Kafka架构概述

Kafka的体系结构 Kafka是由Apache软件基金会管理的一个开源的分布式数据流处理平台。Kafka具有支持消息的发布/订阅模式、高吞吐量与低延迟、持久化、支持水平扩展、高可用性等特点。可以将Kafka应用于大数据实时处理、高性能数据管道、流分析、数据集成和关键任务应用等场景。…

### 【HTML】注册页面制作 案例二

&#xff08;大家好&#xff0c;今天我们将通过案例实战对之前学习过的HTML标签知识进行复习巩固&#xff0c;大家和我一起来吧&#xff0c;加油&#xff01;&#x1f495;&#xff09; 案例复习 通过综合案例&#xff0c;主要复习&#xff1a; 表格标签&#xff0c;可以让内容…

### 力扣Lc26--- 1108. IP 地址无效化(java版）-2024年4月02日

1.题目描述 2.知识点 注1&#xff1a;首先&#xff0c;在Java中&#xff0c;字符类型应该使用单引号’&#xff0c;而不是双引号"。其次&#xff0c;修改字符数组中的元素应该使用单引号。 注2&#xff1a;String类的replace方法用于在字符串中替换指定的字符或字符序列。…

### 158 Linux C++ 通讯架构实战13，epoll 原理和函数介绍,epoll_create,epoll_ctl ,epoll_wait

epoll技术简介 //&#xff08;2.1&#xff09;epoll概述 //(1)I/O多路复用&#xff1a;epoll就是一种典型的I/O多路复用技术:epoll技术的最大特点是支持高并发&#xff1b; //传统多路复用技术select,poll&#xff0c;在并发量达到1000-2000&#xff0c;性能就会明显下…