Python中使用DFS和Tarjan算法判断图(Graph)是否有割点(Articulation Point)

def dfs(vertex, visited, low_time, dfn_time, parent, is_articulation):
    visited.add(vertex)
    dfn_time[vertex] = low_time[vertex] = dfs.time  # 前向星时间戳
    dfs.time += 1
    child_num = 0  # 子节点数量

    for w in graph[vertex]:
        if w not in visited:
            child_num += 1
            parent[w] = vertex
            dfs(w, visited, low_time, dfn_time, parent, is_articulation)
            low_time[vertex] = min(low_time[vertex], low_time[w])
            if parent[vertex] == -1 and child_num > 1:
                is_articulation[vertex] = True
            elif parent[vertex] != -1 and dfn_time[vertex] <= low_time[w]:
                is_articulation[vertex] = True
        elif w != parent[vertex]:
            low_time[vertex] = min(low_time[vertex], dfn_time[w])


def find_articulation_points():
    visited = set()  # 已经访问过的节点
    low_time = [-1] * n  # 各节点最早能访问到的时间戳
    dfn_time = [-1] * n  # 最早遍历到各节点的时间戳
    parent = [-1] * n  # 各节点的父节点
    is_articulation = [False] * n  # 是否为割点
    dfs.time = 0

    for i in range(n):
        if i not in visited:
            dfs(i, visited, low_time, dfn_time, parent, is_articulation)

    for i in range(n):
        if is_articulation[i]:
            print("Node", i, "is an articulation point.")


n = 8
graph = [[1, 2, 3], [0, 2], [0, 1], [0, 4], [3, 5], [4, 6, 7], [5], [5]]
find_articulation_points()

def tarjan(vertex, visited, low_time, dfn_time, parent, is_articulation):
    visited.add(vertex)
    low_time[vertex] = dfn_time[vertex] = tarjan.time  # 时间戳
    tarjan.stack.append(vertex)

    for w in graph[vertex]:
        if w not in visited:
            parent[w] = vertex
            tarjan(w, visited, low_time, dfn_time, parent, is_articulation)
            low_time[vertex] = min(low_time[vertex], low_time[w])
            if dfn_time[vertex] <= low_time[w]:
                is_articulation[vertex] = True
                while tarjan.stack[-1] != w:
                    u = tarjan.stack.pop()
                    is_articulation[u] = True
                tarjan.stack.pop()
        elif w != parent[vertex]:
            low_time[vertex] = min(low_time[vertex], dfn_time[w])

    if low_time[vertex] == dfn_time[vertex]:
        while len(tarjan.stack) != 0 and tarjan.stack[-1] != vertex:
            u = tarjan.stack.pop()
            print(u)
        u = tarjan.stack.pop()
        print(u)


def find_articulation_points():
    visited = set()  # 已经访问过的节点
    low_time = [-1] * n  # 各节点最早能访问到的时间戳
    dfn_time = [-1] * n  # 最早遍历到各节点的时间戳
    parent = [-1] * n  # 各节点的父节点
    is_articulation = [False] * n  # 是否为割点
    tarjan.time = 0
    tarjan.stack = []

    for i in range(n):
        if i not in visited:
            tarjan(i, visited, low_time, dfn_time, parent, is_articulation)

    for i in range(n):
        if is_articulation[i]:
            print("Node", i, "is an articulation point.")


n = 8
graph = [[1, 2, 3], [0, 2], [0, 1], [0, 4], [3, 5], [4, 6, 7], [5], [5]]
find_articulation_points()