Bellman-Ford Algorithm
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.
Breadth-First Search (BFS)
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;
}
}
}
}
Depth-First Search (DFS)
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);
}
}
}
Dijkstra Algorithm
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.
Floyd-Warshall Algorithm
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];
}
}
}
}
}
Kosaraju Algorithm
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).
Kruskal Algorithm
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.
Prim Algorithm
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.
Topological Sort
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.