Classe Graphe
Leçon 3 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
La classe Graph est construite autour d'un seul champ, vertices, qui est la liste d'adjacence : une map associant chaque clé de sommet à la liste de ses voisins. Chaque opération que nous ajouterons plus tard (ajouter des arêtes, lister les voisins, supprimer des arêtes) n'est qu'une petite modification de cette map.
Le constructeur initialise le graphe dans son état vide : aucun sommet, aucune arête. Ainsi, la map est simplement une map vide. Les méthodes que nous ajouterons dans les prochaines leçons la feront croître.
Défi
FacileÉcrivez une classe Graph avec un constructor qui ne prend aucun paramètre d'entrée.
Initialisez un champ unique vertices comme une empty map (ou l'équivalent dans votre langage d'une map d'adjacence de type clé-vers-liste).
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"); }
}
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