图论 之 DFS

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

  

• 开始的时间，假如标题中的边的记载没有转化为毗邻表的情势，那么就必要我们自己举行转化
  

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

复制代码

  

• 总体的遍历的模版
  

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

复制代码

几类题目

  

• 假如存在环的情况，一样寻常要设置visited，否则会重复访问，固然，假如是有向无环图，就不消设置visited  
  
• 当你要记载一个节点是否被访问的时间，你就要设置这个visited  
  
• visited标志的更新的题目
  

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

复制代码

  

• 怎样判断是否有环的题目？你可以记载当前节点的parent,当碰到一个新的已经访问的节点，而且该节点还不是父节点(感觉n>2才行)
  

1971.探求图中是否存在路径