深度优先搜索(DFS)

Algorithm

思路：当访问一个节点的邻居的时候，立即访问邻居的邻居。当一个节点的邻居都被访问完后，回溯到有邻居没有访问的节点。

Example

class Node:
    def __init__(self, value):
        self.value = value
        self.color = 0  # 0-white 1-gray 2-black
        self.d = float('inf')
        self.f = float('inf')
        self.p = None


nodes = {n: Node(n) for n in ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']}
G = {nodes['A']: [nodes['B'], nodes['C'], nodes['D']],
     nodes['B']: [nodes['A'], nodes['E'], nodes['F']],
     nodes['C']: [nodes['A'], nodes['D'], nodes['G']],
     nodes['D']: [nodes['A'], nodes['C'], nodes['G'], nodes['H']],
     nodes['E']: [nodes['B'], nodes['F'], nodes['I']],
     nodes['F']: [nodes['B'], nodes['E'], nodes['G']],
     nodes['G']: [nodes['C'], nodes['D'], nodes['F']],
     nodes['H']: [nodes['D']],
     nodes['I']: [nodes['E']]}


def DFS_visit(graph, start, time=-1):
    # initialize: done by init Node
    time += 1
    start.d = time
    start.color = 1
    for v in graph[start]:
        if v.color == 0:
            v.color = 1
            v.p = start
            time = DFS_visit(graph, v, time)
    time += 1
    start.f = time
    start.color = 2
    return time

DFS_visit(G,nodes['I'])

for n in G.keys():
    print(f"{n.value},{n.d},{n.f}")

Application

1.回环检测（返回是否有回环）

思路：

一个树（连通有向无环图）一定包含 $V-1$ 条边

如果一个图的边少于 $V-1$ ，则不连通

如果一个图的边多于 $V-1$ ，则有环

Algorithm:

run BFS/DFS 找到所有的连通图
对每个连通图统计边的数量 $E$
如果 $E\geq V$ ，则表明有环

2.回环检测（返回回环）

tree edge, back edge, and cross edge

tree edge: BFS或DFS生成的树
back edge: 连接一个点和其ancestor（不包括parent）的边
cross edge: 连接的两个节点之间没有ancestor/descendent关系（i.e.下图中，6的ancestor为1，5，descendent为7，8，因此3和6之间没有ancestor/descendent关系）

algorithms - Difference between cross edges and forward edges in a DFT - Computer Science Stack Exchange

proposition：对于无向图，DFS中没有cross edge。

proof：考虑边 ${\rm edge}(u,v)$ ，不妨设 $u$ 比 $v$ 更早发现。如果有一条连接 $u$ 和 $v$ ，那么 $u$ 是 $v$ 的ancestor，则这条边为tree edge或back edge。

proposition，对于无向图，BFS中没有back edge。

proof：考虑边 ${\rm edge}(u,v)$ ，不妨设 $u$ 比 $v$ 更早发现。如果有一条连接 $u$ 和 $v$ ，则 $u$ 是 $v$ 的parent，这条边为tree edge。

DFS for cycle detection

在进行DFS时，如果有一条边连接当前节点 $u$ 和一些已经发现的节点（且不是父节点），denote as $v$ ，那么这条边就是back edge，此时找到cycle。由于我们知道这个cycle一定是从当前节点的ancestor开始的，因此只需要不断找parent直到找到 $v$

注：bfs也可以

3. Bridge Detection

bridge：如果删除一条边，图变得不连通了，则这条边就是bridge

算法1. 移除一条边，然后使用DFS/BFS检测图是否连通，重复 $E$ 次，复杂度 $\mathcal{O}(E^2)$

observation

back edge不是bridge：back bridge在环里
对于一个从 $u$ 到 $v$ 的tree edge，这条边是bridge的充分必要条件是：没有back edge连接 $v$ 的descendant(包括 $v$ )和 $u$ 的ancestor(包括 $u$ )。例如下图，即使去掉了 ${\rm edge}(u,v)$ ，还有一条 ${\rm edge}(u,t)$ 使图连通

flowchart TD
	a((a))---b((b))
	b --- u((u))
	u --- v((v))
	v --- s((s))
	v --- t((t))
	t --- u
	linkStyle 5 stroke:#d11a2d,stroke-width:2px;

Tarjan Algorithm

思路：找到DFS tree，对于每个 ${\rm edge}(u,v)$ ，检测是否存在“跨越” ${\rm edge}(u,v)$ 的back edge

具体而言：记录 $u.{\rm st}$ 和 $u.{\rm low}$ 。
其中 $u.{\rm st}$ 是该节点最初被访问的时刻
$u.{\rm low}$ 是以下三个值中最小的一个：

$u.{\rm st}$

$t.{\rm st}$ ，其中 ${\rm edge}(u,t)$ 是一个back edge

$v.{\rm low}$ ，其中 $v$ 是 $u$ 的child

一个tree edge是bridge当且仅当 $v.{\rm low}>u.{\rm st}$

关于为什么判断桥的语句在if中是因为if中处理的是tree edge，而else if中处理的是back edge。桥必然在tree edge中。

example

Critical Connections in a Network - LeetCode

很菜，但总之过了就行

class Node:
    def __init__(self, value: int):
        self.value = value
        self.color = 0
        self.st = float("inf")
        self.low = float("inf")
        self.p = None


class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = self.convert_to_graph(connections)
        result = []
        for u in graph.keys():
            if u.color == 0:
                self.DFS_visit(graph, u, 0, result)
        return result

    def DFS_visit(self, graph, u, t, result):
        u.color = 1
        t += 1
        u.st = t
        u.low = t
        for v in graph[u]:
            if v.color == 0:
                v.p = u
                t = self.DFS_visit(graph, v, t, result)
                u.low = min(u.low, v.low)
                if v.low > u.st:
                    result.append([u.value, v.value])
            elif v != u.p:
                u.low = min(u.low, v.st)
        u.color = 2
        return t

    def convert_to_graph(self, connections):
        node_dict = {}
        graph = {}
        for u, v in connections:
            if u not in node_dict:
                node_dict[u] = Node(u)
                graph[node_dict[u]] = []
            if v not in node_dict:
                node_dict[v] = Node(v)
                graph[node_dict[v]] = []
            graph[node_dict[u]].append(node_dict[v])
            graph[node_dict[v]].append(node_dict[u])
        return graph