So implementieren Sie einen topologischen Sortieralgorithmus für Graphen mit Java

Wie man mit Java den topologischen Sortieralgorithmus von Graphen implementiert

Einführung:
Graph ist eine sehr verbreitete Datenstruktur und hat ein breites Anwendungsspektrum im Bereich der Informatik. Der topologische Sortieralgorithmus ist ein klassischer Algorithmus der Graphentheorie, der einen gerichteten azyklischen Graphen (DAG) sortieren kann, um die Abhängigkeiten zwischen Knoten im Graphen zu bestimmen. In diesem Artikel wird anhand spezifischer Java-Codebeispiele erläutert, wie Sie mithilfe der Programmiersprache Java den topologischen Sortieralgorithmus von Diagrammen implementieren.

1. Definieren Sie die Datenstruktur des Diagramms
Bevor wir den topologischen Sortieralgorithmus implementieren, müssen wir zunächst die Datenstruktur des Diagramms definieren. Um das Problem zu vereinfachen, können wir eine Adjazenzliste verwenden, um den Graphen darzustellen.

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

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

Im obigen Code definieren wir eine Graph-Klasse, die eine Ganzzahl V enthält, die die Anzahl der Scheitelpunkte im Diagramm darstellt, und eine Adjazenzliste adj[], mit So speichern Sie die benachbarten Scheitelpunkte jedes Scheitelpunkts. Graph类，它包含了一个整数V表示图中的顶点数，以及一个邻接表adj[]，用来存储各个顶点的邻接顶点。

二、实现拓扑排序算法
拓扑排序算法的基本思想是通过不断删除图中入度为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方法是拓扑排序的入口方法，它利用递归方法对所有顶点进行逐个排序。最后的printResult方法用来输出排序结果。

三、示例
以下是一个使用拓扑排序算法的示例：

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

2. Implementieren Sie den topologischen Sortieralgorithmus. Die Grundidee des topologischen Sortieralgorithmus besteht darin, kontinuierlich Scheitelpunkte mit einem In-Grad von 0 im Diagramm zu löschen, bis alle Scheitelpunkte im Diagramm gelöscht sind. Das Folgende ist ein Codebeispiel, das Java verwendet, um den topologischen Sortieralgorithmus zu implementieren:

rrreee
Im obigen Code ist die Klasse TopologicalSorting die Klasse, die für die topologische Sortierung verwendet wird. Unter diesen ist die Methode topologicalSortUtil eine rekursive Methode, die zum Implementieren einer bestimmten Sortierlogik verwendet wird. Die Methode topologicalSort ist die Eingabemethode der topologischen Sortierung. Sie verwendet eine rekursive Methode, um alle Eckpunkte einzeln zu sortieren. Die letzte Methode printResult wird zur Ausgabe der sortierten Ergebnisse verwendet.

🎜3. Beispiel🎜Das Folgende ist ein Beispiel für die Verwendung des topologischen Sortieralgorithmus: 🎜rrreee🎜Der Code erstellt einen gerichteten Graphen und fügt einige Kanten hinzu. Führen Sie dann eine topologische Sortierung durch und geben Sie die Ergebnisse über die Klasse TopologicalSorting aus. 🎜🎜Fazit: 🎜Dieser Artikel stellt vor, wie die Java-Sprache zum Implementieren des topologischen Sortieralgorithmus von Diagrammen verwendet wird, und gibt spezifische Codebeispiele. Der topologische Sortieralgorithmus ist ein klassischer Algorithmus zur Lösung des Problems der Sortierung von Scheitelpunktabhängigkeiten in Diagrammen und ist in praktischen Anwendungen von großer Bedeutung. Durch die Einleitung dieses Artikels möchte ich den Lesern helfen, diesen Algorithmus zu verstehen und zu beherrschen. 🎜

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