任务
797. 所有可能的路径
给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。
思路
题目所给的图的表示是邻接表,题意就是找到从i到n的所有路径,这里使用dfs。参考之前的回溯章节,区别是当时的各种情况的出发根节点可以认为是虚拟节点,在循环和递归中处理各种情况,而现在的出发节点是实际的图的点,需要提前加入到path中来保证正确。
class Solution:
def __init__(self):
self.result = []
self.path = []
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
self.path.append(0)
self.dfs(graph,0,len(graph)-1)
return self.result
def dfs(self,graph,x,n): # 从x出发到n
if x == n:
self.result.append(self.path[:])
return
for i in graph[x]:
self.path.append(i)
self.dfs(graph,i,n)
self.path.pop()
下面给出输入为 邻接矩阵的算法
class Solution:
def __init__(self):
self.result = []
self.path = []
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
self.path.append(0)
self.dfs(graph,0,len(graph)-1)
return self.result
def dfs(self,graph,x,n): # 从x出发到n
if x == n:
self.result.append(self.path[:])
return
for i in graph[x][i]:
if graph[x][i] == 1:
self.path.append(i)
self.dfs(graph,i,n)
self.path.pop()
深度有限搜索(dfs)和广度优先搜索(bfs) 简析
可以认为树中的 先中后序遍历为dfs的特例,层序遍历为bfs的特例。
dfs适合的问题:
- 路径查找:在一些问题中,我们需要找到从起点到终点的一条路径(或所有路径)。DFS 很适合这种问题,因为它可以递归地探索每一条可能的路径,直到找到目标为止。
- 连通性问题:DFS 可以用于判断图是否连通,即图中是否存在一条从一个节点到另一个节点的路径。
- 拓扑排序:在处理有向无环图(DAG)时,DFS 可以用于生成拓扑排序
- 回溯算法:之前的回溯算法章节的问题都可以认为是dfs解决的问题
bfs适合的问题
- 最短路径问题:BFS 是在无权图中寻找两点之间最短路径的最优算法。因为 BFS 按层次遍历,所以首次到达目标节点时,一定是通过最短路径到达的。
- 层次遍历:BFS 按层次逐层遍历图或树结构,非常适合需要按照距离或层次关系处理的场景。
- 最小生成树(MST):在一些图算法中,BFS 可以用来生成最小生成树(虽然更常用的是 Prim 或 Kruskal 算法)。
bfs的参考代码
from collections import deque
# 表示四个方向
dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]
def bfs(grid, visited, x, y):
# 定义队列
que = deque()
# 起始节点加入队列
que.append((x, y))
# 只要加入队列,立刻标记为访问过的节点
visited[x][y] = True
while que:
# 从队列取元素
curx, cury = que.popleft() # 当前节点坐标
# 开始向当前节点的四个方向左右上下去遍历
for i in range(4):
nextx = curx + dir[i][0]
nexty = cury + dir[i][1] # 获取周边四个方向的坐标
# 坐标越界了,直接跳过
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
continue
# 如果节点没被访问过
if not visited[nextx][nexty]:
# 队列添加该节点为下一轮要遍历的节点
que.append((nextx, nexty))
# 只要加入队列立刻标记,避免重复访问
visited[nextx][nexty] = True
标签:图论,graph,self,dfs,Part1,第十一章,path,节点,append
From: https://www.cnblogs.com/haohaoscnblogs/p/18396266