Kenar Var mı
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 6 / 14.
Bir grafa sorulacak en basit soru "bu iki köşe birbirine bağlı mı?" sorusudur. Komşuluk listemizle cevap, bir eşleme (map) araması artı bir liste taramasıdır: u'nun komşularına bakın ve v'nin bu listede olup olmadığını kontrol edin.
Eğer u grafta bile değilse, taranacak bir liste yoktur, bu nedenle false döndürün. addEdge bağlantıyı her iki yönde de kurduğu için, sadece bir tarafı kontrol etmeniz yeterlidir: eğer v, u'nun komşuları arasındaysa, yapı gereği u da v'ninkiler arasındadır.
Şimdi bunu yazın.
Görev
KolayGraph sınıfına bir hasEdge metodu ekleyin.
Bu metot u ve v adında iki tam sayı alır ve aralarında bir kenar varsa true, aksi takdirde false değerini döndürür.
Eğer u, vertices içinde değilse false döndürün. Aksi takdirde, v'nin u'nun komşu listesinde olup olmadığını döndürün.
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);
}
}
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;
}