Javaを使用してトポロジカルソートアルゴリズムを実装する方法

Java を使用してトポロジカル ソート アルゴリズムを実装する方法

トポロジカル ソートは、グラフ理論で一般的に使用されるアルゴリズムであり、有向非巡回グラフ (有向非巡回グラフ、DAG 用) に使用されます。 short) 頂点がソートされます。トポロジカルソートは、依存関係やタスクのスケジュールなどの問題を解決するために使用できます。この記事では、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. 次に、トポロジカルソート手法を実装する必要があります。トポロジカル ソートの実装プロセスは 2 つのステップに分けることができます:

   a. グラフを走査し、各頂点の次数 (つまり、その頂点を指す頂点の数) を計算し、キューを初期化します。頂点 0 の入次数を格納します。

   b. キューから頂点を取り出し続け、隣接する頂点の入次数を減らしていき、頂点の入次数が 0 になったらキューに追加します。

   c. キューが空になり、すべての頂点の入次数が 0 になるまで、ステップ (b) を繰り返します。このときにキューに入れられた頂点の数がグラフの頂点の数と等しくない場合、グラフ内に循環が存在し、トポロジカル ソートが完了できないことを意味します。

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 中国語 Web サイトの他の関連記事を参照してください。