Đồ thị (Graph)

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

Đồ thị (Graph)

Bellman-Ford Algorithm

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

Mô tả nguyên lý

Tìm đường đi ngắn nhất từ nguồn đơn, hỗ trợ trọng số cạnh âm và phát hiện chu trình âm.

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

// Lặp qua tất cả các cạnh V-1 lần để cập nhật khoảng cách tối ưu cho từng đỉnh.
Đồ thị (Graph)

Breadth-First Search (BFS)

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

Mô tả nguyên lý

Thuật toán tìm kiếm theo chiều rộng trên đồ thị hoặc cây, sử dụng cấu trúc Queue.

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

function bfs($graph, $start) {
    $visited = []; $queue = [$start];
    $visited[$start] = true;
    while(!empty($queue)) {
        $node = array_shift($queue);
        foreach($graph[$node] as $neighbor) {
            if(!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor;
            }
        }
    }
}
Đồ thị (Graph)

Depth-First Search (DFS)

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

Mô tả nguyên lý

Thuật toán tìm kiếm theo chiều sâu trên đồ thị hoặc cây, sử dụng Stack hoặc đệ quy.

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

function dfs($graph, $node, &$visited = []) {
    $visited[$node] = true;
    foreach ($graph[$node] as $neighbor) {
        if (!isset($visited[$neighbor])) {
            dfs($graph, $neighbor, $visited);
        }
    }
}
Đồ thị (Graph)

Dijkstra Algorithm

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

Mô tả nguyên lý

Tìm đường đi ngắn nhất từ một nguồn đến mọi đỉnh trong đồ thị có trọng số không âm.

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

// Sử dụng cấu trúc Priority Queue kết hợp danh sách kề để tối ưu tìm kiếm khoảng cách tối thiểu.
Đồ thị (Graph)

Floyd-Warshall Algorithm

Thời gian (Time) O(V³)
Không gian (Space) O(V²)

Mô tả nguyên lý

Thuật toán quy hoạch động tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị.

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

function floydWarshall(&$dist, $V) {
    for ($k = 0; $k < $V; $k++) {
        for ($i = 0; $i < $V; $i++) {
            for ($j = 0; $j < $V; $j++) {
                if ($dist[$i][$k] + $dist[$k][$j] < $dist[$i][$j]) {
                    $dist[$i][$j] = $dist[$i][$k] + $dist[$k][$j];
                }
            }
        }
    }
}
Đồ thị (Graph)

Kosaraju Algorithm

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 (Strongly Connected Components) trong đồ thị có hướng.

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

// Thực hiện 2 lần DFS trên đồ thị gốc và đồ thị chuyển vị (transpose graph).
Đồ thị (Graph)

Kruskal Algorithm

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

Mô tả nguyên lý

Tìm cây khung nhỏ nhất (Minimum Spanning Tree) sử dụng cấu trúc Disjoint Set Union (DSU).

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

// Sắp xếp tất cả các cạnh theo trọng số tăng dần và thêm vào cây nếu không tạo chu trình.
Đồ thị (Graph)

Prim Algorithm

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

Mô tả nguyên lý

Xây dựng cây khung nhỏ nhất bằng cách bắt đầu từ một đỉnh bất kỳ và mở rộng cạnh có trọng số nhỏ nhất.

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

// Sử dụng Min Heap để chọn cạnh tối ưu kết nối tập đỉnh đã thăm và chưa thăm.
Đồ thị (Graph)

Topological Sort

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

Mô tả nguyên lý

Sắp xếp tuyến tính các đỉnh của đồ thị có hướng không có chu trình (DAG) dựa trên thứ bậc phụ thuộc.

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

// Dựa trên thuật toán DFS kết hợp ngăn xếp (stack) để đảo ngược thứ tự hoàn thành.