Ajouter un sommet
Leçon 4 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Un sommet est un point unique dans le graphe. En ajouter un signifie enregistrer sa clé dans la map vertices avec une liste de voisins vide : il existe, mais n'a pas encore de connexions.
Si la clé est déjà dans la map, ne faites rien. Nous ne voulons pas effacer les voisins existants d'un sommet simplement parce que quelqu'un a appelé addVertex dessus deux fois. Ce genre de comportement idempotent rend la méthode sûre à appeler depuis addEdge plus tard.
Écrivons-le.
Défi
FacileAjoutez une méthode addVertex à la classe Graph.
Elle prend un entier key et :
- Si
keyn'est pas dansvertices, ajoutez-le avec une liste de voisins vide. - Si
keyest déjà dansvertices, ne faites rien.
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)); }
}
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