Поиск в глубину: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показано 10 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== TLDR == | |||
<youtube width="300" height="180">3-XLRh2M5YI</youtube> | |||
== Стандартный DFS == | |||
void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) { | |||
visited[v] = 1; | |||
for (int to : graph[v]) | |||
if (!visited[to]) | |||
dfs(graph, to, visited); | |||
} | |||
== DFS на неявном графе == | |||
void dfs(vector<vector<int>> &a, int y, int x, vector<vector<int>> &visited) { | |||
visited[y][x] = 1; | |||
static vector<int> dy = { -1, 0, 1, 0 }; | |||
static vector<int> dx = { 0, 1, 0, -1 }; | |||
for (int d = 0; d < dy.size(); d++) { | |||
int ty = y + dy[d]; | |||
int tx = x + dx[d]; | |||
if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[ty][tx] && !visited[ty][tx]) | |||
dfs(a, ty, tx, visited); | |||
} | |||
} | |||
== Ссылки == | == Ссылки == | ||
* [http://e-maxx.ru/algo/dfs e-maxx.ru — Поиск в глубину] | * [http://e-maxx.ru/algo/dfs e-maxx.ru — Поиск в глубину] | ||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD neerc.ifmo.ru/wiki — Обход в глубину] | * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD neerc.ifmo.ru/wiki — Обход в глубину] | ||
* [http://brestprog. | * [http://brestprog.by/topics/dfs/ brestprog — Рекурсия. Обход в глубину (DFS)] | ||
* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину] | |||
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2] | * [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2] | ||
* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину] | * [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину] | ||
* [http://ejudge.btty.su/bmstu/addon/docs/articles/moscow2006-dfs.pdf Лахно А. Поиск в глубину и его применение] | * [http://ejudge.btty.su/bmstu/addon/docs/articles/moscow2006-dfs.pdf Лахно А. Поиск в глубину и его применение] | ||
* [http://algs4.cs.princeton.edu/lectures/41UndirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.1 Undirected Graphs] | * [http://algs4.cs.princeton.edu/lectures/41UndirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.1 Undirected Graphs] | ||
* [http://brilliant.org/wiki/depth-first-search-dfs Brilliant.org — Depth-First Search] | |||
* [http://visualgo.net/dfsbfs.html VisuAlgo — Graph Traversal] | * [http://visualgo.net/dfsbfs.html VisuAlgo — Graph Traversal] | ||
[[Category:Поиск в глубину и его приложения]] | [[Category:Поиск в глубину и его приложения]] | ||
Текущая версия от 15:12, 24 мая 2023
TLDR
Стандартный DFS
void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {
visited[v] = 1;
for (int to : graph[v])
if (!visited[to])
dfs(graph, to, visited);
}
DFS на неявном графе
void dfs(vector<vector<int>> &a, int y, int x, vector<vector<int>> &visited) {
visited[y][x] = 1;
static vector<int> dy = { -1, 0, 1, 0 };
static vector<int> dx = { 0, 1, 0, -1 };
for (int d = 0; d < dy.size(); d++) {
int ty = y + dy[d];
int tx = x + dx[d];
if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[ty][tx] && !visited[ty][tx])
dfs(a, ty, tx, visited);
}
}
Ссылки
- e-maxx.ru — Поиск в глубину
- neerc.ifmo.ru/wiki — Обход в глубину
- brestprog — Рекурсия. Обход в глубину (DFS)
- algorithmica.org — Графы. Поиск в глубину
- informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
- Калинин П. Поиск в глубину
- Лахно А. Поиск в глубину и его применение
- algs4.cs.princeton.edu/lectures — 4.1 Undirected Graphs
- Brilliant.org — Depth-First Search
- VisuAlgo — Graph Traversal