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.
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.
import java.util.arraylist;
import java.util.linkedlist;
classe publique Amwgraph {
Private ArrayList Vertexlist;
// La table de liaison des points de stockage
Entreaux privés [] [];
// Adresse Matrice, utilisé pour stocker les bords
Int numofedges privé;
// Nombre de bords
Amwgraph public (int n) {
// initialise la matrice, le tableau unidimensionnel et le nombre de bords
EDGES = NOUVEAU INT [N] [N];
vertexList = new ArrayList (n);
numofedges = 0;
}
// Obtenez le nombre de nœuds
public int getnumofvertex () {
return vertexList.size ();
}
// Obtenez le nombre d'arêtes
public int getNumOfedges () {
retour numofedges;
}
// Renvoie les données du nœud I
objet public getValueByIndex (int i) {
return vertexList.get (i);
}
// retourne le poids de v1 et v2
public int getweight (int v1, int v2) {
Return Adges [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) {
Arêtes [V1] [V2] = poids;
numofedges ++;
}
// Supprimer le nœud
public void Deleteedge (int v1, int v2) {
EDGES [V1] [V2] = 0;
numofedges--;
}
// Obtenez l'indice du premier nœud adjacent
public int getFirstneighbor (int index) {
pour (int j = 0; j <vertexList.size (); j ++) {
if (arêtes [index] [j]> 0) {
retour j;
}
}
retour -1;
}
// Obtenez 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) {
pour (int j = v2 + 1; j <vertexList.size (); j ++) {
if (arêtes [v1] [j]> 0) {
retour j;
}
}
retour -1;
}
}Jetons un coup d'œil au code qui implémente la matrice d'adjacence pour représenter des graphiques denses:
package com.datastructure.graph;
///// Graphique dense - Utilisez la matrice d'adjacence pour représenter
// classe publique densegraph {
//
// private int n; // Nombre de nœuds
// private int m; // Numéro de bord
// Boolean privé dirigé; // est-ce un graphique dirigé
// Boolean privé [] [] g; // Données spécifiques de l'image
//
// // constructeur
// public densegraph (int n, booléen dirigé) {
// affirme n> = 0;
// this.n = n;
// this.m = 0; // L'initialisation n'a pas de bords
// this.directed = dirigé;
// // g est initialisé dans une matrice booléenne de n * n. Chaque g [i] [j] est faux, indiquant qu'il n'y a pas de bords.
// // false est la valeur par défaut de la variable de type booléen
// g = new Boolean [n] [n];
//}
//
// public int v () {
// retour n;
//} // Renvoie le nombre de nœuds
//
// public int e () {
// retour m;
//} // Renvoie le nombre de bords
//
// // ajouter un bord au graphique
// public void addge (int v, int w) {
//
// affirme v> = 0 && v <n;
// affirme w> = 0 && w <n;
//
// if (Hasedge (v, w))
// retour;
//
// // Connect V et W
// g [v] [w] = true;
// if (! dirigé)
// g [w] [v] = true;
//
// // Nombre d'arêtes ++
// m ++;
//}
//
// // Vérifiez s'il y a des arêtes de V à W dans le graphique
// boolean hasedge (int v, int w) {
// affirme v> = 0 && v <n;
// affirme w> = 0 && w <n;
// retourne g [v] [w];
//}
//
// // Renvoie tous les voisins d'un sommet dans le graphique
// // Étant donné que Java utilise un mécanisme de référence, le retour d'un vecteur n'apportera aucune surcharge supplémentaire.
// public itérable <Integer> adj (int v) {
// affirme v> = 0 && v <n;
// vector <nteger> adjv = new vector <nteger> ();
// pour (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// retour adjv;
//}
//}
import java.util.arraylist;
Importer java.util.list;
// Utiliser la matrice d'adjacence pour représenter des graphiques denses
classe publique densegraph {
Int n privé;
// Nombre de nœuds sur la figure
Int m;
// Nombre d'arêtes sur l'image
booléen privé [] [] g;
// matrice adjacente G
Boolean privé dirigé;
// est-ce un graphique dirigé
public densegraph (int n, booléen dirigé) {
this.n = n;
// le nombre de nœuds dans le graphique d'initialisation
this.m = 0;
// Le nombre de bords sur la figure est initialisé à 0
this.directed = dirigé;
g = nouveau booléen [n] [n];
// La matrice d'adjacence G est initialisée dans une matrice bidimensionnelle de n * n
// L'indice représente le nœud dans le graphique, et la valeur stockée dans G est de savoir si le nœud a des bords
}
// Renvoie le nombre de bords dans le graphique
public int e () {
retour m;
}
// renvoie le nombre de nœuds dans le graphique
public int v () {
retour n;
}
// ajoute des bords entre les deux nœuds spécifiés sur la figure
public void addge (int v, int w) {
if (! HasEdge (v, w)) {
// connecter [v] [w]
g [v] [w] = true;
// graphique non dirigé
si (!
g [w] [v] = true;
// le nombre de côtés dans l'image +1
m ++;
}
}
// déterminer s'il y a des bords entre les deux nœuds
Boolean privé HasEdge (int v, int w) {
retour g [v] [w];
}
// Renvoie les nœuds d'adjacence de tous les nœuds V
public iTable <Integer> AdjacentNode (int v) {
// Adjacentl est utilisé pour stocker le nœud adjacent de V
List <Integer> adjacentl = new ArrayList <> ();
// Trouvez tous les nœuds adjacents à V et ajoutez-les à adjacentl
pour (int i = 0; i <n; i ++) {
if (g [v] [i])
Adjacentl.add (i);
}
retour adjacentl;
}
}
Résumer
Ce qui précède est tout le contenu de cet article sur la programmation Java pour implémenter l'exemple de code de la représentation de graphe dense de la matrice d'adjacence, et j'espère que cela sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à ce site:
Analyse des concepts de base et des exemples de code de l'arbre de structure de données Java
Questions d'entrevue de structure de données communes Java (avec des réponses)
Principe d'algorithme d'algorithme de correspondance multimode et code d'implémentation Java
S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!