面试中常用到的图算法

这篇文章将解释面试中常用的图算法 —— 关于BST,DFS,BFS等。面试中常用到的图算法基本局限在二叉树相关,以BFS或者DFS的方式对图进行遍历顺便储存相关的DP信息,以topological sort为主要的图顶点排序,还有将不同元素进行归类的union find算法。

Representations of the graph

二叉树的话很简单,一般使用如下结构表示。

1
2
3
4
5
class TreeNode():
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

普通图的话,根据题目里所给定的或者需求选用不同的表示方法。假设已经提前知道所有顶点的集合,或者比较方便能够将顶点映射到整数的情况下,推荐使用二维数组。比如顶点是26个英文字母的情况下就可以使用这种方法。

1
2
# graph[i][j] = True 意味着有从i到j的边存在
graph = [[False] * 26 for _ in range(len(26))]

不太好将顶点映射到整数的情况下,或者预先不知道所有顶点的集合而是需要遍历一遍才能构建图的情况下,选择使用HashMap,将顶点作为key。因为是一对多的结构,value所使用的结构可以为list或者set,根据需求进行选择。

如果反正是要遍历一边endpoint的话,可以选择list简明扼要。如果只需要判断有没有这个边存在,或者是需要快速添加和移除边的话,可以使用set。

1
2
3
4
5
graph = {}
for start, end in l: # l = [[1,2], [2,3], [4,5]]
lst = graph.get(start, [])
lst.append(end) # 使用list可能会重复添加边,如果不是simple graph的话
graph[start] = lst

DFS, BFS

DFS和BFS为两种遍历图的方法,为深度优先和广度优先。顾名思义,前者会先将某一条路径遍历到底,再寻找另一条路径。而后者是根据离出发点的先后顺序,先遍历完最近的那些点,再一层一层往外铺开。

一般情况下两者是可以通用的。但如果是要寻找从某一点出发的最短路径,那么BFS无论从理论上还是从实际的算法复杂度上都似乎更加合适。

DFS常用recursion和iterative两种方法。recursion的话,根据任务的要求,我们一般可以在三个地方加上自己的逻辑来解题,一为刚访问这个点的时候,二为将这个点所有的邻边都访问完的时候,三为返回和这个点相关的数值或者布尔值,通常用在dp问题里。

1
2
3
4
5
6
7
8
9
10
11
12
13
visited = set()

def dfs(node):
if node not in visited:
visited.add(node)
# 1
for end in graph[node]:
dfs(end)
# 2
# 3: return xxx

for key in graph:
dfs(key) # treat every node as start point, so that we visit the stand-alone part

iterative的话,dfs的结构更像stack,所以我们使用stack。这个方法一般用于单source的题目中。

1
2
3
4
5
6
7
8
def dfs(start, graph):
stack = []
stack.append(start)
while stack:
node = stack.pop()
if node in graph:
for end in graph[node]:
stack.append(node)

BFS则一般使用iterative的方法,和DFS不同,我们使用queue,因为先加入的(离原点近的)需要先被遍历完,再遍历远的(FIFO)。

1
2
3
4
5
6
7
8
def bfs(start, start):
queue = []
queue.append(start)
while queue:
node = queue.pop(0)
if node in graph:
for end in graph[node]:
queue.append(end)

在BST中使用DFS或者BFS的时候则简单的多,只要分别check当前node的left和right是否为None再依次遍历就行了。

Cycle Detection

如果一个图有cycle的话,那么从某个点出发,还没有访问完这个点为源点的所有边,就又会碰到这个点,故此使用DFS更为合理。这里的关键是,刚访问到这个点的时候,mark他,然后访问完所有的边之后,再unmark他。这个mark的数据结构,根据构建的简易性,访问的复杂度可以使用数组或者hashset。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def is_cycle(graph):
visited = set()
in_stack = set() # 这里的visited和inStack均适用set,比较直观

def is_cycle_util(node):
visited.add(node)
in_stack.add(node) #标记我们开始访问这个点

if node in graph:
for end in graph[node]:
if end not in visited and is_cycle_util(end):
return True
if end in visited and end in in_stack: # We encounter this node again
return True

in_stack.remove(node) # 移除,表示我们已经访问完毕
return False

for key in graph:
if is_cycle_util(key):
return True
return False

Topological Sort

拓扑排序是基于有向边图的一种排序方法,拓扑排序出来的结果表示着有向图的起点一定会排在终点之前,结果常常不唯一。故这个排序方法可能用来理清需求关系,比如理清一系列dependents的先后顺序。

拓扑排序常常有两种方法,第一种是贪心算法。从入度为0的顶点开始删边,删完之后将这个顶点放入拓扑排序的结果之中。然后在子图上重复这个步骤。这种方法同样也能检测cycle,因为正常情况下最后图里应该没有顶点也没有边了,但是cycle的情况下,最后还会有顶点在图里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def topological_sort_greedy(graph):
in_degree = {}
result = []
for vertice in graph: # we assume every vertice will be the key of the graph dict
in_degree[vertice] = len(graph[vertice])
stack = []
for key in in_degree:
if in_degree[key] == 0: stack.append(key)
while stack:
v = stack.pop()
result.append(v)
for end in graph[v]:
in_degree[end] = in_degree[end] - 1
if in_degree[end] == 0:
stack.append(end)
# cycle detection, no need if not needed
for key in in_degree:
if in_degree[key] > 0: # 如果还有未删完的边,则存在cycle
print("cycle detected.")
return result[::-1]

另外一种则是DFS,把以一个顶点为开始所有的边全部都遍历之后,再加入最后的拓扑排序中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def topological_sort_dfs(graph):
result = []
visited = set()

def dfs(node):
if node not in visited:
visited.add(node)
for end in graph[node]:
dfs(end)
result.append(node)

for v in graph:
dfs(v)

return result[::-1]

当我们使用DFS的时候,我们也可以改进算法,让他也具备有检测cycle的功能。(一般说来,面试题不会假定没有cycle,所以写出来的算法最好也要有检测cycle的功能)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 下面的代码结合了上面的topological_sort_dfs和之前的is_cycle
def sort_with_cycle_detection(graph):
result = []
visited = set()
in_stack = set()

def dfs(node):
should_append = node not in visited
visited.add(node)
in_stack.add(node)
ret = False
for end in graph[node]:
if end not in visited and dfs(end):
ret = True
if end in visited and node in in_stack:
ret = True
in_stack.remove(node)
if should_append:
result.append(node)
return ret

for key in graph:
if dfs(key):
return True # cycle detected
return False # cycle not detected, and result[::-1] is the sort result

Union Find

Union find 可以把元素分成互不相交的几个集合,比如说leetcode的第721题就是一个典型的例子。做union find的时候,首先要把每个元素进行编号(我们使用list based的方法实现union find,比tree based的方法更容易用在面试中)。最后做完union find之后,还要能够轻易的访问到每个元素以此进行归类:你可以使用hashmap,也可以直接遍历id的幅值范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
def union_find():
p = [i for i in range(100)] # 每个元素i都指向自己,此时有100个disjoint set

def find(x):
# 如果x不是当前的代表元素,一个个顺着往上找,并且全部直接更新到父元素,这叫做path compression
if p[x] != x:
p[x] = find(p[x])
return p[x]

def union(x,y):
# 把x元素的根结点指向y元素的根结点,相当于merge两个集合。
# 在更加优化的算法里,经常还需要看rank来决定把谁并到谁里面去。
p[find(x)] = find(y)