Last Updated: 2024-05-08 07:56:44 Wednesday
-- TOC --
深度优先搜索，DFS，其实现一般采用递归，其实本质上DFS就是个回溯算法。
下面是一个DFS在无向图上的递归参考实现：
G = {
'a': ('b','h'),
'b': ('a','h','c'),
'c': ('b','i','f','d'),
'd': ('c','f','e'),
'e': ('d','f'),
'f': ('g','c','d','e'),
'g': ('i','f'),
'h': ('a','b','i'),
'i': ('h','c','g'),
}
def DFS(G, s):
""" Depth-First Search """
assert s in G
ordered = []
def __dfs(v):
ordered.append(v)
for nb in G[v]:
if nb not in ordered:
__dfs(nb)
__dfs(s)
return ordered
print("DFS:")
print(DFS(G,'a'))
print(DFS(G,'b'))
print(DFS(G,'f'))
复杂度：\(\Theta(V+E)\)
教授说：DFS比BFS更有价值，好多算法都基于DFS！
Pseuducode for DFS:
DFS(v):
mark v as visited
for each w in adjacency(v):
if w is not visited:
DFS(w)
通过DFS算法生成的Tree的过程，对Edge有一个分类。《CLRS》里面是这么说的：
Tree edges are edges in the depth-first forest. Edge (u,v) is a tree edge if v was first discovered by exploring edge (u,v).Back edges are those edges (u,v) connecting a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges.Forward edges are those non-tree edges (u,v) connecting a vertex u to a proper descendant v in a depth-first tree.Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.下面的pseudocode演示如何识别这4种不同的Edge：
visit_num = 0
color all vertice as white
DFS(v):
color(v) = gray # v is visited
visit_num += 1
dfsn(v) = visit_num # dfs visit number
For each w in adjacent(v):
if color(w) == white: # w is not visited
mark (v,w) as Tree Edge
DFS(v)
else:
if color(w) == gray:
mark (v,w) as Back Edge
continue
# assert color(w) == black
if dfsn(v) < dfsn(w):
mark (v,w) as Forward Edge
elif dfsn(v) > dfsn(w):
mark (v,w) as Cross Edge
color(v) = black
Directed Graph
如果是有向图，BFS和DFS算法保持不变，只是不同的起始点，可能会导致部分节点访问不到。下面是一个用于测试的有向图对应的数据：
G = {
'a': ('b','h'),
'b': ('h','c'),
'c': ('f','d'),
'd': ('f'),
'e': ('d'),
'f': ('e'),
'g': ('f'),
'h': ('i'),
'i': ('c','g'),
}
通过DFS算法，可以得到Graph的拓扑顺序。使用上面Directed数据，参考实现如下：
def DFS(G, s):
""" Depth-First Search """
assert s in G
tpsort = []
visited = []
def __dfs(v):
visited.append(v)
for nb in G[v]:
if nb not in visited:
__dfs(nb)
tpsort.insert(0,v) #!!
__dfs(s)
return tpsort
print("Topological Sort:")
print('start a',DFS(G,'a'))
print('start i',DFS(G,'i'))
print('start f',DFS(G,'f'))
输出：
Topological Sort:
start a ['a', 'b', 'h', 'i', 'g', 'c', 'f', 'e', 'd']
start i ['i', 'g', 'c', 'f', 'e', 'd']
start f ['f', 'e', 'd']
复杂度：\(\Theta(V+E)\)
用pseudocode换个角度，再描述一次topological sort算法：
Topological_Sort(G):
run DFS on G to determine finish time of each vertex
Sort finish time in descending order
最长路径
DAG can be topologically sorted. 如果按其倒序的方式遍历节点，可以实现快速的计算最长路径的算法，这也是个DP算法。
跑两遍DFS，在第1遍时，记录下每个vertex的finish time。然后创建\(G^T\)，即将所有Edge的方向反转，然后第2遍DFS，此时在调用DFS(v)时，按照finish time递减的顺序进行。按照finish time递减的顺序很关键，这实际上就是要按照第1遍DFS时形成的topological sort的顺序进行第2遍DFS。此时，第2遍DFS生成的每棵树，都是一个SCC。Edge反转后，通过反转前的topological sort还能访问的vertex，一定存在双向Edge。
Tarjan算法
An undirected graph G is biconnected if the removal of any one vertex leaves the graph still connected.
If the graph is not biconnected then there exists at least one vertex whose removal would disconnect the graph. Such a vertex is called articulation vertex.
下面是基于DFS寻找articulation vertex的算法：
visit_num = 0
DFS_Articulation_Vertex(v):
mark v as visited
++visit_num
dfsn(v) = visit_num
lowpt(v) = dfsn(v)
For each w in adjacency(v):
if w is not visited:
DFS_Articualtion_Vertex(w)
if lowpt(w) >= dfsn(v):
v is articulation vertex!!
else:
lowpt(v) = min(lowpt(v),lowpt(w))
else:
lowpt(v) = min(lowpt(v), dfsn(w))
lowpt(v): lowest visit number vertex v can reach by a sequence of 0 or more tree edges and at most one back edge.
本文链接：https://cs.pynote.net/ag/graph/202404212/
-- EOF --
-- MORE --