java graph tutorial how implement graph data structure
Ce didacticiel Java Graph complet explique en détail la structure des données graphiques. Il comprend comment créer, implémenter, représenter et parcourir des graphiques en Java:
meilleur logiciel de nettoyage gratuit pour windows 10
Une structure de données graphique représente principalement un réseau reliant divers points. Ces points sont appelés sommets et les liens reliant ces sommets sont appelés «arêtes». Ainsi, un graphe g est défini comme un ensemble de sommets V et d'arêtes E qui relient ces sommets.
Les graphiques sont principalement utilisés pour représenter divers réseaux tels que les réseaux informatiques, les réseaux sociaux, etc. Ils peuvent également être utilisés pour représenter diverses dépendances dans des logiciels ou des architectures. Ces graphiques de dépendances sont très utiles pour analyser le logiciel et parfois aussi pour le déboguer.
=> Consultez TOUS les didacticiels Java ici.
Ce que vous apprendrez:
- Structure de données Java Graph
- Comment créer un graphique?
- Implémentation de graph en Java
- Bibliothèque de graphes Java
- Conclusion
Structure de données Java Graph
Ci-dessous est un graphe ayant cinq sommets {A, B, C, D, E} et des arêtes données par {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Comme les arêtes ne montrent aucune direction, ce graphique est appelé «graphe non orienté».
Outre le graphe non orienté illustré ci-dessus, il existe plusieurs variantes du graphe en Java.
Discutons de ces variantes en détail.
Différentes variantes de graphique
Voici quelques-unes des variantes du graphique.
# 1) Graphique dirigé
Un graphe orienté ou digraphe est une structure de données de graphe dans laquelle les arêtes ont une direction spécifique. Ils proviennent d'un sommet et aboutissent à un autre sommet.
Le diagramme suivant montre l'exemple de graphe orienté.
Dans le diagramme ci-dessus, il y a une arête du sommet A au sommet B.Mais notez que A à B n'est pas la même chose que B à A comme dans un graphe non orienté à moins qu'il n'y ait une arête spécifiée de B à A.
Un graphe orienté est cyclique s'il existe au moins un chemin dont le premier et le dernier sommet sont identiques. Dans le diagramme ci-dessus, un chemin A-> B-> C-> D-> E-> A forme un cycle dirigé ou un graphe cyclique.
Inversement, un graphe acyclique dirigé est un graphe dans lequel il n'y a pas de cycle dirigé, c'est-à-dire qu'il n'y a pas de chemin qui forme un cycle.
# 2) Graphique pondéré
Dans un graphique pondéré, un poidsest associé à chaque arête du graphe. Le poids indique normalement la distance entre les deux sommets. Le diagramme suivant montre le graphique pondéré. Comme aucune direction n'est indiquée, il s'agit du graphique non orienté.
Notez qu'un graphique pondéré peut être orienté ou non.
Comment créer un graphique?
Java ne fournit pas une implémentation complète de la structure de données du graphe. Cependant, nous pouvons représenter le graphique par programme à l'aide de Collections en Java. Nous pouvons également implémenter un graphe en utilisant des tableaux dynamiques comme des vecteurs.
Habituellement, nous implémentons des graphiques en Java à l'aide de la collection HashMap. Les éléments HashMap se présentent sous la forme de paires clé-valeur. Nous pouvons représenter la liste de contiguïté du graphe dans un HashMap.
Un moyen le plus courant de créer un graphique consiste à utiliser l'une des représentations de graphiques comme la matrice de contiguïté ou la liste de contiguïté. Nous discuterons de ces représentations ensuite, puis implémenterons le graphe en Java en utilisant la liste de contiguïté pour laquelle nous utiliserons ArrayList.
Représentation graphique en Java
La représentation graphique désigne l’approche ou la technique selon laquelle les données graphiques sont stockées dans la mémoire de l’ordinateur.
Nous avons deux représentations principales des graphiques comme indiqué ci-dessous.
Matrice d'adjacence
La matrice d'adjacence est une représentation linéaire de graphes. Cette matrice stocke le mappage des sommets et des arêtes du graphe. Dans la matrice de contiguïté, les sommets du graphique représentent des lignes et des colonnes. Cela signifie que si le graphe a N sommets, alors la matrice de contiguïté aura la taille NxN.
Si V est un ensemble de sommets du graphe alors l'intersection Mijdans la liste de contiguïté = 1 signifie qu'il existe une arête entre les sommets i et j.
Pour mieux comprendre ce concept, préparons une matrice de contiguïté pour un graphe non orienté.
Comme le montre le diagramme ci-dessus, nous voyons que pour le sommet A, les intersections AB et AE sont définies sur 1 car il y a une arête de A à B et de A à E. De même, l'intersection BA est définie sur 1, car il s'agit d'un graphe et AB = BA. De même, nous avons mis à 1 toutes les autres intersections pour lesquelles il existe une arête.
Dans le cas où le graphique est orienté, l'intersection Mijsera mis à 1 uniquement s'il y a un bord clair dirigé de Vi vers Vj.
Ceci est illustré dans l'illustration suivante.
Comme nous pouvons le voir sur le diagramme ci-dessus, il y a une arête de A à B. Donc, l'intersection AB est mise à 1 mais l'intersection BA est mise à 0. C'est parce qu'il n'y a pas d'arête dirigée de B vers A.
Considérons les sommets E et D. Nous voyons qu'il y a des arêtes de E à D ainsi que de D à E. Par conséquent, nous avons mis ces deux intersections à 1 dans la matrice de contiguïté.
Nous passons maintenant aux graphiques pondérés. Comme nous le savons pour le graphe pondéré, un entier également appelé poids est associé à chaque arête. Nous représentons ce poids dans la matrice de contiguïté pour l'arête qui existe. Ce poids est spécifié chaque fois qu’il y a une arête d’un sommet à un autre au lieu de «1».
Cette représentation est présentée ci-dessous.
Liste de proximité
Au lieu de représenter un graphe comme une matrice de contiguïté qui est de nature séquentielle, nous pouvons également utiliser une représentation liée. Cette représentation liée est connue sous le nom de liste de contiguïté. Une liste de contiguïté n'est rien d'autre qu'une liste chaînée et chaque nœud de la liste représente un sommet.
La présence d'une arête entre deux sommets est indiquée par un pointeur du premier sommet au second. Cette liste de contiguïté est conservée pour chaque sommet du graphique.
Lorsque nous avons parcouru tous les nœuds adjacents pour un nœud particulier, nous stockons NULL dans le champ de pointeur suivant du dernier nœud de la liste de contiguïté.
Nous allons maintenant utiliser les graphiques ci-dessus que nous avons utilisés pour représenter la matrice de contiguïté pour démontrer la liste de contiguïté.
La figure ci-dessus montre la liste de contiguïté pour le graphe non orienté. Nous voyons que chaque sommet ou nœud a sa liste de contiguïté.
Dans le cas du graphe non orienté, les longueurs totales des listes de contiguïté sont généralement le double du nombre d'arêtes. Dans le graphique ci-dessus, le nombre total d'arêtes est de 6 et le total ou la somme de la longueur de toute la liste de contiguïté est de 12.
Préparons maintenant une liste de contiguïté pour le graphique dirigé.
Comme le montre la figure ci-dessus, dans le graphe orienté, la longueur totale des listes de contiguïté du graphe est égale au nombre d'arêtes dans le graphe. Dans le graphique ci-dessus, il y a 9 arêtes et la somme des longueurs des listes de contiguïté pour ce graphique = 9.
Considérons maintenant le graphe orienté pondéré suivant. Notez que chaque bord du graphique pondéré a un poids qui lui est associé. Ainsi, lorsque nous représentons ce graphique avec la liste de contiguïté, nous devons ajouter un nouveau champ à chaque nœud de la liste qui dénotera le poids de l'arête.
La liste de contiguïté pour le graphique pondéré est présentée ci-dessous.
Le diagramme ci-dessus montre le graphique pondéré et sa liste de contiguïté. Notez qu'il existe un nouvel espace dans la liste de contiguïté qui indique le poids de chaque nœud.
Implémentation de graph en Java
Le programme suivant montre l'implémentation d'un graphe en Java. Ici, nous avons utilisé la liste de contiguïté pour représenter le graphique.
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i Production:
Traversée graphique Java
Pour effectuer toute action significative, comme la recherche de la présence de données, nous devons parcourir le graphique de sorte que chaque sommet et l'arête du graphique soient visités au moins une fois. Cela se fait à l'aide d'algorithmes de graphes qui ne sont rien d'autre qu'un ensemble d'instructions qui nous aident à parcourir le graphe.
Il existe deux algorithmes pris en charge pour parcourir le graphique en Java .
- Traversée en profondeur d'abord
- Traversée en largeur d'abord
Traversée en profondeur d'abord
La recherche en profondeur d'abord (DFS) est une technique utilisée pour parcourir un arbre ou un graphique. La technique DFS commence par un nœud racine, puis traverse les nœuds adjacents du nœud racine en approfondissant le graphique. Dans la technique DFS, les nœuds sont traversés en profondeur jusqu'à ce qu'il n'y ait plus d'enfants à explorer.
Une fois que nous atteignons le nœud feuille (plus de nœuds enfants), le DFS revient en arrière et commence avec d'autres nœuds et effectue la traversée de la même manière. La technique DFS utilise une structure de données de pile pour stocker les nœuds qui sont traversés.
Voici l'algorithme de la technique DFS.
Algorithme
Étape 1: Commencez par le nœud racine et insérez-le dans la pile
Étape 2: Pop l'élément de la pile et l'insérer dans la liste 'visité'
Étape 3: pour le nœud marqué comme «visité» (ou dans la liste visitée), ajoutez à la pile les nœuds adjacents de ce nœud qui ne sont pas encore marqués comme visité.
Étape 4: Répétez les étapes 2 et 3 jusqu'à ce que la pile soit vide.
Illustration de la technique DFS
Nous allons maintenant illustrer la technique DFS en utilisant un exemple approprié de graphique.
Ci-dessous un exemple de graphique. Nous maintenons une pile pour stocker les nœuds explorés et une liste pour stocker les nœuds visités.
Nous allons commencer par A pour commencer, le marquer comme visité et l'ajouter à la liste visitée. Ensuite, nous allons considérer tous les nœuds adjacents de A et pousser ces nœuds sur la pile comme indiqué ci-dessous.
Ensuite, nous sortons un nœud de la pile, c'est-à-dire B, et le marquons comme visité. Nous l'ajoutons ensuite à la liste des «visités». Ceci est représenté ci-dessous.
Nous considérons maintenant les nœuds adjacents de B qui sont A et C. En dehors de cela, A est déjà visité. Nous l'ignorons donc. Ensuite, nous sortons C de la pile. Mark C comme visité. Le nœud adjacent de C, c'est-à-dire E, est ajouté à la pile.
Ensuite, nous sortons le nœud E suivant de la pile et le marquons comme visité. Le nœud adjacent du nœud E est C qui est déjà visité. Nous l'ignorons donc.
Désormais, seul le nœud D reste dans la pile. Nous le marquons donc comme visité. Son nœud adjacent est A qui est déjà visité. Nous ne l'ajoutons donc pas à la pile.
À ce stade, la pile est vide. Cela signifie que nous avons terminé le parcours en profondeur pour le graphe donné.
La liste visitée donne la séquence finale de parcours en utilisant la technique de la profondeur d'abord. La séquence DFS finale pour le graphique ci-dessus est A-> B-> C-> E-> D.
Implémentation DFS
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list[]; // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList[v]; for (int i=0; i Production:
Applications de DFS
# 1) Détecter un cycle dans un graphique: DFS facilite la détection d'un cycle dans un graphique lorsque nous pouvons revenir en arrière vers une arête.
# 2) Recherche de chemin: Comme nous l'avons déjà vu dans l'illustration DFS, étant donné deux sommets quelconques, nous pouvons trouver le chemin entre ces deux sommets.
# 3) Minimum arbre couvrant et chemin le plus court: Si nous exécutons la technique DFS sur le graphe non pondéré, cela nous donne le spanning tree minimum et le chemin raccourci.
# 4) Tri topologique: Le tri topologique est utilisé lorsque nous devons planifier les travaux. Nous avons des dépendances entre divers emplois. Nous pouvons également utiliser le tri topologique pour résoudre les dépendances entre les éditeurs de liens, les ordonnanceurs d'instructions, la sérialisation des données, etc.
Traversée en largeur d'abord
La technique BFS (Breadth-first) utilise une file d'attente pour stocker les nœuds du graphe. Contrairement à la technique DFS, dans BFS, nous parcourons le graphe dans le sens de la largeur. Cela signifie que nous traversons le niveau du graphique. Lorsque nous explorons tous les sommets ou nœuds à un niveau, nous passons au niveau suivant.
Vous trouverez ci-dessous un algorithme pour la technique de traversée en largeur d'abord .
Algorithme
Voyons l’algorithme de la technique BFS.
Étant donné un graphe G pour lequel nous devons effectuer la technique BFS.
- Étape 1: Commencez par le nœud racine et insérez-le dans la file d'attente.
- Étape 2: Répétez les étapes 3 et 4 pour tous les nœuds du graphique.
- Étape 3: Supprimez le nœud racine de la file d'attente et ajoutez-le à la liste Visité.
- Étape 4: Ajoutez maintenant tous les nœuds adjacents du nœud racine à la file d'attente et répétez les étapes 2 à 4 pour chaque nœud. [END OF LOOP]
- Étape 6: SORTIR
Illustration de BFS
Illustrons la technique BFS à l'aide d'un exemple de graphique ci-dessous. Notez que nous avons conservé une liste nommée 'Visité' et une file d'attente. Nous utilisons le même graphique que nous avons utilisé dans l'exemple DFS à des fins de clarté.
Tout d'abord, nous commençons par root, c'est-à-dire le nœud A et l'ajoutons à la liste visitée. Tous les nœuds adjacents du nœud A, c'est-à-dire B, C et D sont ajoutés à la file d'attente.
Ensuite, nous supprimons le nœud B de la file d'attente. Nous l'ajoutons à la liste Visité et le marquons comme visité. Ensuite, nous explorons les nœuds adjacents de B dans la file d'attente (C est déjà dans la file d'attente). Un autre nœud A adjacent est déjà visité, nous l'ignorons donc.
Ensuite, nous supprimons le nœud C de la file d'attente et le marquons comme visité. Nous ajoutons C à la liste visitée et son nœud adjacent E est ajouté à la file d'attente.
Ensuite, nous supprimons D de la file d'attente et le marquons comme visité. Le nœud A adjacent du nœud D est déjà visité, nous l’ignorons donc.
Alors maintenant, seul le nœud E est dans la file d'attente. Nous le marquons comme visité et l'ajoutons à la liste visitée. Le nœud adjacent de E est C qui est déjà visité. Alors ignorez-le.
À ce stade, la file d'attente est vide et la liste visitée a la séquence que nous avons obtenue à la suite de la traversée BFS. La séquence est, A-> B-> C-> D-> E.
Implémentation BFS
Le programme Java suivant montre l'implémentation de la technique BFS.
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list[]; //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList[v]; for (int i=0; i Production:
Applications de BFS Traversal
# 1) Collecte des ordures: L’un des algorithmes utilisés par la technique du garbage collection pour copier le garbage collection est «l’algorithme de Cheney». Cet algorithme utilise une technique de traversée en largeur d'abord.
# 2) Diffusion dans les réseaux: La diffusion de paquets d'un point à un autre dans un réseau se fait selon la technique BFS.
# 3) Navigation GPS: Nous pouvons utiliser la technique BFS pour trouver des nœuds adjacents lors de la navigation à l'aide du GPS.
# 4) Sites Web de réseautage social: La technique BFS est également utilisée dans les sites Web de réseautage social pour trouver le réseau de personnes entourant une personne en particulier.
# 5) Chemin le plus court et arbre couvrant minimum dans un graphique non pondéré: Dans le graphe non pondéré, la technique BFS peut être utilisée pour trouver un arbre couvrant minimum et le chemin le plus court entre les nœuds.
Bibliothèque de graphes Java
Java n'oblige pas les programmeurs à toujours implémenter les graphiques dans le programme. Java fournit de nombreuses bibliothèques prêtes à l'emploi qui peuvent être directement utilisées pour utiliser des graphiques dans le programme. Ces bibliothèques disposent de toutes les fonctionnalités de l'API graphique requises pour utiliser pleinement le graphique et ses diverses fonctionnalités.
Vous trouverez ci-dessous une brève introduction à certaines des bibliothèques de graphes en Java.
# 1) Google Guava: Google Guava fournit une bibliothèque riche qui prend en charge les graphiques et les algorithmes, y compris les graphiques simples, les réseaux, les graphiques de valeur, etc.
# 2) Apache Commons: Apache Commons est un projet Apache qui fournit des composants de structure de données Graph et des API qui ont des algorithmes qui fonctionnent sur cette structure de données graphiques. Ces composants sont réutilisables.
# 3) JGraphT: JGraphT est l'une des bibliothèques de graphes Java largement utilisées. Il fournit des fonctionnalités de structure de données graphiques contenant un graphique simple, un graphique dirigé, un graphique pondéré, etc. ainsi que des algorithmes et des API qui fonctionnent sur la structure de données graphiques.
# 4) SourceForge JUNG: JUNG signifie «Java Universal Network / Graph» et est un framework Java. JUNG fournit un langage extensible pour l'analyse, la visualisation et la modélisation des données que nous voulons représenter sous forme de graphique.
JUNG fournit également divers algorithmes et routines pour la décomposition, le clustering, l'optimisation, etc.
Questions fréquemment posées
Q # 1) Qu'est-ce qu'un graphique en Java?
Répondre: Une structure de données graphique stocke principalement des données connectées, par exemple, un réseau de personnes ou un réseau de villes. Une structure de données de graphe se compose généralement de nœuds ou de points appelés sommets. Chaque sommet est connecté à un autre sommet à l'aide de liens appelés arêtes.
Q # 2) Quels sont les types de graphiques?
Répondre: Différents types de graphiques sont répertoriés ci-dessous.
- Graphique linéaire: Un graphique linéaire est utilisé pour tracer les changements dans une propriété particulière par rapport au temps.
- Graphique à barres: Les graphiques à barres comparent les valeurs numériques d'entités telles que la population de diverses villes, les pourcentages d'alphabétisation à travers le pays, etc.
En dehors de ces types principaux, nous avons également d'autres types comme le pictogramme, l'histogramme, le graphique en aires, le nuage de points, etc.
Q # 3) Qu'est-ce qu'un graphe connecté?
Répondre: Un graphe connecté est un graphe dans lequel chaque sommet est connecté à un autre sommet. Par conséquent, dans le graphe connecté, nous pouvons accéder à tous les sommets à partir de tous les autres sommets.
Q # 4) Quelles sont les applications du graphe?
Répondre: Les graphiques sont utilisés dans une variété d'applications. Le graphique peut être utilisé pour représenter un réseau complexe. Les graphiques sont également utilisés dans les applications de réseautage social pour désigner le réseau de personnes ainsi que pour des applications telles que la recherche de personnes ou de connexions adjacentes.
Les graphiques sont utilisés pour désigner le flux de calcul en informatique.
Q # 5) Comment stockez-vous un graphique?
Réponse: Il existe trois façons de stocker un graphique en mémoire:
#1) Nous pouvons stocker des nœuds ou des sommets comme des objets et des arêtes comme des pointeurs.
#deux) Nous pouvons également stocker des graphiques sous forme de matrice de contiguïté dont les lignes et les colonnes sont identiques au nombre de sommets. L'intersection de chaque ligne et colonne indique la présence ou l'absence d'une arête. Dans le graphe non pondéré, la présence d'une arête est notée 1 tandis que dans le graphe pondéré elle est remplacée par le poids de l'arête.
# 3) La dernière approche pour stocker un graphe consiste à utiliser une liste de contiguïté d'arêtes entre les sommets ou les nœuds du graphe. Chaque nœud ou sommet a sa liste de contiguïté.
Conclusion
Dans ce didacticiel, nous avons discuté en détail des graphiques en Java. Nous avons exploré les différents types de graphes, l'implémentation de graphes et les techniques de parcours. Les graphiques peuvent être utilisés pour trouver le chemin le plus court entre les nœuds.
Dans nos prochains didacticiels, nous continuerons d'explorer les graphiques en discutant de quelques façons de trouver le chemin le plus court.
=> Regardez la série de formation Java simple ici.
lecture recommandée
- Tutoriel de réflexion Java avec des exemples
- Comment implémenter l'algorithme de Dijkstra en Java
- Tutoriel Java SWING: Conteneur, composants et gestion des événements
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
- TreeMap en Java - Tutoriel avec des exemples de TreeMap Java
- Modificateurs d'accès en Java - Tutoriel avec des exemples
- Tutoriel Java String with String Buffer et String Builder
- Tutoriel sur la méthode Java String contains () avec des exemples