DFS
Урок 11 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Поиск в глубину (Depth-First Search) идет вглубь, прежде чем идти вширь. Начиная с вершины, он следует по одному ребру как можно дальше, затем возвращается назад и пробует следующее. Итеративная версия использует стек: извлеките вершину, запишите её, поместите её непосещенных соседей обратно в стек.
Чтобы DFS выдавал детерминированный порядок обхода в этой задаче, добавляйте соседей в обратном отсортированном порядке. Таким образом, наименьший сосед окажется на вершине стека и будет обработан первым, что соответствует порядку, который выдал бы рекурсивный DFS при обходе соседей по возрастанию.
Следите за тем, чтобы вершина не была добавлена дважды (разные соседи могут иметь одну и ту же вершину). Проверяйте набор посещенных вершин в начале цикла и пропускайте вершину, если она уже была посещена.
Задание
ЛегкоНапишите функцию dfs, которая принимает двумерный массив целых чисел adjacency (где каждая строка представляет собой ребро [u, v]) и целое число start, и возвращает порядок обхода DFS, начиная с вершины start, в виде списка целых чисел.
Постройте граф, добавляя каждое ребро. Используйте итеративный DFS с помощью стека: извлеките вершину из стека, если она еще не была посещена, зафиксируйте её и добавьте её соседей в стек в обратном отсортированном порядке, чтобы первым обрабатывался сосед с наименьшим значением.
Вы должны использовать класс Graph (предоставленный в файле graph) — не используйте встроенные средства языка (словари, наборы) для моделирования списка смежности. Вспомогательные данные для алгоритма (множества посещенных вершин, стеки) могут использовать типы из стандартной библиотеки.
Попробуйте сами
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}