Kante hinzufügen
Lektion 5 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Eine Kante verbindet zwei Knoten. Da unser Graph ungerichtet ist, besteht die Verbindung in beide Richtungen: wenn u und v verbunden sind, erscheint u in der Nachbarliste von v und v erscheint in der von u.
Bevor Sie etwas verbinden, stellen Sie sicher, dass beide Knoten existieren, indem Sie addVertex für jeden aufrufen (dies ist wirkungslos, wenn sie bereits existieren). Fügen Sie dann jeden zur Nachbarliste des jeweils anderen hinzu. Überspringen Sie ein doppeltes Hinzufügen, wenn die Kante bereits vorhanden ist. Fügen Sie eine Selbstschleife (u == v) nur einmal hinzu.
Schreiben wir es nun auf.
Aufgabe
EinfachFügen Sie der Klasse Graph eine Methode addEdge hinzu.
Sie nimmt zwei Ganzzahlen u und v entgegen und verbindet diese in beide Richtungen:
- Stellen Sie sicher, dass sowohl
uals auchvexistieren (verwenden SieaddVertex, falls nicht). - Fügen Sie
vzur Nachbarliste vonuhinzu (nur wenn es dort noch nicht vorhanden ist). - Fügen Sie
uzur Nachbarliste vonvhinzu (nur wenn es dort noch nicht vorhanden ist). Wennu == vist, fügen Sie es kein zweites Mal hinzu.
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);
}
}
}
return 0;
}
Alle Lektionen in Graphen - Datenstrukturen-Serie #9
2Graph-Projekt
Graph-KlasseKnoten hinzufügenKante hinzufügenHat KanteNachbarn abrufenKante entfernenGröße