Pobieranie sąsiadów
Lekcja 7 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.
Algorytmy takie jak BFS, DFS i algorytm najkrótszej ścieżki nie analizują surowej mapy: pytają „jakich sąsiadów ma ten wierzchołek?” i przemierzają otrzymaną listę. Udostępnia ją nasza metoda getNeighbors.
Jeśli wierzchołek znajduje się w grafie, zwróć listę jego sąsiadów. Zwróć jej kopię, jeśli chcesz umożliwić wywołującym modyfikowanie wyniku bez naruszania grafu (to dobry nawyk). Jeśli wierzchołek nie istnieje, zwróć pustą listę zamiast powodować błąd. Dzięki temu kod kliencki jest prosty: zawsze może iterować po wyniku.
Wyzwanie
ŁatwyDodaj metodę getNeighbors do klasy Graph.
Przyjmuje liczbę całkowitą key i zwraca listę jej sąsiadów:
- Jeśli
keyznajduje się wvertices, zwróć listę jej sąsiadów (może być kopią). - Jeśli
keynie znajduje się w grafie, zwróć pustą listę.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Grafy – struktury danych, seria nr 9
2Projekt grafu
Klasa grafuDodawanie wierzchołkaDodawanie krawędziCzy istnieje krawędźPobieranie sąsiadówUsuwanie krawędziRozmiarPoćwicz samodzielnie: Kompilator C online