Obtenir les voisins
Leçon 7 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Les algorithmes comme BFS, DFS et le plus court chemin ne regardent pas la carte brute : ils demandent « quels sont les voisins de ce sommet ? » et parcourent la réponse. Notre méthode getNeighbors expose cela.
Si le sommet est dans le graphe, retournez sa liste de voisins. Retournez une copie si vous voulez que les appelants modifient le résultat sans casser le graphe (c'est une bonne habitude). Si le sommet n'existe pas, retournez une liste vide plutôt que de planter. Cela simplifie le code client : il peut toujours itérer sur le résultat.
Défi
FacileAjoutez une méthode getNeighbors à la classe Graph.
Elle prend un entier key et renvoie une liste de ses voisins :
- Si
keyest présent dansvertices, renvoyez sa liste de voisins (une copie convient). - Si
keyn'est pas dans le graphe, renvoyez une liste vide.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
static int _cmp_int(const void* a, const void* b) {
int ai = *(const int*)a, bi = *(const int*)b;
return (ai > bi) - (ai < bi);
}
int main() {
Graph g;
Graph_init(&g);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "verticesEmpty") == 0) { printf("%s\n", g.vertexCount == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Graph_indexOf(&g, atoi(arg)) != -1 ? "true" : "false"); }
if (strcmp(cmd, "addVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Graph_addVertex(&g, atoi(arg)); }
if (strcmp(cmd, "addEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_addEdge(&g, atoi(a1), atoi(a2)); }
if (strcmp(cmd, "degree") == 0) {
char* arg = strtok(NULL, " \t");
if (arg) {
int k = atoi(arg);
int ki = Graph_indexOf(&g, k);
printf("%d\n", ki == -1 ? 0 : g.vertices[ki].n);
}
}
if (strcmp(cmd, "hasEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) printf("%s\n", Graph_hasEdge(&g, atoi(a1), atoi(a2)) ? "true" : "false"); }
if (strcmp(cmd, "neighbors") == 0) {
char* arg = strtok(NULL, " \t");
if (arg) {
int buf[MAX_NEIGHBORS];
int n = Graph_getNeighbors(&g, atoi(arg), buf);
qsort(buf, n, sizeof(int), _cmp_int);
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", buf[i]);
}
printf("\n");
}
}
}
return 0;
}
Toutes les leçons de Graphes - Série Structures de données n°9
2Projet Graphe
Classe GrapheAjouter un sommetAjouter une arêtePossède une arêteObtenir les voisinsSupprimer une arêteTaille