Получение соседей
Урок 7 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Алгоритмы, такие как BFS, DFS и поиск кратчайшего пути, не смотрят на исходную карту: они спрашивают «какие соседи у этой вершины?» и обходят полученный результат. Наш метод getNeighbors предоставляет эту возможность.
Если вершина есть в графе, верните список её соседей. Возвращайте копию, если хотите, чтобы вызывающий код мог изменять результат без нарушения целостности графа (это хорошая привычка). Если вершина не существует, верните пустой список вместо того, чтобы вызывать ошибку. Это упрощает клиентский код: он всегда может итерировать результат.
Задание
ЛегкоДобавьте метод getNeighbors в класс Graph.
Он принимает целое число key и возвращает список его соседей:
- Если
keyприсутствует вvertices, верните список его соседей (копия вполне подойдет). - Если
keyотсутствует в графе, верните пустой список.
Попробуйте сами
#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;
}
Все уроки раздела Графы — Серия «Структуры данных» №9
2Проект: Граф
Класс GraphДобавление вершиныДобавление ребраНаличие ребраПолучение соседейУдаление ребраРазмер