在Python中找出图形中的关键边和虚关键边的程序

简介

在图论中，关键边是指在一张无向连通图中，如果去掉这条边，整张图就不连通了；而虚关键边则是指在一张无向连通图中，去掉这条边后，整张图会变成有多个连通块，但是这条边恰好连接了两个不同的连通块。本文介绍如何在 Python 中实现找出关键边和虚关键边的程序。

算法思路

找关键边和虚关键边的算法，可以用 Tarjan 算法来实现。Tarjan 算法通过 DFS 遍历图实现，分别通过 low 和 dfn 数组来保存每个节点的遍历次序和最小可回溯到的次序，其中 dfn 数组可看作该节点的出现时间戳，low 数组可看作该节点可回溯到的最早时间戳。根据这两个数组可以确定每条边是关键边还是虚关键边。

具体说明如下：

对于当前遍历到的节点 u，先将 dfn[u] 和 low[u] 初始化为当前遍历次序；并将 u 标记为已遍历。
遍历 u 的所有邻居节点 v，如果 v 未被遍历，则递归遍历 v。在遍历过程中，如果遍历到的不是 u 的父节点，则说明存在可回溯的路径，需要更新 low[u] 的值，即 low[u] = min(low[u], low[v])。
如果遍历到的 v 已经被遍历，且 v 是 u 的父节点，则不需要更新 low[u] 的值。
针对每条边 (u,v)，如果 dfn[u] < low[v]，则说明该边是一个关键边；如果 dfn[u] low[v] 且该边不是 u 的父节点，则说明该边是一个虚关键边。因为在 u 节点向下搜索过程中，如果 v 节点存在除 u 节点的子树以外的路径可以回溯到比 u 更早的节点，则 dfn[u] < low[v]；如果 v 节点在 u 节点的子树内且能够到达比 u 更早的节点，则 dfn[u] low[v]，但该边不是关键边，因为可以找到别的路径到达该节点。

示例代码

下面是用 Python 实现 Tarjan 算法找出关键边和虚关键边的示例代码：

def tarjan(u, father):
    global timestamp
    dfn[u], low[u] = timestamp, timestamp
    timestamp += 1
    visited[u] = True
    for v in graph[u]:
        if not visited[v]:
            tarjan(v, u)
            low[u] = min(low[u], low[v])
            if dfn[u] < low[v]:
                print(f'{u} - {v} is a critical edge')
            elif dfn[u] == low[v] and v != father:
                print(f'{u} - {v} is a pseudo critical edge')
        elif v != father:
            low[u] = min(low[u], dfn[v])

# 假设 graph 是待遍历的无向连通图，节点从 1 到 n 编号。
n = len(graph)
dfn, low = [0] * (n + 1), [0] * (n + 1)
visited = [False] * (n + 1)
timestamp = 1
tarjan(1, 0)  # 从节点 1 开始遍历

在上述代码中，graph 表示待遍历的图，每个节点的邻居节点都以列表形式储存。dfn、low、visited 分别是遍历节点的时间戳、最小可回溯的时间戳和遍历记录数组。timestamp 记录当前的遍历次序。在 tarjan 函数中，先将节点 u 的 dfn 和 low 值都设置为当前遍历次序，然后递归遍历节点 u 的每个邻居节点 v。如果 v 尚未被访问，则继续递归遍历 v，否则需要根据 dfn 和 low 数组更新 low[u] 的值。在更新 low[u] 的同时，如果 dfn[u] < low[v]，则此边为关键边，如果 dfn[u] low[v]，则要判断该边是否为虚关键边。