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

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

はじめに:
グラフは非常に一般的なデータ構造であり、さまざまな用途に使用できます。コンピューターサイエンスの分野。トポロジカル ソート アルゴリズムは、有向非巡回グラフ (DAG) をソートしてグラフ内のノード間の依存関係を判断できる、グラフ理論の古典的なアルゴリズムです。この記事では、Java プログラミング言語を使用してグラフのトポロジカル ソート アルゴリズムを実装する方法を、具体的な Java コード例とともに紹介します。

1. グラフのデータ構造を定義する
トポロジカルソートアルゴリズムを実装する前に、まずグラフのデータ構造を定義する必要があります。問題を単純化するために、隣接リストを使用してグラフを表すことができます。

import java.util.*;

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);
    }

    // 其他图操作方法...
}

上記のコードでは、グラフ内の頂点の数を表す整数 V と隣接リスト adj[]## を含む Graph クラスを定義します。 # 、各頂点の隣接する頂点を保存するために使用されます。

2. トポロジカル ソート アルゴリズムの実装

トポロジカル ソート アルゴリズムの基本的な考え方は、グラフ内のすべての頂点が削除されるまで、グラフ内の内次数 0 の頂点を継続的に削除することです。以下は、Java を使用してトポロジカル ソート アルゴリズムを実装するコード例です。

class TopologicalSorting {
    private Graph graph;
    private int V;
    private LinkedList<Integer> resultList;

    TopologicalSorting(Graph g) {
        graph = g;
        V = g.V;
        resultList = new LinkedList<>();
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;

        Iterator<Integer> it = graph.adj[v].iterator();
        while (it.hasNext()) {
            int i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        stack.push(v);
    }

    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        while (stack.empty() == false)
            resultList.add(stack.pop());
    }

    // 输出结果
    void printResult() {
        System.out.println("拓扑排序结果：");
        for (int i : resultList)
            System.out.print(i + " ");
        System.out.println();
    }
}

上記のコードでは、

TopologicalSorting クラスがトポロジカル ソートに使用されるクラスです。このうち、topologicalSortUtil メソッドは、特定の並べ替えロジックを実装するために使用される再帰的メソッドです。 topologicalSort メソッドは、再帰的手法を使用してすべての頂点を 1 つずつソートするトポロジカル ソートのエントリ メソッドです。最後の printResult メソッドは、並べ替えられた結果を出力するために使用されます。

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);

        TopologicalSorting ts = new TopologicalSorting(graph);
        ts.topologicalSort();
        ts.printResult();
    }
}

コードは、有向グラフを作成し、いくつかのエッジを追加します。次に、トポロジカル ソートを実行し、

TopologicalSorting クラスを通じて結果を出力します。

結論:

この記事では、Java 言語を使用してグラフのトポロジカル ソート アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。トポロジカルソートアルゴリズムは、グラフ内の頂点の依存関係をソートする問題を解決する古典的なアルゴリズムであり、実際のアプリケーションでは非常に重要です。この記事の紹介を通じて、読者がこのアルゴリズムを理解し、習得できるようにしたいと考えています。

以上がJavaを使用してグラフトポロジーソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。