Comment implémenter un algorithme de tri topologique en utilisant Java

Comment utiliser Java pour implémenter un algorithme de tri topologique

Le tri topologique est un algorithme couramment utilisé en théorie des graphes, utilisé pour trier les sommets d'un graphe acyclique dirigé (DAG). Le tri topologique peut être utilisé pour résoudre des problèmes tels que les dépendances ou la planification des tâches. Dans cet article, nous présenterons comment utiliser Java pour implémenter l'algorithme de tri topologique et donnerons des exemples de code correspondants.

L'idée d'implémentation du tri topologique est la suivante :

1. Tout d'abord, nous devons définir une structure de données d'un graphe orienté, qui peut être représentée par une liste de contiguïté. Une liste de contiguïté est une structure de données qui stocke des graphiques. Chaque sommet correspond à une liste chaînée, et la liste chaînée stocke tous les sommets adjacents au sommet.

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. Ensuite, nous devons implémenter une méthode de tri topologique. Le processus de mise en œuvre du tri topologique peut être divisé en deux étapes :

   a. Parcourez le graphique, calculez le degré en entrée de chaque sommet (c'est-à-dire le nombre de sommets qui y pointent) et initialisez une file d'attente pour stocker les sommets avec un en degré de 0.

   b. Supprimez continuellement un sommet de la file d'attente et réduisez le degré en entrée de ses sommets adjacents. Si le degré en entrée d'un sommet devient 0, ajoutez-le à la file d'attente.

   c. Répétez l'étape (b) jusqu'à ce que la file d'attente soit vide et que le degré en entrée de tous les sommets devienne 0. Si le nombre de sommets mis en file d'attente à ce moment n'est pas égal au nombre de sommets du graphe, cela signifie qu'il y a un cycle dans le graphe et que le tri topologique ne peut pas être effectué.

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. Enfin, nous pouvons créer un graphe et appeler la méthode de tri topologique pour le trier.

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

Ci-dessus sont les étapes et les exemples de code pour implémenter l'algorithme de tri topologique en Java. Grâce à des algorithmes de tri topologique, nous pouvons résoudre efficacement des problèmes tels que les dépendances ou la planification des tâches.

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!