Structure de stockage
Pour stocker un graphique, nous savons que le graphique a à la fois des nœuds et des bords. Pour un graphique alimenté, chaque bord a également une valeur de poids. Il existe deux principaux types de structures de stockage de graphiques couramment utilisées:
Matrice adjacente table adjacente
Matrice adjacente
Nous savons que pour représenter les nœuds, nous pouvons les représenter avec un tableau unidimensionnel. Cependant, pour la relation entre les nœuds, nous ne pouvons pas simplement les représenter avec un tableau unidimensionnel. Nous pouvons les représenter avec un tableau bidimensionnel, c'est-à-dire une méthode de représentation de formation de matrice.
Nous supposons que A est ce tableau bidimensionnel, puis un élément AIJ dans un non seulement reflète la relation entre le nœud VI et le nœud VJ, mais aussi la valeur de l'AIJ peut représenter la taille du poids.
Voici un exemple de représentation de la matrice d'adjacence d'un graphique non dirigé:
D'après la figure ci-dessus, nous pouvons voir que la matrice d'adjacence du graphique non dirigé est une matrice symétrique et doit être une matrice symétrique. Et la valeur de la diagonale du coin supérieur gauche au coin inférieur droit est nul (la diagonale indique le même nœud)
Quelle est la matrice d'adjacence d'un graphique dirigé?
Pour les graphiques pondérés, la valeur de l'AIJ peut être utilisée pour représenter la taille du poids. Les deux graphiques ci-dessus sont des graphiques sans poids, donc leurs valeurs sont toutes deux 1.
Table adjacente
Nous savons que la méthode de stockage de la matrice d'adjacence du graphique utilise une matrice N * n. Lorsque cette matrice est une matrice dense (par exemple, lorsque le graphique est un graphique complet), bien sûr, la méthode de stockage de la matrice d'adjacence est choisie.
Mais si cette matrice est une matrice clairsemée, la structure de stockage de table adjacente est une structure de stockage plus économique.
Pour le graphique non dirigé ci-dessus, nous pouvons utiliser une table d'adjacence pour le représenter comme suit:
Le nœud connecté à chaque nœud est son nœud adjacent.
Comparaison entre la matrice d'adjacence et la table d'adjacence
Lorsque le nombre de nœuds dans le graphique est petit et qu'il y a de nombreux côtés, l'efficacité de l'utilisation d'une matrice d'adjacence est plus élevée.
Lorsque le nombre de nœuds est très grand et que le nombre de bords est beaucoup plus petit que le nombre de bords du graphique complet du même nœud, il est plus efficace d'adopter une structure de stockage de table d'adjacence.
Implémentation Java de la matrice d'adjacence
Classe de modèle matriciel adjacent
Le nom de classe de la classe de modèle de matrice d'adjacence est amwgraph.java. Il peut construire un graphique représenté par une matrice d'adjacence via cette classe, et fournir des nœuds d'insertion, insérer les bords et obtenir le premier nœud d'adjacence et le nœud d'adjacence suivant d'un certain nœud.
Importer java.util.arraylist; Importer java.util.linkedlist; / ** * @Description Matrix Model Classe * @author beanlam * @time 2015.4.17 * / classe publique Amwgraph {private ArrayList vertexlist; // points de stockage private int [] [] bords; // AMWGRAPH (int n) {// Initialiser la matrice, le tableau unidimensionnel et le nombre de bords EDGES = new int [n] [n]; vertexList = new ArrayList (n); numofedges = 0; } // Obtenez le nombre de nœuds publics int getNumofverTex () {return vertexList.size (); } // Obtenez le nombre d'arêtes publiques int getNumofedges () {return numofedges; } // Renvoie les données de Node i public objet getValueByIndex (int i) {return vertexList.get (i); } // Renvoie le poids de v1, v2 public int getweight (int v1, int v2) {return bords [v1] [v2]; } // insérer le nœud public void insertverTex (objet vertex) {vertexList.add (vertexList.size (), vertex); } // insérer le nœud public void insertEdge (int v1, int v2, int poids) {bords [v1] [v2] = poids; numofedges ++; } // Supprimer le nœud public void DeleteedGE (int v1, int v2) {ardeons [v1] [v2] = 0; numofedges--; } // Obtenez l'index du premier nœud adjacent public int getFirstneighbor (int index) {for (int j = 0; j <vertexList.size (); j ++) {if (edges [index] [j]> 0) {return j; }} return -1; } // Répondre le nœud d'adjacence suivant en fonction de l'indice du nœud d'adjacence précédent public int getNextNeighbor (int v1, int v2) {for (int j = v2 + 1; j <vertexList.size (); j ++) {if (edges [v1] [j]> 0) {return j; }} return -1; }}Test de la classe de modèle de matrice d'adjacence
Ensuite, configurez la classe de modèle de test en fonction du graphique dirigé suivant
Le programme de test testamwgraph.java est le suivant:
/ ** * @description Test Classe de classe Amwgraph * @author beanlam * @time 2015.4.17 * / classe publique TestAmwGraph {public static void main (String args []) {int n = 4, e = 4; // représente le nombre de nœuds et le nombre de bord Identification AMWGraph Graph = new Amwgraph (n); for (String Label: Labels) {graph.InsertverTex (Label); // insérer le nœud} // insérer quatre arêtes Graph.InsertEdge (0, 1, 2); graph.insertEdge (0, 2, 5); Graph.InsertEdge (2, 3, 8); Graph.InsertEdge (3, 0, 7); System.out.println ("Le nombre de nœuds est:" + graph.getNumofverTex ()); System.out.println ("Le nombre de bords est:" + graph.getNumofedges ()); graph.deleteedge (0, 1); // delete <v1, v2> edge system.out.println ("après la suppression <v1, v2> bord ..."); System.out.println ("Le nombre de nœuds est:" + graph.getNumofverTex ()); System.out.println ("Le nombre de bords est:" + graph.getNumofedges ()); }}Les résultats de sortie de la console sont présentés dans la figure ci-dessous:
Résumer
Ce qui précède est tout le contenu de cet article sur la description du langage Java de la structure de stockage et des exemples de code de matrice d'adjacence. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler.