Mô phỏng thuật toán Thành phần liên thông mạnh

Strongly Connected Components · Nhóm: Đồ thị

Thành phần liên thông mạnh (Strongly Connected Components), nhóm Đồ thị.

Mã Python

def kosaraju(adj, radj, n):
    visited = [False] * n
    order = []
    def dfs1(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)
    for s in range(n):
        if not visited[s]:
            dfs1(s)
    comp = [-1] * n
    def dfs2(u, c):
        comp[u] = c
        for v in radj[u]:
            if comp[v] == -1:
                dfs2(v, c)
    c = 0
    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, c)
            c += 1
    return comp

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