Nachbarn abrufen
Lektion 7 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Algorithmen wie BFS, DFS und der kürzeste Pfad schauen sich nicht die Rohdaten der Karte an: Sie fragen: „Was sind die Nachbarn dieses Knotens?“ und durchlaufen das Ergebnis. Unsere Methode getNeighbors stellt dies bereit.
Wenn sich der Knoten im Graphen befindet, geben Sie seine Nachbarliste zurück. Geben Sie eine Kopie zurück, wenn Sie möchten, dass Aufrufer das Ergebnis verändern können, ohne den Graphen zu beschädigen (das ist eine gute Gewohnheit). Wenn der Knoten nicht existiert, geben Sie eine leere Liste zurück, anstatt abzustürzen. Das hält den Client-Code einfach: Er kann das Ergebnis immer iterieren.
Aufgabe
EinfachFügen Sie der Klasse Graph eine Methode getNeighbors hinzu.
Sie nimmt eine Ganzzahl key entgegen und gibt eine Liste ihrer Nachbarn zurück:
- Wenn
keyinverticesvorhanden ist, geben Sie die Liste der Nachbarn zurück (eine Kopie ist in Ordnung). - Wenn
keynicht im Graphen vorhanden ist, geben Sie eine leere Liste zurück.
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)); }
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;
}
Alle Lektionen in Graphen - Datenstrukturen-Serie #9
2Graph-Projekt
Graph-KlasseKnoten hinzufügenKante hinzufügenHat KanteNachbarn abrufenKante entfernenGröße