图论之 DFS

文章目录

1971.寻找图中是否存在路径
797.所有可能的路径
841.钥匙和房间

DFS的遍历的模版大差不差，主要是区别题目中的图是否是有环的？题目求解的是可达问题，路径数量问题

开始的时候，如果题目中的边的记录没有转化为邻接表的形式，那么就需要我们自己进行转化

  # 使用邻接表存储图adj = [[] for _ in range(n)]for u, v in edges:adj[u].append(v)adj[v].append(u)

总体的遍历的模版

  # DFS 函数def dfs(i):if 终止条件return True# 如果需要标记，visited[i] = True  # 标记当前节点为已访问# 访问当前节点的邻居节点for neighbor in adj[i]:# 具体的操作# 返回return

几类问题

如果存在环的情况，一般要设置visited，不然会重复访问，当然，如果是有向无环图，就不用设置visited
当你要记录一个节点是否被访问的时候，你就要设置这个visited
visited标记的更新的问题

def dfs(i):# 一般更新在外边visited[i] = True

如何判断是否有环的问题？你可以记录当前节点的parent,当遇到一个新的已经访问的节点，并且该节点还不是父节点(感觉n>2才行)

1971.寻找图中是否存在路径

在这里插入图片描述

思路分析：该题使用传统的DFS可以完成，当然使用并查集也可以完成.下面介绍使用dfs的做法

使用dfs，首先为了方便起见，我们使用邻接表记录图中边的情况，注意使用的是邻接表，同时，我们应该开一个数组visited[i]用来记录节点i是否被访问过。递归的截止的条件是 i == destination,否则，我们首先将当前访问的节点标记为True,接着，我们访问i的邻居节点neighbor,如果邻居节点还没有被访问，我们就可以递归访问，当有一个节点返回True,我们就返回True,当访问完全部的节点都没有返回True,我们就返回True

from typing import Listclass Solution:def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:# 使用邻接表存储图adj = [[] for _ in range(n)]for u, v in edges:adj[u].append(v)adj[v].append(u)# 记录访问过的节点visited = [False] * n# DFS 函数def dfs(i):if i == destination:return Truevisited[i] = True  # 标记当前节点为已访问for neighbor in adj[i]:if not visited[neighbor]:if dfs(neighbor):return Truereturn False  # 所有路径都尝试过，未找到目标节点return dfs(source)

797.所有可能的路径

在这里插入图片描述

思路分析：求解的是方案数，我们需要传递两个参数，当前访问到的节点i和当前的路径存储path,注意，每次应该先把当前的节点加入path,然后进行判断是否到达n-1,如果没有，就访问邻居节点，否则就把path加入ans答案中，访问完邻居之后，就path.pop()弹出节点i

class Solution:def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:ans = []  # 存储所有路径n = len(graph)def dfs(i, path):# 将当前节点加入路径path.append(i)# 如果当前节点是目标节点，将路径加入结果if i == n - 1:ans.append(path.copy())  # 注意：这里需要传递 path 的副本# 遍历所有邻居节点for neighbor in graph[i]:dfs(neighbor, path)  # 递归调用# 回溯：移除当前节点path.pop()dfs(0, [])  # 从节点 0 开始 DFSreturn ans

841.钥匙和房间

在这里插入图片描述

思路分析：我们只要使用这个dfs进行遍历即可，通过判断访问的房间数是否等于n或者是否访问过全部的房间

class Solution:def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:n = len(rooms)visited = [False] * n  # 记录房间是否被访问过def dfs(i):nonlocal num  # 使用 nonlocal 关键字修改外部变量visited[i] = True  # 标记当前房间为已访问num += 1  # 更新已访问的房间数量for neigh in rooms[i]:  # 访问邻居if not visited[neigh]:dfs(neigh)  # 递归访问未访问的房间num = 0  # 记录已访问的房间数量dfs(0)  # 从房间 0 开始访问return num == n  # 检查是否所有房间都被访问过