Đồ thị

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 4)

Đồ thị

Bridge and Articulation Point Detection

Thời gian (Time) O(V + E)
Không gian (Space) O(V)

Mô tả nguyên lý

Tìm các cạnh cầu và đỉnh khớp trong đồ thị vô hướng bằng cây DFS.

Cài đặt mẫu (Implementation)

// Kiểm tra điều kiện $low[v] > disc[u]$ cho cạnh cầu và $low[v] \ge disc[u]$ cho đỉnh khớp.
Đồ thị

Bridge and Articulation Point Finding

Thời gian (Time) O(V + E)
Không gian (Space) O(V)

Mô tả nguyên lý

Tìm các cạnh cầu và đỉnh khớp trong đồ thị vô hướng bằng DFS.

Cài đặt mẫu (Implementation)

// Dựa vào mảng discovery time và low time trong cây DFS.
Đồ thị

Kosaraju Strongly Connected Components

Thời gian (Time) O(V + E)
Không gian (Space) O(V)

Mô tả nguyên lý

Tìm thành phần liên thông mạnh bằng 2 lần duyệt DFS trên đồ thị gốc và đồ thị chuyển vị.

Cài đặt mẫu (Implementation)

// Sắp xếp thứ tự hoàn thành DFS ở lần 1 và duyệt theo thứ tự giảm dần ở lần 2.
Đồ thị

Tarjan Strongly Connected Components

Thời gian (Time) O(V + E)
Không gian (Space) O(V)

Mô tả nguyên lý

Tìm các thành phần liên thông mạnh trong đồ thị có hướng chỉ với một lần duyệt DFS.

Cài đặt mẫu (Implementation)

function tarjan($u, &$disc, &$low, &$st, &$inStack, $adj, &$time) {
    $disc[$u] = $low[$u] = ++$time;
    $st[] = $u; $inStack[$u] = true;
    foreach ($adj[$u] as $v) {
        if ($disc[$v] == -1) {
            tarjan($v, $disc, $low, $st, $inStack, $adj, $time);
            $low[$u] = min($low[$u], $low[$v]);
        } elseif ($inStack[$v]) {
            $low[$u] = min($low[$u], $disc[$v]);
        }
    }
}