Représenter des graphiques

Représenter un graphe, c'est stocker ses sommets et ses arêtes dans un programme. La structure de données pour stocker un graphique est constituée de tableaux ou de listes. Pour écrire un programme qui traite et manipule des graphiques, vous devez stocker ou représenter les données des graphiques dans l'ordinateur.

Représenter les sommets

Les sommets peuvent être stockés dans un tableau ou une liste. Par exemple, vous pouvez stocker tous les noms de villes dans le graphique de la figure ci-dessous en utilisant le tableau suivant :

String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", " Miami", "Dallas", "Houston"};

Les sommets peuvent être des objets de n'importe quel type. Par exemple, vous pouvez considérer les villes comme des objets contenant des informations telles que leur nom, leur population et leur maire. Ainsi, vous pouvez définir les sommets comme suit :

City city0 = new City("Seattle", 608660, "Mike McGinn");
...
Ville city11 = nouvelle ville("Houston", 2099451, "Annise Parker");
Ville[] sommets = {ville0, ville1, ... , ville11};

classe publique Ville {
chaîne privée cityName ;
population internationale privée ;
maire de String privé;

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

Les sommets peuvent être facilement étiquetés en utilisant les nombres naturels 0, 1, 2, ..., n - 1, pour un graphique pour n sommets. Ainsi, vertices[0] représente "Seattle", vertices[1] représente "San Francisco", et ainsi de suite, comme illustré dans la figure ci-dessous.

Vous pouvez référencer un sommet par son nom ou son index, selon ce qui vous convient le mieux. Évidemment, il est facile d'accéder à un sommet via son index dans un programme.

Représentation des bords : tableau de bords

Les bords 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 28.1 en utilisant le tableau suivant :

int[][] bords = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

Cette représentation est connue sous le nom de tableau de bords. Les sommets et les arêtes de la figure ci-dessous (a) peuvent être représentés comme suit :

String[] noms = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
int[][] bords = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

Représentation des bords : objets Edge

Une autre façon de représenter les bords est de définir les bords en tant qu'objets et de stocker les bords dans une java.util.ArrayList. La classe Edge peut être définie comme suit :

classe publique Edge {
int toi;
int v;
public Edge (int u, int v) {
ceci.u = u;
ceci.v = v;
>
public booléen égal(Objet o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
>
>

Par exemple, vous pouvez stocker toutes les arêtes du graphique de la figure ci-dessous en utilisant la liste suivante :

java.util.ArrayList list = nouveau java.util.ArrayList<>();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

Stocker des objets Edge dans une ArrayList est utile si vous ne connaissez pas les bords à l'avance.

Bien que représenter les bords à l'aide d'un tableau de bords ou d'objets Edge dans la section précédente (Représenter les bords : Tableau de bords) et plus tôt dans cette section peut être intuitif pour la saisie, ce n'est pas efficace pour traitement interne. Les deux sections suivantes présentent la représentation des graphiques à l'aide de matrices d'adjacence et de listes d'adjacence. Ces deux structures de données sont efficaces pour le traitement des graphiques.

Représentation des bords : matrices de contiguïté

Supposons que le graphe ait n sommets. Vous pouvez utiliser une matrice n * n bidimensionnelle, disons adjacencyMatrix, pour représenter les arêtes. Chaque élément du tableau est 0 ou 1. adjacencyMatrix[i][j] vaut 1 s'il y a une arête du sommet i au sommet j ; sinon, adjacencyMatrix[i][j] vaut 0. Si le graphique n'est pas orienté, la matrice est symétrique, car adjacencyMatrix[i][j] est la même que adjacencyMatrix[j][i]. Par exemple, les arêtes du graphique de la figure ci-dessous peuvent être représentées à l'aide d'une matrice de contiguïté comme suit :

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston
};

Étant donné que la matrice est symétrique pour un graphe non orienté, pour économiser de l'espace de stockage, vous pouvez utiliser un tableau irrégulier.

La matrice de contiguïté pour le graphe orienté de la figure ci-dessous (a) peut être représentée comme suit :

int[][] a = {{0, 0, 1, 0, 0}, // Pierre
{0, 0, 1, 0, 0}, // Jeanne
{0, 0, 0, 0, 1}, // Marque
{0, 0, 0, 0, 1}, // Cindy
{0, 0, 0, 0, 0} // Wendy
};

Représentation des arêtes : listes de contiguïté

Vous pouvez représenter les arêtes à l'aide de listes de sommets de contiguïté ou de listes d'arêtes de contiguïté. Une liste de sommets de contiguïté pour un sommet i contient les sommets adjacents à i et une liste d'arêtes de contiguïté pour un sommet i contient les arêtes adjacentes à i. Vous pouvez définir un tableau de listes. Le
le tableau a n entrées, et chaque entrée est une liste. La liste des sommets de contiguïté pour le sommet i contient tous les sommets j tels qu'il y a une arête du sommet i au sommet j. Par exemple, pour représenter les arêtes dans le graphique de la figure ci-dessous, vous pouvez créer un tableau de listes comme suit :

java.util.List[] voisins = new java.util.List[12];

neighbours[0] contient tous les sommets adjacents au sommet 0 (c'est-à-dire Seattle), neighbours[1] contient tous les sommets adjacents au sommet 1 (c'est-à-dire San Francisco), et ainsi de suite, comme le montre la figure ci-dessous.

Pour représenter les listes de bords de contiguïté pour le graphique de la figure ci-dessous, vous pouvez créer un tableau de listes comme suit :

java.util.List[] voisins = new java.util.List[12];

neighbours[0] contient toutes les arêtes adjacentes au sommet 0 (c'est-à-dire Seattle), neighbours[1] contient toutes les arêtes adjacentes au sommet 1 (c'est-à-dire San Francisco), et ainsi de suite, comme le montre la figure ci-dessous.

Vous pouvez représenter un graphique à l'aide d'une matrice de contiguïté ou de listes de contiguïté. Lequel est le meilleur ? Si le graphe est dense (c’est-à-dire qu’il y a beaucoup d’arêtes), il est préférable d’utiliser une matrice de contiguïté. Si le graphique est très clairsemé (c'est-à-dire très peu d'arêtes), il est préférable d'utiliser des listes de contiguïté, car l'utilisation d'une matrice de contiguïté gaspillerait beaucoup d'espace.

Les matrices de contiguïté et les listes de contiguïté peuvent être utilisées dans un programme pour rendre les algorithmes plus efficaces. Par exemple, il faut un temps constant O(1) pour vérifier si deux sommets sont connectés à l'aide d'une matrice de contiguïté, et il faut un temps linéaire O(m) pour imprimer toutes les arêtes d'un graphe à l'aide de listes de contiguïté, où m est le nombre d'arêtes. .

La liste des sommets de contiguïté est plus simple pour représenter des graphiques non pondérés. Cependant, les listes de bords de contiguïté sont plus flexibles pour une large gamme d'applications graphiques. Il est facile d’ajouter des contraintes supplémentaires sur les arêtes à l’aide de listes d’arêtes de contiguïté. Pour cette raison, ce livre utilisera des listes de bords de contiguïté pour représenter les graphiques.

Vous pouvez utiliser des tableaux, des listes de tableaux ou des listes chaînées pour stocker des listes de contiguïté. Nous utiliserons des listes au lieu de tableaux, car les listes sont facilement extensibles pour vous permettre d'ajouter de nouveaux sommets. De plus, nous utiliserons des listes de tableaux au lieu de listes chaînées, car nos algorithmes nécessitent uniquement la recherche de sommets adjacents dans la liste. L'utilisation de listes de tableaux est plus efficace pour nos algorithmes. À l'aide de listes de tableaux, la liste de bords de contiguïté dans la figure ci-dessous peut être construite comme suit :

Liste> voisins = new ArrayList<>();
voisins.add(new ArrayList());
voisins.get(0).add(new Edge(0, 1));
voisins.get(0).add(new Edge(0, 3));
voisins.get(0).add(new Edge(0, 5));
voisins.add(new ArrayList());
voisins.get(1).add(new Edge(1, 0));
voisins.get(1).add(new Edge(1, 2));
voisins.get(1).add(new Edge(1, 3));
...
...
voisins.get(11).add(new Edge(11, 8));
voisins.get(11).add(new Edge(11, 9));
voisins.get(11).add(new Edge(11, 10));

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!