


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
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 :
- Tout d'abord, utilisez DFS pour parcourir chaque sommet du graphique et marquer les sommets visités.
- Ensuite, calculez la transposition du graphique (c'est-à-dire inversez la direction des arêtes dirigées) pour obtenir le graphique transposé.
- Ensuite, effectuez un parcours DFS sur le graphe transposé et triez les sommets en fonction de l'heure de fin DFS.
- 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(); } }
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
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 :
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!

Outils d'IA chauds

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

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

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

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

Sujets chauds

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.

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.

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

Guide de TimeStamp to Date en Java. Ici, nous discutons également de l'introduction et de la façon de convertir l'horodatage en date en Java avec des exemples.

Les capsules sont des figures géométriques tridimensionnelles, composées d'un cylindre et d'un hémisphère aux deux extrémités. Le volume de la capsule peut être calculé en ajoutant le volume du cylindre et le volume de l'hémisphère aux deux extrémités. Ce tutoriel discutera de la façon de calculer le volume d'une capsule donnée en Java en utilisant différentes méthodes. Formule de volume de capsule La formule du volume de la capsule est la suivante: Volume de capsule = volume cylindrique volume de deux hémisphères volume dans, R: Le rayon de l'hémisphère. H: La hauteur du cylindre (à l'exclusion de l'hémisphère). Exemple 1 entrer Rayon = 5 unités Hauteur = 10 unités Sortir Volume = 1570,8 unités cubes expliquer Calculer le volume à l'aide de la formule: Volume = π × r2 × h (4

PHP et Python ont chacun leurs propres avantages, et le choix doit être basé sur les exigences du projet. 1.Php convient au développement Web, avec une syntaxe simple et une efficacité d'exécution élevée. 2. Python convient à la science des données et à l'apprentissage automatique, avec une syntaxe concise et des bibliothèques riches.

PHP est un langage de script largement utilisé du côté du serveur, particulièrement adapté au développement Web. 1.Php peut intégrer HTML, traiter les demandes et réponses HTTP et prend en charge une variété de bases de données. 2.PHP est utilisé pour générer du contenu Web dynamique, des données de formulaire de traitement, des bases de données d'accès, etc., avec un support communautaire solide et des ressources open source. 3. PHP est une langue interprétée, et le processus d'exécution comprend l'analyse lexicale, l'analyse grammaticale, la compilation et l'exécution. 4.PHP peut être combiné avec MySQL pour les applications avancées telles que les systèmes d'enregistrement des utilisateurs. 5. Lors du débogage de PHP, vous pouvez utiliser des fonctions telles que error_reportting () et var_dump (). 6. Optimiser le code PHP pour utiliser les mécanismes de mise en cache, optimiser les requêtes de base de données et utiliser des fonctions intégrées. 7

Java est un langage de programmation populaire qui peut être appris aussi bien par les développeurs débutants que par les développeurs expérimentés. Ce didacticiel commence par les concepts de base et progresse vers des sujets avancés. Après avoir installé le kit de développement Java, vous pouvez vous entraîner à la programmation en créant un simple programme « Hello, World ! ». Une fois que vous avez compris le code, utilisez l'invite de commande pour compiler et exécuter le programme, et « Hello, World ! » s'affichera sur la console. L'apprentissage de Java commence votre parcours de programmation et, à mesure que votre maîtrise s'approfondit, vous pouvez créer des applications plus complexes.
