Représenter des graphiques pondérés

Les bords pondérés peuvent être stockés dans des listes de contiguïté.

Il existe deux types de graphiques pondérés : pondérés par les sommets et pondérés par les bords. Dans un graphique pondéré par les sommets, chaque sommet se voit attribuer un poids. Dans un graphique pondéré par les arêtes, chaque arête se voit attribuer un poids. Parmi les deux types, les graphiques pondérés par les bords ont plus d’applications. Ce chapitre considère les graphiques pondérés par les bords.

Les graphiques pondérés peuvent être représentés de la même manière que les graphiques non pondérés, sauf qu'il faut représenter les poids sur les bords. Comme pour les graphiques non pondérés, les sommets des graphiques pondérés peuvent être stockés dans un tableau. Cette section présente trois représentations des arêtes dans les graphiques pondérés.

Représentation des arêtes pondérées : tableau d'arêtes

Les bords pondérés peuvent être représentés à l'aide d'un tableau bidimensionnel. Par exemple, vous pouvez stocker toutes les arêtes du graphique de la figure ci-dessous (a) en utilisant le tableau de la figure ci-dessous (b).

Les poids peuvent être de n'importe quel type : Integer, Double, BigDecimal, etc. Vous pouvez utiliser un tableau bidimensionnel de type Object pour représenter les arêtes pondérées comme suit :

Objet[][] bords = {
{nouveau Integer(0), nouveau Integer(1), nouveau SomeTypeForWeight(2)},
{nouveau Integer(0), nouveau Integer(3), nouveau SomeTypeForWeight(8)},
...
};

Matrices de contiguïté pondérées

Supposons que le graphe ait n sommets. Vous pouvez utiliser une matrice n * n bidimensionnelle, disons poids, pour représenter les poids sur les bords. weights[i][j] représente le poids sur le bord (i, j). Si les sommets i et j ne sont pas connectés, weights[i][j] est null. Par exemple, les poids dans le graphique de la figure ci-dessus (a) peuvent être représentés à l'aide d'une matrice de contiguïté comme suit :

Listes de contiguïté

Une autre façon de représenter les bords consiste à définir les bords en tant qu'objets. La classe AbstractGraph.Edge a été définie pour représenter une arête non pondérée dans AbstractGraph.java. Pour les bords pondérés, nous définissons la classe WeightedEdge comme indiqué dans le code ci-dessous.

AbstractGraph.Edge est une classe interne définie dans la classe AbstractGraph. Il représente une arête du sommet u à v. WeightedEdge étend AbstractGraph.Edge avec une nouvelle propriété weight.

Pour créer un objet WeightedEdge, utilisez new WeightedEdge(i, j, w), où w est le poids sur le bord (i , j). Il est souvent nécessaire de comparer les poids des bords. Pour cette raison, la classe WeightedEdge implémente l'interface Comparable.

Pour les graphiques non pondérés, nous utilisons des listes de contiguïté pour représenter les arêtes. Pour les graphiques pondérés, nous utilisons toujours des listes de contiguïté, les listes de contiguïté pour les sommets du graphique de la figure ci-dessous a peuvent être représentées comme suit :

java.util.List[] list = new java.util.List[5];

list[i] stocke toutes les arêtes adjacentes au sommet i.

Pour plus de flexibilité, nous utiliserons une liste de tableaux plutôt qu'un tableau de taille fixe pour représenter list comme suit :

Liste> list = nouveau java.util.ArrayList<>();

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!