Java 中拓撲排序的實現
這篇深入的文章將教你如何以遞迴順序在有向無環圖上實現拓撲排序。本教程分為兩個部分。
首先，我們從理論上展開拓撲順序的結構、應用、範圍和排序，以幫助我們的讀者建立基礎，然後自己執行 Java 程式碼。
你可能已經猜到了，本文的第二部分是關於有向無環圖 (DAG) 的實現。
Java 中的拓撲排序
拓撲排序是圖中標註 (n) 的排序。如果在 (u,v) 之間有一條邊，那麼 u 必須在 v 之前。
在現實世界的場景中，它可以成為構建相互依賴的應用程式的基礎。
在我們進行拓撲排序之前，你必須考慮只有有向無環圖 (DAG) 才能進行拓撲排序。
拓撲排序的兩個真實示例
- 例如，在整合開發環境 (IDE) 中，給定管理使用者檔案系統的底層邏輯，IDE 可以根據通過 GUI 獲取的使用者偏好使用拓撲順序來確定檔案的執行和管理。
- 考慮以下示例：兩條路線可以將你帶到目的地（A 和 B）。
要到達那裡，你一次只能帶一個。假設你走 B 路。在這種情況下，你不會走 A 路。
因此，它不會建立一個絕對迴圈。因此，拓撲排序也是可能的。
相反，只有一個週期。拓撲順序很可能被排除。
拓撲排序的應用
- 根據作業之間的相互依賴安排作業。這種型別的排序在基於研究的應用軟體工程、能源效率、雲和網路中廣泛執行。
- 拓撲排序的另一個應用可以是確定編譯任務應該如何在 makefile、資料序列化和連結器中的符號依賴中執行。
- 也適用於製造工作流程和上下文無關語法。
- 很多構建系統都使用這種演算法。
- 遷移系統長期以來一直在使用這種順序。
時間複雜度
它類似於深度優先搜尋 (DFS) 演算法，但有一個額外的堆疊。時間複雜度一般來說是 O(V+E)。
輔助空間
O(V) - 堆疊需要額外的空間。
直接無環圖的演示
首先，你應該清楚，如果圖是有向無環圖 (DAG)，拓撲排序是唯一可行的解決方案。另外，請注意，對於給定的有向無環圖，可能有幾種替代的拓撲排序。
拓撲排序是頂點在陣列中的排列。
考慮以下示例：
此 DAG 最多有四種可能的排序解決方案：
A B C D E F
A B C D F E
A C B D E F
A C B D F E
V，邊寫為 E。如果你理解了縮寫，我們希望你也能理解以下對 DAG 的假設描述。值得一提的是，我們的演示只是為了解釋通用過程。
如果你對資料結構方面感興趣，請考慮另一種選擇。但是，以下描述足以使用 Java 以遞迴和迭代順序對直接圖進行排序，以達到所有實際目的。
因此，事不宜遲，請按照以下步驟操作。
-
找到每個圖節點的入度（
n）：
如你所見，
VA在上圖中的in-degree最少。 -
因此，現在我們將刪除
VA及其相關邊。這些相同的邊也稱為鄰居。 -
完成後，你需要做的就是更新其他頂點的
in-degree。
-
VB的in-degree最少。刪除VB及其相關邊。 -
現在，更新其他頂點的
in-degree。
- 上圖也可以表示為：
C => 0 , D => 0, E => 2 - 同樣，此圖的執行也可能有所不同。
- 僅供大家理解演示。
由於我們得到了兩個入度最小的頂點，因此最終可以將圖排序為以下兩個 n 順序。
A B C D E
A B D C E
Java 中拓撲排序的實現
我們將使用這個圖來實現。我們的目標是基於圖論確定 u 在 v 之前的從屬關係。
不用說，這個執行是基於 DAG 和 DFS。我們將使用一種演算法對圖進行拓撲排序。
請繼續閱讀每一步以瞭解更多資訊。
- 圖表：
讓我們以 v15 為例。V15 取決於 v10 和 v5。
V5 依賴於 v10 和 v20。V10 依賴於 v20。
基於依賴關係，v5、v10 和 v20 在拓撲排序中應該排在 v15 之前。
你還應該瞭解深度優先搜尋 (DFS) 以瞭解此實現。
- DFS 演算法：
深度優先搜尋，也稱為深度優先遍歷，是一種遞迴演算法，用於查詢圖或樹資料結構的所有頂點。遍歷一個圖需要訪問它的所有節點。
它將圖形的每個頂點分類為兩組之一。
- 訪問
v。 - 沒有訪問
v。
另外，請注意 DFS 演算法的功能如下：
- 最初，它將圖形的頂點排列在堆疊的頂部。
- 然後，它將堆疊中的頂部專案新增到訪問列表中。
- 之後，它會列出與該頂點相鄰的節點。
- 將不在訪問列表中的堆疊在頂部。
同時，應重複步驟 2 和 3，直到堆疊為空。
Java 中遞迴順序的拓撲排序
因為拓撲排序包含一個短棧，所以我們不會立即列印頂點。相反，我們將遞迴地對其所有鄰居呼叫拓撲排序，然後將其推送到堆疊中。
到目前為止，讓我們將邏輯流程分解為幾個易於理解的部分。
TopoSortDAG類 - 包含一個包含所有節點的堆疊，並確定已訪問和未訪問的節點。
程式碼：
public class TopoSortDAG {
Stack<N> customstack;
public TopoSortDAG() {
customstack = new Stack<>();
}
static class N {
int d;
boolean isVstd;
List<N> nghbr;
N(int d) {
this.d = d;
this.nghbr = new ArrayList<>();
}
- 遞迴拓撲排序演算法
程式碼：
public void tpSort(N N) {
List<N> nghbr = N.getnghbr();
for (int i = 0; i < nghbr.size(); i++) {
N n = nghbr.get(i);
if (n != null && !n.isVstd) {
tpSort(n);
n.isVstd = true;
}
}
customstack.push(N);
}
解釋：
- 該演算法的執行是因為當我們將一個
v壓入堆疊時，我們之前已經壓入了它的鄰居（及其依賴項）。 - 從此以後，沒有依賴關係的
v將自動位於堆疊頂部。
20 將位於堆疊頂部。到現在為止，我們希望你已經理解了迄今為止驅動拓撲排序的基本概念。
也就是說，在我們執行整個程式之前，你應該首先了解每個步驟，以便你可以在下次使用 toposort 時建立圖表。
使用遞迴順序在 Java 中實現拓撲排序：
// We will implement a topological sort algorithm on a direct acyclic graph using the depth-first
// search technique.
package delftstack.com.util;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @author SARWAN
*
*/
public class TopoSortDAG {
Stack<N> customstack;
public TopoSortDAG() {
customstack = new Stack<>();
}
static class N {
int d;
boolean isVstd;
List<N> nghbr;
N(int d) {
this.d = d;
this.nghbr = new ArrayList<>();
}
public void adj(N nghbrN) {
this.nghbr.add(nghbrN);
}
public List<N> getnghbr() {
return nghbr;
}
public void setnghbr(List<N> nghbr) {
this.nghbr = nghbr;
}
public String toString() {
return "" + d;
}
}
public void tpSort(N N) {
List<N> nghbr = N.getnghbr();
for (int i = 0; i < nghbr.size(); i++) {
N n = nghbr.get(i);
if (n != null && !n.isVstd) {
tpSort(n);
n.isVstd = true;
}
}
customstack.push(N);
}
public static void main(String arg[]) {
TopoSortDAG topo = new TopoSortDAG();
N N20 = new N(20);
N N5 = new N(5);
N N10 = new N(10);
N N15 = new N(15);
N N30 = new N(30);
N N25 = new N(25);
N N35 = new N(35);
N20.adj(N5);
N20.adj(N10);
N5.adj(N15);
N10.adj(N5);
N10.adj(N15);
N10.adj(N30);
N10.adj(N25);
N15.adj(N30);
N30.adj(N35);
N25.adj(N35);
System.out.println("Sorting Result Set Based on the Graph:");
topo.tpSort(N20);
Stack<N> reS = topo.customstack;
while (reS.empty() == false) System.out.print(reS.pop() + " ");
}
}
輸出：
Sorting Result Set Based on the Graph:
20 10 25 5 15 30 35
輸出堆疊：
Sarwan Soomro is a freelance software engineer and an expert technical writer who loves writing and coding. He has 5 years of web development and 3 years of professional writing experience, and an MSs in computer science. In addition, he has numerous professional qualifications in the cloud, database, desktop, and online technologies. And has developed multi-technology programming guides for beginners and published many tech articles.
LinkedIn