Пошук у глибину (DFS)

Пошук у глибину (DFS) — один із основних алгоритмів на графах.

Пошук у глибину знаходить лексикографічно перший шлях у графі від початкової вершини $u$ до кожної вершини. Пошук у глибину також знаходить найкоротші шляхи в дереві (бо там існує лише один простий шлях), але для довільних графів це вже не так.

Алгоритм працює за час $O(m + n)$ , де $n$ — кількість вершин, а $m$ — кількість ребер.

Коли підходить цей алгоритм?

Потрібно обійти граф вглиб: компоненти зв'язності, пошук циклу, топологічне сортування, часи входу/виходу або перевірка «предок-нащадок»?
Достатньо будь-якого (лексикографічно першого) шляху, а не найкоротшого за кількістю ребер? (якщо потрібен найкоротший у незваженому графі → BFS)
DFS — основа складніших алгоритмів на цій сторінці (мости, точки зчленування, компоненти сильної зв'язності)?

Опис алгоритму

Ідея DFS полягає в тому, щоб заходити в граф якомога глибше, і повертатися назад, щойно ми опиняємося у вершині, де немає невідвіданих сусідніх вершин.

Алгоритм дуже легко описати / реалізувати рекурсивно: Ми починаємо пошук в одній вершині. Відвідавши вершину, ми далі виконуємо DFS для кожної сусідньої вершини, яку ще не відвідували. Так ми відвідуємо всі вершини, досяжні зі стартової вершини.

Подробиці дивіться в реалізації.

Застосування пошуку у глибину

Знайти будь-який шлях у графі від початкової вершини $u$ до всіх вершин.
Знайти лексикографічно перший шлях у графі від початкової вершини $u$ до всіх вершин.
Перевірити, чи є вершина в дереві предком якоїсь іншої вершини:

На початку та в кінці кожного виклику пошуку ми запам'ятовуємо «час» входу та виходу для кожної вершини. Тепер можна знайти відповідь для будь-якої пари вершин $(i, j)$ за $O(1)$ : вершина $i$ є предком вершини $j$ тоді й лише тоді, коли $\text{entry}[i] < \text{entry}[j]$ і $\text{exit}[i] > \text{exit}[j]$ .
Знайти найнижчого спільного предка (LCA) двох вершин.
Топологічне сортування:

Запускаємо серію пошуків у глибину так, щоб відвідати кожну вершину рівно один раз за час $O(n + m)$ . Потрібний топологічний порядок — це вершини, відсортовані за спаданням часу виходу.
Перевірити, чи є заданий граф ациклічним, і знайти цикли в графі. (Як зазначено нижче — підрахувавши зворотні ребра в кожній компоненті зв'язності.)
Знайти компоненти сильної зв'язності в орієнтованому графі:

Спочатку робимо топологічне сортування графа. Потім транспонуємо граф і запускаємо ще одну серію пошуків у глибину в порядку, заданому топологічним сортуванням. Для кожного виклику DFS компонента, яку він створює, є компонентою сильної зв'язності.
Знайти мости в неорієнтованому графі:

Спочатку перетворюємо заданий граф на орієнтований, запустивши серію пошуків у глибину та орієнтуючи кожне ребро в міру проходження через нього — у тому напрямку, в якому ми йшли. По-друге, знаходимо компоненти сильної зв'язності в цьому орієнтованому графі. Мости — це ребра, кінці яких належать різним компонентам сильної зв'язності.

Класифікація ребер графа

Ми можемо класифікувати ребра графа $G$ , використовуючи час входу та виходу кінцевих вершин $u$ і $v$ ребер $(u,v)$ . Ці класифікації часто застосовують у задачах на кшталт пошуку мостів та пошуку точок зчленування.

Ми виконуємо DFS і класифікуємо ребра, що трапляються, за такими правилами:

Якщо $v$ не відвідано:

Деревне ребро — Якщо $v$ відвідано після $u$ , то ребро $(u,v)$ називається деревним ребром. Іншими словами, якщо $v$ відвідується вперше, а $u$ відвідується зараз, то $(u,v)$ називається деревним ребром. Ці ребра утворюють дерево DFS — звідси й назва «деревні ребра».

Якщо $v$ відвідано раніше за $u$ :

Зворотні ребра — Якщо $v$ є предком $u$ , то ребро $(u,v)$ є зворотним ребром. $v$ є предком саме тоді, коли ми вже увійшли у $v$ , але ще не вийшли з нього. Зворотні ребра замикають цикл, бо існує шлях від предка $v$ до нащадка $u$ (у рекурсії DFS) і ребро від нащадка $u$ до предка $v$ (зворотне ребро), отже, утворюється цикл. Цикли можна виявляти за допомогою зворотних ребер.
Прямі ребра — Якщо $v$ є нащадком $u$ , то ребро $(u, v)$ є прямим ребром. Іншими словами, якщо ми вже відвідали $v$ і вийшли з нього, і $\text{entry}[u] < \text{entry}[v]$ , то ребро $(u,v)$ утворює пряме ребро.
Перехресні ребра: якщо $v$ не є ні предком, ні нащадком $u$ , то ребро $(u, v)$ є перехресним ребром. Іншими словами, якщо ми вже відвідали $v$ і вийшли з нього, і $\text{entry}[u] > \text{entry}[v]$ , то $(u,v)$ є перехресним ребром.

Теорема. Нехай $G$ — неорієнтований граф. Тоді виконання DFS на $G$ класифікує кожне ребро, що трапляється, або як деревне ребро, або як зворотне ребро, тобто прямі та перехресні ребра існують лише в орієнтованих графах.

Припустимо, що $(u,v)$ — довільне ребро графа $G$ , і, без втрати загальності, $u$ відвідано раніше за $v$ , тобто $\text{entry}[u] < \text{entry}[v]$ . Оскільки DFS обробляє ребра лише один раз, існує тільки два способи, якими ми можемо обробити ребро $(u,v)$ і тим самим класифікувати його:

Уперше ми досліджуємо ребро $(u,v)$ у напрямку від $u$ до $v$ . Оскільки $\text{entry}[u] < \text{entry}[v]$ , рекурсивна природа DFS означає, що вершина $v$ буде повністю досліджена, а отже, з неї вийдуть, перш ніж ми зможемо «піднятися назад стеком викликів», щоб вийти з вершини $u$ . Тому вершина $v$ має бути невідвіданою, коли DFS уперше досліджує ребро $(u,v)$ від $u$ до $v$ , бо інакше пошук дослідив би $(u,v)$ від $v$ до $u$ ще до виходу з вершини $v$ , оскільки вершини $u$ і $v$ є сусідами. Отже, ребро $(u,v)$ є деревним ребром.
Уперше ми досліджуємо ребро $(u,v)$ у напрямку від $v$ до $u$ . Оскільки ми виявили вершину $u$ раніше за вершину $v$ , а ребра обробляємо лише один раз, єдиний спосіб дослідити ребро $(u,v)$ у напрямку від $v$ до $u$ — це якщо існує інший шлях від $u$ до $v$ , який не використовує ребро $(u,v)$ , що робить $u$ предком $v$ . Тоді ребро $(u,v)$ замикає цикл, бо йде від нащадка $v$ до предка $u$ , з якого ми ще не вийшли. Отже, ребро $(u,v)$ є зворотним ребром.

Оскільки існує лише два способи обробити ребро $(u,v)$ — з двома випадками та відповідними їм класифікаціями, описаними вище, — виконання DFS на $G$ класифікує кожне ребро, що трапляється, або як деревне ребро, або як зворотне ребро, тобто прямі та перехресні ребра існують лише в орієнтованих графах. Це завершує доведення.

Реалізація

C++
Python
TypeScript
Go

vector<vector<int>> adj; // граф, представлений списком суміжності
int n; // кількість вершин

vector<bool> visited;

void dfs(int v) {
	visited[v] = true;
	for (int u : adj[v]) {
		if (!visited[u])
			dfs(u);
    }
}

import sys

# Рекурсивний DFS на глибокому графі може впертися в стандартний ліміт
# рекурсії Python (~1000), що спричинить RecursionError. Збільшуємо його.
sys.setrecursionlimit(1_000_000)

adj: list[list[int]] = []  # граф: список списків суміжності
n: int = 0                 # кількість вершин

visited: list[bool] = []


def dfs(v: int) -> None:
    visited[v] = True
    for u in adj[v]:
        if not visited[u]:
            dfs(u)

let adj: number[][] = []; // граф: масив списків суміжності
let n = 0;                // кількість вершин

let visited: boolean[] = [];

function dfs(v: number): void {
    visited[v] = true;
    for (const u of adj[v]) {
        if (!visited[u]) dfs(u);
    }
}

var adj [][]int // граф: слайс слайсів суміжності
var n int       // кількість вершин

var visited []bool

func dfs(v int) {
	visited[v] = true
	for _, u := range adj[v] {
		if !visited[u] {
			dfs(u)
		}
	}
}

Це найпростіша реалізація пошуку у глибину. Як описано в застосуваннях, може бути корисно також обчислювати час входу та виходу й колір вершини. Ми будемо фарбувати всі вершини кольором 0, якщо ми їх не відвідували, кольором 1, якщо ми їх відвідали, і кольором 2, якщо ми з вершини вже вийшли.

Ось узагальнена реалізація, яка додатково обчислює це:

C++
Python
TypeScript
Go

vector<vector<int>> adj; // граф, представлений списком суміжності
int n; // кількість вершин

vector<int> color;

vector<int> time_in, time_out;
int dfs_timer = 0;

void dfs(int v) {
	time_in[v] = dfs_timer++;
	color[v] = 1;
	for (int u : adj[v])
		if (color[u] == 0)
			dfs(u);
	color[v] = 2;
	time_out[v] = dfs_timer++;
}

import sys

# Глибока рекурсія -> збільшуємо ліміт, щоб уникнути RecursionError.
sys.setrecursionlimit(1_000_000)

adj: list[list[int]] = []  # граф: список списків суміжності
n: int = 0                 # кількість вершин

color: list[int] = []

time_in: list[int] = []
time_out: list[int] = []
dfs_timer = 0


def dfs(v: int) -> None:
    global dfs_timer
    time_in[v] = dfs_timer
    dfs_timer += 1
    color[v] = 1
    for u in adj[v]:
        if color[u] == 0:
            dfs(u)
    color[v] = 2
    time_out[v] = dfs_timer
    dfs_timer += 1

let adj: number[][] = []; // граф: масив списків суміжності
let n = 0;                // кількість вершин

let color: number[] = [];

let timeIn: number[] = [];
let timeOut: number[] = [];
let dfsTimer = 0;

function dfs(v: number): void {
    timeIn[v] = dfsTimer++;
    color[v] = 1;
    for (const u of adj[v]) {
        if (color[u] === 0) dfs(u);
    }
    color[v] = 2;
    timeOut[v] = dfsTimer++;
}

var adj [][]int // граф: слайс слайсів суміжності
var n int       // кількість вершин

var color []int

var timeIn []int
var timeOut []int
var dfsTimer int

func dfs(v int) {
	timeIn[v] = dfsTimer
	dfsTimer++
	color[v] = 1
	for _, u := range adj[v] {
		if color[u] == 0 {
			dfs(u)
		}
	}
	color[v] = 2
	timeOut[v] = dfsTimer
	dfsTimer++
}

Пошук у глибину (DFS)

Опис алгоритму

Застосування пошуку у глибину

Класифікація ребер графа

Реалізація

Задачі для практики

Відеоматеріали

Опис алгоритму​

Застосування пошуку у глибину​

Класифікація ребер графа​

Реалізація​

Задачі для практики​

Відеоматеріали​

Опис алгоритму

Застосування пошуку у глибину

Класифікація ребер графа

Реалізація

Задачі для практики

Відеоматеріали