Kenar Ekle
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 5 / 14.
Bir kenar iki köşeyi birbirine bağlar. Grafımız yönsüz olduğu için bağlantı her iki yöne de gider: eğer u ve v bağlıysa, u, v'nin komşu listesinde görünür ve v de u'nun listesinde görünür.
Herhangi bir bağlantı yapmadan önce, her biri üzerinde addVertex çağırarak her iki köşenin de var olduğundan emin olun (zaten varlarsa bu işlem bir şey yapmaz). Ardından her birini diğerinin komşu listesine ekleyin. Kenar zaten oradaysa mükerrer bir ekleme yapmaktan kaçının. Kendi kendine döngü (u == v) durumunda, onu yalnızca bir kez ekleyin.
Şimdi bunu yazalım.
Görev
KolayGraph sınıfına bir addEdge metodu ekleyin.
Bu metot u ve v adında iki tam sayı alır ve bunları her iki yönde birbirine bağlar:
- Hem
uhem dev'nin mevcut olduğundan emin olun (mevcut değilseaddVertexkullanın). v'yiu'nun komşu listesine ekleyin (yalnızca zaten orada değilse).u'yuv'nin komşu listesine ekleyin (yalnızca zaten orada değilse). Eğeru == vise, ikinci kez eklemeyin.
Kendin dene
#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;
}