数据结构与算法：图论——深度优先搜索dfs

发布于：2025-06-28 ⋅ 阅读:(10) ⋅ 点赞:(0)

深度优先搜索dfs

提到深度优先搜索（dfs），就不得不说和广度优先搜索（bfs）有什么区别

根据搜索方式的不同，可以将图的遍历分为「深度优先搜索」和「广度优先搜索」。

  • 深度优先搜索：从某一顶点出发，沿着⼀条路径⼀直搜索下去，在⽆法搜索时，回退到刚刚访问过的节点。
  • 广度优先搜索：从某个顶点出发，⼀次性访问所有未被访问的邻接点，再依次从这些已访问过的邻接点出发，⼀层⼀层地访问。

基础与模板：

不断深入，更新标记

下图来自：AlgoNote/docs/06_graph/06_03_graph_dfs.md at main · itcharge/AlgoNote · GitHub

image-20250624101309420

两种两种深度优先搜索的实现方式

  • 递归实现
  • 基于堆栈实现

首先介绍递归实现。与算法本身非常的和谐，和二叉树的遍历的两种方式很像，实现方法也类似，只不过图的储存方式跟二叉树不同而已。

image-20250624110932548

基于堆栈实现：深度优先搜索是使用stack比较合适

image-20250624114822458

题目1、797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出从节点 0 到节点 n-1 的所有路径并输出（不要求按特定顺序）

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

示例 1：

img

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

img

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

提示：

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i（即不存在自环）
  • graph[i] 中的所有元素 互不相同
  • 保证输入为 有向无环图（DAG）

这个题目使用深度优先搜索，用stack实现感觉代码量比较多一些。这里使用递归实现比较好理解，而且代码量比较少，需要考虑的细节也比较多。需要改变DFS的递归条件

找出从节点 0 到节点 n-1 的所有路径并输出，所以递归的时候碰见n-1就把这一组加入结果

image-20250624164453567

class Solution {
public:
	vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
		vector<vector<int>> res;
		vector<int> singleVec{0};   // 这里开头0先加到中间vec里面
		int num = graph.size();
		function<void(vector<int>&)> dfs = [&](vector<int>& vec){
			if(singleVec.back() == num-1){	// 中间vec最后一个值判断条件
				res.push_back(singleVec);
				return;
			}
			for(auto a:vec){
				singleVec.push_back(a);
				dfs(graph[a]);
				singleVec.pop_back();// 这里singleVec在外面有push就需要pop
			}
		};
		dfs(graph[0]);
		return res;
	}
};

题目2、200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

经典题目：往上下左右四个方向DFS，先遍历，碰到1就开开始DFS把周围的1都变成0

image-20250624174938394

	int dir[4][2]={0,1,1,0,0,-1,-1,0}; // 上下左右
	void makezero(vector<vector<char>>& grid,int x,int y){
		grid[x][y] = '0';    	// 碰见1以后上下左右都置零
		for(int i = 0;i<4;i++){
			int nx = x+dir[i][0];
			int ny = y+dir[i][1];
			if(nx<0||ny<0||nx>=grid.size()||ny>=grid[0].size()) continue;
			if(grid[nx][ny]=='1'){
				makezero(grid,nx,ny);
			}
		}
	}
	int numIslands(vector<vector<char>>& grid) {
		int row = grid.size();
		int col = grid[0].size();
		int res = 0;
		for(int i = 0 ;i<row;i++){
			for(int j =0;j<col;j++ ){
				if(grid[i][j] == '1' ){ //碰见1之后，周围置零
					makezero(grid,i,j);
					res++;
				}
			}
		}
		return res;
	}

题目3、695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

img 
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 为 0 或 1

这个题目只是在外面加一个参数count，遍历数组，得到count的最大值

image-20250624181738358

题目4、133. 克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

image-20250624201046963 
class Solution {
public:
    vector<int> flags  = vector<int>(101,1);
    unordered_map<Node*,Node*>mp;
}
这里的flags  为什么不能 vector<int> flags(101,1);

在 C++ 类的定义里，成员变量的初始化要遵循特定的语法规则。当你在类中声明非静态成员变量时，像下面这样直接初始化是不被允许的：

vector<int> flags(101,1); // 错误的类内初始化方式

这是因为这种圆括号初始化的形式，会被编译器理解成函数声明。也就是说，编译器会把它误认为是一个名为flags，返回类型为vector，并且带有两个参数（一个int类型和一个int类型）的函数。

而使用等号加花括号或者直接用花括号的初始化方式，就不会产生歧义，所以是合法的类内初始化形式：

vector<int> flags = vector<int>(101,1); // 正确，使用等号初始化
vector<int> flags{101,1}; // 正确，使用花括号列表初始化（但这种方式是创建包含两个元素101和1的vector）
vector<int> flags = {101,1}; // 正确，等价于上面的花括号形式

在你的代码中：

vector<int> flags  = vector<int>(101,1);

这是正确的类内初始化写法。它借助拷贝初始化，先构造出一个临时的vector对象，然后再把这个临时对象拷贝给成员变量flags。

总结一下，类内初始化要避开圆括号语法，防止和函数声明混淆。建议优先采用花括号初始化或者等号初始化的方式。

这个题目，主要是

  • 首先，dfs时要确定好终止条件，当新节点创立好了之后就不用创立了，返回这个新节点即可
  • 怎么找到创立好的新节点呢，通过哈希表建立起新旧节点的关系，通过旧节点找到新节点
class Node {
public:
	int val;
	vector<Node*> neighbors;
	Node() {
		val = 0;
		neighbors = vector<Node*>();
	}
	Node(int _val) {
		val = _val;
		neighbors = vector<Node*>();
	}
	Node(int _val, vector<Node*> _neighbors) {
		val = _val;
		neighbors = _neighbors;
	}
};
class Solution {
public:
	// 这里为了判断这个节点有没有被创建
	vector<int> flags  = vector<int>(101,1); 
	// 这个建立原始图节点和新建节点之间映射
	// 当neighbors中有已经创建的节点之后
	// 通过这个哈希表就可以找到新建的对应节点
	unordered_map<Node*,Node*>mp;
	Node* cloneGraph(Node* node) {
		if(!node) return nullptr;
		
		if(flags[node->val] == 0) 
			return mp[node];// 节点已创建，返回新节点
		
		Node* res = new Node(node->val);// 新建节点
		mp[node] = res;		  // 建立新旧节点哈希表
		flags[node->val] = 0; // 表示新节点已经创建
		
		for(auto a:node->neighbors){
			res->neighbors.push_back(cloneGraph(a));
		}					// 新节点neighbors
		return res;
	}
};

上面是个人写的代码，让deepseek优化之后发现，这个创建标识符flags可以省略，通过哈希表就可以完成这个是否创建的判断

class Solution {
public:
    unordered_map<Node*, Node*> visited; // 存储原节点到克隆节点的映射
    
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (visited.find(node) != visited.end()) 
            return visited[node]; // 已克隆则直接返回
        
        Node* cloneNode = new Node(node->val); // 创建新节点
        visited[node] = cloneNode; // 建立映射关系
        
        for (Node* neighbor : node->neighbors) {
            cloneNode->neighbors.push_back(cloneGraph(neighbor)); // 递归克隆邻居
        }
        return cloneNode;
    }
};

题目5、841. 钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

image-20250624204447096

这里就是dfs的模板题。把图从开头遍历，设置flags，表示遍历到这个节点，，否则返回false

image-20250624213220582

class Solution {
public:
	bool canVisitAllRooms(vector<vector<int>>& rooms) {
		vector<int> flags(rooms.size(),1); // 标准位，1表示未遍历到
		flags[0] = 0;					   // 0已经遍历到，0有钥匙
		function<void(vector<int>&)>dfs = [&](vector<int>& vec){
			for(auto a:vec){
				if(flags[a]){		
					flags[a] = 0;		// 遍历到置零
					dfs(rooms[a]);		// 继续遍历到下一个vec
				}
			}
		};
		dfs(rooms[0]);
		for(auto b:flags){		// 如果这个flags全部被遍历到之后，返回ture
			if(b == 1) return false;
		}
		return true;
	}
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布