Đồ thị
Bridge and Articulation Point Detection
ID: #380
Xem trên trang chủ
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
ID: #56
Xem trên trang chủ
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
ID: #379
Xem trên trang chủ
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
ID: #55
Xem trên trang chủ
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]);
}
}
}