Hướng dẫn từng bước để hiểu thuật toán tìm Minimum Spanning Arborescence — cây khung nhỏ nhất có hướng trên đồ thị.
Cho đồ thị có hướng G, gốc r. Tìm cây đến được mọi đỉnh, trọng số nhỏ nhất.
Tham lam + Co rút chu trình (contraction) + Đệ quy.
O(E·V) với cài đặt đơn giản. O(E + V log V) với Fibonacci Heap.
Mạng phân tán, NLP dependency trees, định tuyến có hướng.
minIn[v].// minIn[v] = cạnh rẻ nhất đi vào v DirectedEdge[] minIn = new DirectedEdge[n]; double[] minW = new double[n]; Arrays.fill(minW, Double.POSITIVE_INFINITY); for (DirectedEdge e : G.edges()) { int vao = e.to(); int ra = e.from(); if (vao == root) continue; // gốc không có cha if (ra == vao) continue; // bỏ tự vòng if (e.weight() < minW[vao]) { minW[vao] = e.weight(); minIn[vao] = e; } }
minIn và chạy phát hiện chu trình có hướng (DFS).EdgeWeightedDigraph subG = buildSubgraph(n, minIn, root); EdgeWeightedDirectedCycle cycleFinder = new EdgeWeightedDirectedCycle(subG); if (!cycleFinder.hasCycle()) { // Không có chu trình → minIn chính là MSA List<DirectedEdge> result = new ArrayList<>(); for (int vao = 0; vao < n; vao++) if (vao != root && minIn[vao] != null) result.add(minIn[vao]); return result; // ← MSA hoàn chỉnh! }
cycleFinder, đánh dấu tất cả đỉnh nằm trong C bằng mảng inCycle[].
List<DirectedEdge> cycleEdgeList = new ArrayList<>(); for (DirectedEdge e : cycleFinder.cycle()) cycleEdgeList.add(e); // Đánh dấu đỉnh nào trong chu trình boolean[] inCycle = new boolean[n]; for (DirectedEdge e : cycleEdgeList) { inCycle[e.from()] = true; inCycle[e.to()] = true; }
superNodeId). Xây đồ thị mới G' nhỏ hơn G.w' = w(e) − minW[v]minIn[v] vốn đang có trong C. Chi phí thực chỉ là phần chênh lệch.
minW[v] rồi (vì toàn bộ minIn của C đã được tính vào chu trình). Nên chỉ tính thêm phần dư = w − minW[v].// Gán id mới: đỉnh ngoài C → 0,1,2,...; đỉnh trong C → superNodeId int[] newId = new int[n]; int counter = 0; for (int v = 0; v < n; v++) if (!inCycle[v]) newId[v] = counter++; int superNodeId = counter++; for (int v = 0; v < n; v++) if (inCycle[v]) newId[v] = superNodeId; // Thêm cạnh vào G', điều chỉnh trọng số cạnh vào C for (DirectedEdge e : G.edges()) { if (inCycle[ra] && inCycle[vao]) continue; // bỏ nội bộ C double newWeight = inCycle[vao] ? (e.weight() - minW[vao]) // cạnh vào C: giảm trọng số : e.weight(); // cạnh thường: giữ nguyên contractedG.addEdge(new DirectedEdge(nra, nvao, newWeight)); }
edmonds(contractedG, newRoot). Mỗi lần đệ quy, G' nhỏ hơn G ít nhất 1 đỉnh (nhiều đỉnh C → 1 siêu đỉnh), đảm bảo thuật toán luôn kết thúc.
// Đệ quy — G' nhỏ hơn G, sẽ đạt base case List<DirectedEdge> contractedMSA = edmonds(contractedG, newRoot); if (contractedMSA == null) return null;
contractedMSA về cạnh gốc tương ứng (qua bảng ánh xạ originalList).replacedVertex: đỉnh trong C bị cạnh từ ngoài thay thế.replacedVertex (vì đỉnh đó đã có cha từ ngoài rồi).
int replacedVertex = -1; for (DirectedEdge ce : contractedMSA) { DirectedEdge original = findOriginalEdge(ce, ...); if (original != null) { result.add(original); if (ce.to() == superNodeId) replacedVertex = original.to(); // đỉnh bị cạnh ngoài thay thế } } // Thêm chu trình C, bỏ cạnh vào replacedVertex for (DirectedEdge e : cycleEdgeList) if (e.to() != replacedVertex) result.add(e);
Cạnh có hướng: from(), to(), weight(). Bất biến sau khi tạo.
Đồ thị có hướng có trọng số. Danh sách kề adj(v), phương thức edges().
Phát hiện chu trình có hướng bằng DFS. hasCycle(), cycle() trả về danh sách cạnh.
Lớp chính. Constructor nhận G và root, gọi đệ quy edmonds(), lưu kết quả vào msaEdges.
| Bước | Hành động | Chi phí | Ghi chú |
|---|---|---|---|
| B1 | Chọn minIn mỗi đỉnh | O(E) | Duyệt toàn bộ cạnh 1 lần |
| B2 | Phát hiện chu trình (DFS) | O(V) | Đồ thị con chỉ có V cạnh |
| B3 | Thu thập cạnh chu trình C | O(V) | Độ dài C ≤ V |
| B4 | Co rút C → G' | O(E) | G' có ít hơn ≥1 đỉnh |
| B5 | Đệ quy trên G' | T(V−1, E) | Mỗi lần giảm ≥1 đỉnh |
| B6 | Phục hồi kết quả | O(E + V) | Tra bảng ánh xạ |
| Tổng cộng (đơn giản) | O(V · E) | Tối đa V lần đệ quy | |