Hat Kante
Lektion 6 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Die einfachste Frage, die man einem Graphen stellen kann, ist: „Sind diese beiden Knoten verbunden?“. Mit unserer Adjazenzliste besteht die Antwort aus einer Map-Abfrage plus einem Listenscan: schlagen Sie die Nachbarn von u nach und prüfen Sie, ob v in dieser Liste enthalten ist.
Wenn u gar nicht im Graphen vorhanden ist, gibt es keine Liste zum Scannen, geben Sie also false zurück. Da addEdge die Verbindung in beide Richtungen hergestellt hat, müssen Sie nur eine Seite prüfen: wenn v in den Nachbarn von u ist, dann ist u konstruktionsbedingt auch in denen von v.
Schreiben Sie es jetzt.
Aufgabe
EinfachFügen Sie der Klasse Graph eine Methode hasEdge hinzu.
Sie nimmt zwei Ganzzahlen u und v entgegen und gibt true zurück, wenn eine Kante zwischen ihnen besteht, andernfalls false.
Wenn u nicht in vertices enthalten ist, geben Sie false zurück. Geben Sie andernfalls zurück, ob v in der Nachbarliste von u enthalten ist.
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"); }
}
return 0;
}
Alle Lektionen in Graphen - Datenstrukturen-Serie #9
2Graph-Projekt
Graph-KlasseKnoten hinzufügenKante hinzufügenHat KanteNachbarn abrufenKante entfernenGröße