Mô phỏng thuật toán Tìm cầu

Finding Bridges · Nhóm: Đồ thị

Tìm cầu (Finding Bridges), nhóm Đồ thị.

Mã Python

def find_bridges(adj):
    tin = [-1]*n; low = [-1]*n; timer = 0
    def dfs(u, parent):
        nonlocal timer
        tin[u] = low[u] = timer; timer += 1
        for v in adj[u]:
            if v == parent:
                continue
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    bridges.append((u, v))
    for s in range(n):
        if tin[s] == -1: dfs(s, -1)

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