Implementation (Part 1)
Урок 5 из 9 курса Поиск в глубину — алгоритмы на графах на Coddy.
Мы реализуем DFS, начиная с поиска по смежности.
Задание
ЛегкоПеред обходом графа нам необходимо знать соседей каждой вершины. Давайте создадим этот механизм поиска на основе плоского списка ребер.
Напишите функцию с именем getNeighbors, которая принимает массив edges (плоские пары [u0, v0, u1, v1, ...], неориентированные) и вершину node, и возвращает отсортированный список соседей node без дубликатов.
Например, getNeighbors([0,1, 0,2, 1,2, 3,0], 0) возвращает [1, 2, 3].
Попробуйте сами
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, int* returnSize) {
// Напишите код здесь
*returnSize = 0;
return edges;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Поиск в глубину — алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity