So implementieren Sie einen topologischen Sortieralgorithmus mit Java

So verwenden Sie Java, um einen topologischen Sortieralgorithmus zu implementieren

Topologische Sortierung ist ein häufig verwendeter Algorithmus in der Graphentheorie, der zum Sortieren der Scheitelpunkte von Directed Asymmetric Graph (DAG) verwendet wird. Topologische Sortierung kann zur Lösung von Problemen wie Abhängigkeiten oder Aufgabenplanung verwendet werden. In diesem Artikel stellen wir vor, wie Java zum Implementieren des topologischen Sortieralgorithmus verwendet wird, und geben entsprechende Codebeispiele.

Die Implementierungsidee der topologischen Sortierung lautet wie folgt:

1. Zunächst müssen wir eine Datenstruktur eines gerichteten Graphen definieren, der durch eine Adjazenzliste dargestellt werden kann. Eine Adjazenzliste ist eine Datenstruktur, die Diagramme speichert. Jeder Scheitelpunkt entspricht einer verknüpften Liste, und die verknüpfte Liste speichert alle an den Scheitelpunkt angrenzenden Scheitelpunkte.

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. Dann müssen wir eine topologische Sortiermethode implementieren. Der Implementierungsprozess der topologischen Sortierung kann in zwei Schritte unterteilt werden:

   a Durchlaufen Sie den Graphen, berechnen Sie den In-Grad jedes Scheitelpunkts (dh wie viele Scheitelpunkte darauf zeigen) und initialisieren Sie eine Warteschlange zum Speichern von Scheitelpunkten mit einem In-Grad von 0.

   b. Nehmen Sie kontinuierlich einen Scheitelpunkt aus der Warteschlange heraus und reduzieren Sie den In-Grad seiner benachbarten Scheitelpunkte. Wenn der In-Grad eines Scheitelpunkts 0 wird, fügen Sie ihn der Warteschlange hinzu.

   c. Wiederholen Sie Schritt (b), bis die Warteschlange leer ist und der In-Grad aller Eckpunkte 0 wird. Wenn die Anzahl der zu diesem Zeitpunkt in die Warteschlange eingereihten Scheitelpunkte nicht der Anzahl der Scheitelpunkte des Diagramms entspricht, bedeutet dies, dass sich im Diagramm ein Zyklus befindet und die topologische Sortierung nicht abgeschlossen werden kann.

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. Schließlich können wir ein Diagramm erstellen und die topologische Sortiermethode aufrufen, um es zu sortieren.

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

Das Obige sind die Schritte und Codebeispiele für die Implementierung des topologischen Sortieralgorithmus in Java. Durch topologische Sortieralgorithmen können wir Probleme wie Abhängigkeiten oder Aufgabenplanung effektiv lösen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen topologischen Sortieralgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!