当图是有向的时候要使用dfs,这些是图的特性,应该在一开始有图做题的时候就应该有所判断:
下面是1559. 二维网格图中探测环 无向图dfs的范例:
sys.setrecursionlimit(999999999)
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
direction = [(-1,0),(1,0),(0,-1),(0,1)]
N,M = len(grid),len(grid[0])
explored=set()
def dfs(node,pre):
if node in explored:
return True
explored.add(node)
for d in direction:
x,y = node[0]+d[0],node[1]+d[1]
if x<0 or x>=N or y<0 or y>=M or grid[x][y]!=grid[node[0]][node[1]] or (x,y)==pre:
continue
if dfs((x,y),node):
return True
return False
for i in range(N):
for j in range(M):
if (i,j) not in explored and dfs((i,j),None):
return True
return False
一般情况下由于dfs 的时间复杂度为(b^d),效率会比较低,一般会加上剪枝的思考结果会比较理想。
解释
那么有向图又是怎么做的呢?
其实这种情况下一般我更推荐拓扑排序,但是实际使用起来,笔试的时候dfs会更容易想到。
经典的题目是leetcode 207课程表:
1是拓扑排序:即贪婪加bfs的解法:
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
#课程的长度
clen = len(prerequisites)
if clen ==0:
return True
in_degrees = [0 for _ in range(numCourses)]
adj = [set() for _ in range(numCourses)]
for second , first in prerequisites:
in_degrees[second]+=1
adj[first].add(second)
#print('in_degrees',in_degrees)
#首先先遍历一遍
res=[]
queue=[]
for i in range(numCourses):
if in_degrees[i]==0:
queue.append(i)
counter =0
#queue里面存的都是已经没有前置课的文章
while queue:
top= queue.pop(0)
counter+=1
for successor in adj[top]:
in_degrees[successor]-=1
if in_degrees[successor] == 0:
queue.append(successor)
return counter==numCourses
dfs容易超时,这里建议使用flag标记已经遍历过的点或者用cache存一下结果:
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 0 表示没有访问过(白)
# 1 表示访问过了(黑)
visited = [0] * numCourses
adjacency = [[] for _ in range(numCourses)]
@functools.lru_cache(None)
def dfs(i):
if visited[i] == 1:
return False
# if visited[i]==-1:
# return True
visited[i] = 1
for j in adjacency[i]:
if not dfs(j):
return False
visited[i] = 0
return True
for cur, pre in prerequisites:
adjacency[cur].append(pre)
for i in range(numCourses):
if not dfs(i):
return False
return True
大部分问题下dfs会比较直观