Knoten hinzufügen
Lektion 4 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Ein Knoten (Vertex) ist ein einzelner Punkt im Graphen. Einen hinzuzufügen bedeutet, seinen Schlüssel in der vertices-Map mit einer leeren Nachbarliste zu registrieren: Er existiert, hat aber noch keine Verbindungen.
Wenn der Schlüssel bereits in der Map vorhanden ist, tun Sie nichts. Wir wollen die vorhandenen Nachbarn eines Knotens nicht löschen, nur weil jemand addVertex zweimal dafür aufgerufen hat. Diese Art von idempotentem Verhalten macht die Methode sicher für den späteren Aufruf aus addEdge.
Schreiben wir es.
Aufgabe
EinfachFügen Sie der Klasse Graph eine Methode addVertex hinzu.
Sie nimmt eine Ganzzahl key entgegen und:
- Falls
keynicht inverticesvorhanden ist, fügen Sie ihn mit einer leeren Nachbarliste hinzu. - Falls
keybereits inverticesvorhanden ist, tun Sie nichts.
Probier es selbst
#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;
}
Alle Lektionen in Graphen - Datenstrukturen-Serie #9
2Graph-Projekt
Graph-KlasseKnoten hinzufügenKante hinzufügenHat KanteNachbarn abrufenKante entfernenGröße