Komşuları Getir
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 7 / 14.
BFS, DFS ve en kısa yol gibi algoritmalar ham haritaya bakmazlar: "bu köşenin komşuları nelerdir?" diye sorarlar ve cevabı takip ederler. getNeighbors metodumuz bunu açığa çıkarır.
Eğer köşe grafın içindeyse, komşu listesini döndürün. Çağıranların grafı bozmadan sonucu değiştirmesini istiyorsanız bir kopya döndürün (bu iyi bir alışkanlıktır). Eğer köşe mevcut değilse, çökmek yerine boş bir liste döndürün. Bu, istemci kodunu basit tutar: sonucu her zaman yineleyebilir.
Görev
KolayGraph sınıfına bir getNeighbors metodu ekleyin.
Bu metot bir tam sayı key alır ve onun komşularının bir listesini döndürür:
- Eğer
key,verticesiçinde varsa, onun komşu listesini döndürün (bir kopyası olabilir). - Eğer
keygraf içinde yoksa, boş bir liste 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"); }
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;
}