如果说BFS是找眼镜，先从自己身边最近的地方摸一圈再往外找的话，那么DFS就是走迷宫，它的本质是一个backtracking的过程：从一个路口出发，走一个可以走的路口，走到底为止，再从里往外走之前所有没有走过的路口，直到回到最初的那个路口，找下一个没走过的路径... Recursively explore the graph, backtracking as necessary.
伪代码模板
def DFS(graph, visited, s):
# recursively visit every reachable vertices from s that are still not being visited
for u in graph.neighbors(s):
if u not in visited:
visited.add(u)
DFS(graph, visited, u)
def DFS_All(graph):
visited = set()
for v in graph:
if v not in visited:
visited.add(v)
DFS(graph, visited, v)
输入：adjacency list
input n=5, edges=[[0,1],[0,2],[0,3],[1,4]]
output True
from collections import defaultdict
def has_cycle(graph, visited, parent, u):
visited.add(u)
for v in graph[u]:
if v!= parent:
if v in visited or has_cycle(graph, visited, u, v):
return True
return False
class Solution(object):
def valid_tree(self, n, edges):
visited=set()
graph = defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
return not has_cycle(graph, visited, -1, 0) and len(visited) == n
def DFS(graph, visited, s):
mark s as visiting
# recursively visit every reachable vertices from s that are still not being visited
for u in graph.neighbors(s):
if u not in visited:
visited.add(u)
DFS(graph, visited, u)
mark s as visited
调整后的代码
def dfs(directed_graph, visit_status, u):
# 0 represents we are still actively visiting or dfsing a node
# 1 represents we are done with the dfs of a node
visit_status[u]=0
for v in directed_graph[u]:
if v not in visit_status:
if dfs(directed_graph, visit_status, v):
return True
elif visit_status[v] == 0:
return True
visit_status[u]=1
return False
def has_cycle(directed_graph):
visit_status={}
for v in directed_graph:
if v not in visit_status and dfs(directed_graph, visit_status, v):
return True
return False
def can_color(graph, colors, u, color):
colors[u] = color
for v in graph[u]:
if color[v] == color:
return False #我的邻居已经染了色且和我一样
elif not color[v] and not can_color(graph, colors, v, -color):
return False #我的邻居还没有染色，但是我的邻居发现给他染完色之后和自己的邻居冲突
return True
class Solution(object):
def isBarpartite(self, graph):
colors = [0]*len(graph) #一开始都没有染色/not_visited
for v in xrange(len(graph)):
if not colors[v] and not can_color(graph, colors, v, 1): #not_visited而且染不了色
return False
return True
对于DFS来说，一个有向图的边{u,v}, v执行完之后才会执行u。所以只要在DFS的时候创建一个list存放走过的node的结果集，然后在输出时reverse the order就是我们想要的正确的dependency。但是这里其实只会返回任意一个可以满足dependency的排序。如果想要在结果集里生成所有的可能，就要在外面包一层backtracking，检查is_compatible。
输入：2，[[1,0]] 意思是2门课，要先上完0才能上1 所以output [0,1]
输入：4，[[1,0],[2,0],[3,1],[3,2]] output [0,1,2,3] or [0,2,1,3]
from collections import defaultdict
class Solution(object):
def findOrder(self, numCourses, prerequisites):
graph = defaultdict(list)
for p in prerequisites:
graph[p[1]].append(p[0])
courses = []
visited = [-1]*numCourses
def dfs(u):
visited[u] = 0
for v in graph[u]:
if visited[v]==0:
return False
elif visited[v]==-1 and not dfs(v):
return False
visited[u]=1
courses.append(u)
return True
for u in xrange(numCourses):
if visited[u] == -1 and not dfs(u):
return []
return courses
Graph的总结
Meta Template
def whatever_search_first(graph, s):
put s in the bag
mark s
while bag still contain nodes:
take node from bag
for neighbor in graph.neighbors(node):
if neighbor is not visited:
mark neighbor
put neighbor in bag
如果bag是stack：depth first search；是queue：breadth first search；priority queue：best first search。
