Comment implémenter un algorithme de tri topologique graphique à l'aide de Java

Comment utiliser Java pour implémenter l'algorithme de tri topologique des graphiques

Introduction :
Le graphique est une structure de données très courante et a un large éventail d'applications dans le domaine de l'informatique. L'algorithme de tri topologique est un algorithme classique de la théorie des graphes qui permet de trier un graphe acyclique dirigé (DAG) pour déterminer les dépendances entre les nœuds du graphe. Cet article présentera comment utiliser le langage de programmation Java pour implémenter l'algorithme de tri topologique des graphiques, avec des exemples de code Java spécifiques.

1. Définir la structure des données du graphe
Avant d'implémenter l'algorithme de tri topologique, nous devons d'abord définir la structure des données du graphe. Pour simplifier le problème, nous pouvons utiliser une liste de contiguïté pour représenter le graphique.

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

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

Dans le code ci-dessus, nous définissons une classe Graph, qui contient un entier V représentant le nombre de sommets dans le graphe, et une liste de contiguïté adj[], en utilisant Pour stocker les sommets adjacents de chaque sommet. 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. Implémenter l'algorithme de tri topologique

L'idée de base de l'algorithme de tri topologique est de supprimer continuellement les sommets avec un degré entrant de 0 dans le graphique jusqu'à ce que tous les sommets du graphique soient supprimés. Voici un exemple de code qui utilise Java pour implémenter l'algorithme de tri topologique :
rrreee

Dans le code ci-dessus, la classe TopologicalSorting est la classe utilisée pour le tri topologique. Parmi elles, la méthode topologicalSortUtil est une méthode récursive utilisée pour implémenter une logique de tri spécifique. La méthode topologicalSort est la méthode d'entrée du tri topologique. Elle utilise une méthode récursive pour trier tous les sommets un par un. La méthode finale printResult est utilisée pour afficher les résultats triés. 🎜🎜3. Exemple🎜Ce qui suit est un exemple d'utilisation de l'algorithme de tri topologique : 🎜rrreee🎜Le code crée un graphe orienté et ajoute des arêtes. Effectuez ensuite un tri topologique et affichez les résultats via la classe TopologicalSorting. 🎜🎜Conclusion : 🎜Cet article présente comment utiliser le langage Java pour implémenter l'algorithme de tri topologique des graphiques et donne des exemples de code spécifiques. L'algorithme de tri topologique est un algorithme classique pour résoudre le problème du tri des dépendances des sommets dans les graphiques, et il revêt une grande importance dans les applications pratiques. Grâce à l'introduction de cet article, j'espère aider les lecteurs à comprendre et à maîtriser cet algorithme. 🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!