E025. Depth-first search

e-maxx algorithm original: C/C++ #algorithm #dfs #emaxx #graph #search

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

Static

Источник: e-maxx.ru/algo, страница PDF 85.

Это один из основных アルゴリズムов на グラフах. В результате поиска в глубину находится лексикоグラフически первый путь в グラフе. アルゴリズム работает за O (N+M).

Applications アルゴリズムа

● Поиск любого пути в グラフе.

● Поиск лексикоグラフически первого пути в グラフе.

● Проверка, является ли одна vertex дерева предком другой:

В начале и конце итерации поиска в глубину будет запоминать "время" захода и 出力а в каждой вершине. Теперь за O (1) можно find ответ: vertex i является предком вершины j тогда и только тогда, когда starti < startj и endi > endj.

● 問題 LCA (Lowest common ancestor).

● Topological sorting:

Запускаем серию поисков в глубину, чтобы обойти все вершины グラフа. Отсортируем вершины по времени 出力а по убыванию - это и будет ответом.

● Проверка グラフа на ацикличность и нахождение цикла

● Поиск компонент сильной связности:

Сначала делаем топологическую сортировку, потом транспонируем グラフ и проводим снова серию поисков в глубину в порядке, определяемом топологической сортировкой. Каждое 木 поиска - сильносвязная компонента.

● Поиск мостов:

Сначала превращаем グラフ в ориентированный, делая серию поисков в глубину, и ориентируя каждое edge так, как мы пытались по нему пройти. Затем находим сильносвязные компоненты. Мостами являются те рёбра, концы которых принадлежат разным сильносвязным компонентам.

実装

vector < vector<int> > g; // グラフ

int n; // number вершин

vector<int> color; // цвет вершины (0, 1, или 2)

vector<int> time_in, time_out; // "времена" захода и 出力а из вершины

int dfs_timer = 0; // "таймер" для определения времён

void dfs (int v) {

time_in[v] = dfs_timer++;

color[v] = 1;

for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)

if (color[*i] == 0)

dfs (*i);

color[v] = 2;

time_out[v] = dfs_timer++;

} Это наиболее общий код. Во многих случаях времена захода и 出力а из вершины не важны, так же как и не важны цвета вершин (но тогда надо будет ввести аналогичный по смыслу булевский 配列 used). Вот наиболее простая 実装:

vector < vector<int> > g; // グラフ

int n; // number вершин

vector<char> used;

void dfs (int v) {

used[v] = true;

for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)

if (!used[*i])

dfs (*i);

}

C# 解法

自動ドラフト、提出前に確認

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    vector < List<int> > g; // граф
    int n; // число вершин
    List<int> color; // цвет вершины (0, 1, или 2)
    List<int> time_in, time_out; // "времена" захода и выхода из вершины
    int dfs_timer = 0; // "таймер" для определения времён
    void dfs (int v) {
            time_in[v] = dfs_timer++;
            color[v] = 1;
            for (List<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
                    if (color[*i] == 0)
                            dfs (*i);
            color[v] = 2;
            time_out[v] = dfs_timer++;
    }
    vector < List<int> > g; // граф
    int n; // число вершин
    List<char> used;
    void dfs (int v) {
            used[v] = true;
            for (List<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
                    if (!used[*i])
                            dfs (*i);
    }
}

C++ 解法

照合済み/オリジナル

vector < vector<int> > g; // граф
int n; // число вершин
vector<int> color; // цвет вершины (0, 1, или 2)
vector<int> time_in, time_out; // "времена" захода и выхода из вершины
int dfs_timer = 0; // "таймер" для определения времён
void dfs (int v) {
        time_in[v] = dfs_timer++;
        color[v] = 1;
        for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
                if (color[*i] == 0)
                        dfs (*i);
        color[v] = 2;
        time_out[v] = dfs_timer++;
}
vector < vector<int> > g; // граф
int n; // число вершин
vector<char> used;
void dfs (int v) {
        used[v] = true;
        for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
                if (!used[*i])
                        dfs (*i);
}

Java 解法

自動ドラフト、提出前に確認

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    vector < ArrayList<Integer> > g; // граф
    int n; // число вершин
    ArrayList<Integer> color; // цвет вершины (0, 1, или 2)
    ArrayList<Integer> time_in, time_out; // "времена" захода и выхода из вершины
    int dfs_timer = 0; // "таймер" для определения времён
    void dfs (int v) {
            time_in[v] = dfs_timer++;
            color[v] = 1;
            for (ArrayList<Integer>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
                    if (color[*i] == 0)
                            dfs (*i);
            color[v] = 2;
            time_out[v] = dfs_timer++;
    }
    vector < ArrayList<Integer> > g; // граф
    int n; // число вершин
    ArrayList<Character> used;
    void dfs (int v) {
            used[v] = true;
            for (ArrayList<Integer>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
                    if (!used[*i])
                            dfs (*i);
    }
}

Материал разбит как アルゴリズムическая 問題: изучить постановку, понять асимптотику и реализовать アルゴリズム на выбранном языке.

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。