Maison Java javaDidacticiel Comment utiliser Java pour implémenter l'algorithme de composants fortement connectés des graphiques

Comment utiliser Java pour implémenter l'algorithme de composants fortement connectés des graphiques

Sep 21, 2023 am 11:09 AM
java Algorithme de composants fortement connectés

Comment utiliser Java pour implémenter lalgorithme de composants fortement connectés des graphiques

Comment utiliser Java pour implémenter l'algorithme de composants fortement connectés des graphiques

Introduction :
Le graphique est une structure de données couramment utilisée en informatique, et il peut nous aider à résoudre de nombreux problèmes pratiques. Dans un graphique, un composant connecté fait référence à un ensemble de sommets du graphique qui ont des chemins mutuellement accessibles. Un composant fortement connecté signifie qu’il existe un chemin bidirectionnel entre deux sommets quelconques dans un graphe orienté. Cet article expliquera comment utiliser Java pour implémenter l'algorithme de composants fortement connectés des graphiques afin d'aider les lecteurs à mieux comprendre la connectivité des graphiques.

1. Représentation des graphiques
En Java, nous pouvons utiliser des matrices de contiguïté ou des listes de contiguïté pour représenter des graphiques. Une matrice de contiguïté est un tableau bidimensionnel où les éléments de la matrice représentent si une arête existe entre deux sommets. La liste de contiguïté utilise un tableau pour stocker l'ensemble d'arêtes correspondant à chaque sommet du graphique. Dans cet article, nous choisissons d'utiliser des listes de contiguïté pour représenter des graphiques.

2. Principe de l'algorithme de composants fortement connectés
L'algorithme de composants fortement connectés utilise la recherche en profondeur d'abord (DFS) pour parcourir le graphique et trouver un ensemble de sommets avec des propriétés fortement connectées. Le principe de base de l'algorithme est le suivant :

  1. Tout d'abord, utilisez DFS pour parcourir chaque sommet du graphique et marquer les sommets visités.
  2. Ensuite, calculez la transposition du graphique (c'est-à-dire inversez la direction des arêtes dirigées) pour obtenir le graphique transposé.
  3. Ensuite, effectuez un parcours DFS sur le graphe transposé et triez les sommets en fonction de l'heure de fin DFS.
  4. Enfin, effectuez un parcours DFS sur le graphique d'origine et divisez les sommets mutuellement accessibles en le même composant connecté selon l'ordre des sommets triés.

3. Implémentation du code Java
Ce qui suit est un exemple de code pour utiliser Java pour implémenter l'algorithme de composant fortement connecté :

import java.util.*;

class Graph {
    private int V;
    private List<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v) {
        adj[u].add(v);
    }

    public void DFSUtil(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        for (int i : adj[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited, stack);
            }
        }
        stack.push(v);
    }

    public Graph getTranspose() {
        Graph g = new Graph(V);
        for (int v = 0; v < V; v++) {
            for (int i : adj[v]) {
                g.adj[i].add(v);
            }
        }
        return g;
    }

    public void printSCCs() {
        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]) {
                DFSUtil(i, visited, stack);
            }
        }

        Graph gr = getTranspose();
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                gr.DFSUtil(v, visited, new Stack<>());
                System.out.println();
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(3, 4);

        System.out.println("Strongly Connected Components:");
        g.printSCCs();
    }
}
Copier après la connexion

Dans le code ci-dessus, nous définissons d'abord une classe Graph pour représenter le graphique. La méthode addEdge est utilisée pour ajouter des arêtes au graphique, la méthode DFSUtil utilise la récursivité pour effectuer un parcours DFS et la méthode getTranspose est utilisée pour calculer la transposition du graphique, la méthode printSCCs est utilisée pour imprimer chaque composant fortement connecté. Graph类来表示图。addEdge方法用于向图中添加边,DFSUtil方法使用递归的方式进行DFS遍历,getTranspose方法用于计算图的转置,printSCCs方法用于打印出各个强连通分量。

Main类中,我们创建一个具有5个顶点的图,并向图中添加边。然后,调用printSCCs

Dans la classe Main, nous créons un graphe avec 5 sommets et ajoutons des arêtes au graphe. Ensuite, appelez la méthode printSCCs pour imprimer les composants fortement connectés du graphique.


Conclusion :

Cet article présente comment utiliser Java pour implémenter l'algorithme de composants fortement connectés des graphiques et fournit des exemples de code spécifiques. En comprenant et maîtrisant cet algorithme, les lecteurs peuvent mieux gérer et résoudre les problèmes de connectivité graphique. J'espère que cet article pourra être utile aux lecteurs ! 🎜

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Racine carrée en Java Racine carrée en Java Aug 30, 2024 pm 04:26 PM

Guide de la racine carrée en Java. Nous discutons ici du fonctionnement de Square Root en Java avec un exemple et son implémentation de code respectivement.

Nombre parfait en Java Nombre parfait en Java Aug 30, 2024 pm 04:28 PM

Guide du nombre parfait en Java. Nous discutons ici de la définition, comment vérifier le nombre parfait en Java ?, des exemples d'implémentation de code.

Générateur de nombres aléatoires en Java Générateur de nombres aléatoires en Java Aug 30, 2024 pm 04:27 PM

Guide du générateur de nombres aléatoires en Java. Nous discutons ici des fonctions en Java avec des exemples et de deux générateurs différents avec d'autres exemples.

Weka en Java Weka en Java Aug 30, 2024 pm 04:28 PM

Guide de Weka en Java. Nous discutons ici de l'introduction, de la façon d'utiliser Weka Java, du type de plate-forme et des avantages avec des exemples.

Numéro Armstrong en Java Numéro Armstrong en Java Aug 30, 2024 pm 04:26 PM

Guide du numéro Armstrong en Java. Nous discutons ici d'une introduction au numéro d'Armstrong en Java ainsi que d'une partie du code.

Numéro de Smith en Java Numéro de Smith en Java Aug 30, 2024 pm 04:28 PM

Guide du nombre de Smith en Java. Nous discutons ici de la définition, comment vérifier le numéro Smith en Java ? exemple avec implémentation de code.

Questions d'entretien chez Java Spring Questions d'entretien chez Java Spring Aug 30, 2024 pm 04:29 PM

Dans cet article, nous avons conservé les questions d'entretien Java Spring les plus posées avec leurs réponses détaillées. Pour que vous puissiez réussir l'interview.

Break or Return of Java 8 Stream Forach? Break or Return of Java 8 Stream Forach? Feb 07, 2025 pm 12:09 PM

Java 8 présente l'API Stream, fournissant un moyen puissant et expressif de traiter les collections de données. Cependant, une question courante lors de l'utilisation du flux est: comment se casser ou revenir d'une opération FOREAK? Les boucles traditionnelles permettent une interruption ou un retour précoce, mais la méthode Foreach de Stream ne prend pas directement en charge cette méthode. Cet article expliquera les raisons et explorera des méthodes alternatives pour la mise en œuvre de terminaison prématurée dans les systèmes de traitement de flux. Lire plus approfondie: Améliorations de l'API Java Stream Comprendre le flux Forach La méthode foreach est une opération terminale qui effectue une opération sur chaque élément du flux. Son intention de conception est

See all articles