Mô phỏng thuật toán Tìm đỉnh khớp

Articulation Points · Nhóm: Đồ thị

Tìm đỉnh khớp (Articulation Points), nhóm Đồ thị.

Mã Python

def find_articulation(adj):
    tin = low = [0]*n;  visited = [False]*n
    timer = 0;  ap = set()
    def dfs(u, parent):
        nonlocal timer
        visited[u] = True;  tin[u] = low[u] = timer; timer += 1
        children = 0
        for v in adj[u]:
            if v == parent:  continue
            if visited[v]:
                low[u] = min(low[u], tin[v])
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= tin[u]:
                    ap.add(u)
                children += 1
        if parent == -1 and children > 1:
            ap.add(u)
    dfs(0, -1)

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.