Обход графа в глубину

К разделу

1. Как понимать граф в задаче

Перед написанием кода полезно ответить на несколько вопросов:

1. Что является вершинами?
2. Что является ребрами?
3. Граф ориентированный или неориентированный?
4. Нужен один обход или серия обходов?

2. Как хранить граф

Список смежности

Это основной рабочий вариант для большинства задач.

3. Базовый каркас DFS

Главная идея: заходим в вершину, сразу помечаем ее посещенной, потом идем во всех непосещенных соседей.

Визуализация. Неориентированный граф.

Ниже стоит заготовка компонента в том же месте, где на референсе находится пошаговый SVG deck. Позже сюда можно перенести полноценную визуализацию DFS.

1 / 3

Шаг 1. Вход в dfs(1)

• Помечаем вершину 1 посещенной.
• Начинаем перебор соседей.

Рекурсивный DFS

void dfs(int v) {
    used[v] = true;
    for (int to : graph[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

4. Компоненты связности

Материал будет добавлен позже.

5. Двудольность

Материал будет добавлен позже.

6. Поиск цикла в неориентированном графе

Материал будет добавлен позже.