如何使用java實作拓樸排序演算法

如何使用Java實作拓樸排序演算法

拓樸排序是圖論中常用的演算法，用於給有向無環圖(Directed Acyclic Graph，簡稱DAG)的頂點進行排序。拓樸排序可以用來解決依賴關係或任務調度等問題。在本文中，我們將介紹如何使用Java來實作拓樸排序演算法，並給出對應的程式碼範例。

拓樸排序的實作想法如下：

1. 首先，我們需要定義一個有向圖的資料結構，可以使用鄰接表來表示。鄰接表是一種儲存圖的資料結構，每個頂點對應一個鍊錶，鍊錶中儲存了與該頂點相鄰的所有頂點。

class Graph {
    private int V; // 图的顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
}

2. 然後，我們需要實作拓樸排序的方法。拓樸排序的實作過程可以分為兩個步驟：

   a. 遍歷圖，計算每個頂點的入度（即有多少頂點指向它），並初始化一個佇列來儲存入度為0的頂點。

   b. 不斷從佇列中取出一個頂點，減少其鄰接頂點的入度，如果某個頂點的入度變為0，則將其加入佇列。

   c. 重複步驟(b)，直到佇列為空，所有頂點的入度都變成0。如果此時入隊的頂點數不等於圖的頂點數，則表示圖中存在環，拓樸排序無法完成。

import java.util.*;

class TopologicalSort {
    // 拓扑排序算法
    void topologicalSort(Graph graph) {
        int V = graph.V;
        LinkedList<Integer> adj[] = graph.adj;

        int[] indegree = new int[V];
        for (int i = 0; i < V; ++i) {
            for (int j : adj[i]) {
                indegree[j]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; ++i) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;
        ArrayList<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            for (int v : adj[u]) {
                if (--indegree[v] == 0) {
                    queue.add(v);
                }
            }
            count++;
        }

        if (count != V) {
            System.out.println("图中存在环，无法进行拓扑排序");
            return;
        }

        System.out.println("拓扑排序结果：");
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

3. 最後，我們可以建立一個圖，並呼叫拓樸排序方法來排序。

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.topologicalSort(graph);
    }
}

以上就是使用Java實作拓樸排序演算法的步驟和程式碼範例。透過拓樸排序演算法，我們可以有效地解決依賴關係或任務調度等問題。

以上是如何使用java實作拓樸排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！