Топологическая сортировка - История изменений

Ctrlalt в 15:16, 24 мая 2023

2023-05-24T15:16:23Z

← Предыдущая версия		Версия от 15:16, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==
			<youtube width="300" height="180">o0P8oNXoA_w</youtube>

	== Топологическая сортировка через DFS ==		== Топологическая сортировка через DFS ==
	* Порядок топологической сортировки — порядок убывания времени выхода из вершины.		* Порядок топологической сортировки — порядок убывания времени выхода из вершины.

Ctrlalt в 18:16, 22 марта 2022

2022-03-22T18:16:30Z

← Предыдущая версия		Версия от 18:16, 22 марта 2022
Строка 4:		Строка 4:
	* Время работы O(V + E).		* Время работы O(V + E).

	vector<vector<int>> graph~~(vertexCount);~~		void dfs(vector<vector<int>> &graph, int v, vector<int> &visited, vector<int> &order) {
	vector<~~bool~~> visited~~(vertexCount);~~
	vector<int> order;

	~~void dfs(int v~~) {
	visited[v] = 1;		visited[v] = 1;
	for (int to : graph[v])		for (int to : graph[v])
	if (!visited[to])		if (!visited[to])
	dfs(to);		dfs(graph, to, visited, order);
	order.push_back(v);		order.push_back(v);
	}		}

	for (int v = 0; v < ~~vertexCount~~; v++)		for (int v = 0; v < graph.size(); v++)
	if (!visited[v])		if (!visited[v])
	dfs(v);		dfs(graph, v, visited, order);
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());

Строка 26:		Строка 22:
	* Время работы O(VlogV + E).		* Время работы O(VlogV + E).

	~~vector<~~vector<int>> graph(~~vertexCount~~);		vector<int> inDegree(graph.size());
			for (int v = 0; v < graph.size(); v++)
	~~vector<int> inDegree(vertexCount~~);
	for (int v = 0; v < ~~vertexCount~~; v++)
	for (int to : graph[v])		for (int to : graph[v])
	inDegree[to]++;		inDegree[to]++;

	set<pair<int, int>> q;		set<pair<int, int>> q;
	for (int v = 0; v < ~~vertexCount~~; v++)		for (int v = 0; v < graph.size(); v++)
	q.insert({ inDegree[v], v });		q.insert({ inDegree[v], v });

Ctrlalt: /* Ссылки */

2021-04-12T14:59:00Z

Ссылки

← Предыдущая версия		Версия от 14:59, 12 апреля 2021
Строка 59:		Строка 59:
	:* [https://usaco.guide/gold/toposort usaco.guide — Topological Sort]		:* [https://usaco.guide/gold/toposort usaco.guide — Topological Sort]
	:* [https://notes.algoprog.ru/dfs/04_3_topsort.html#id2 Калинин П. Топологическая сортировка]		:* [https://notes.algoprog.ru/dfs/04_3_topsort.html#id2 Калинин П. Топологическая сортировка]
	:* [https://~~archive~~.lksh.ru/2014/~~july~~/Cprime/stuff/Dfs.pdf Лахно А. Поиск в глубину и его применение]		:* [https://ejudge.lksh.ru/archive/2014/07/Cprime/stuff/Dfs.pdf Лахно А. Поиск в глубину и его применение]
	:* [https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]		:* [https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]
	Демонстрация:		Демонстрация:
Строка 65:		Строка 65:
	Код:		Код:
	:* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/dfs/topological_sort.cpp codelibrary/cpp/graphs/dfs/topological_sort.cpp]		:* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/dfs/topological_sort.cpp codelibrary/cpp/graphs/dfs/topological_sort.cpp]
	:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Topological.java algs4//Topological.java]		:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Topological.java algs4/Topological.java]
	Задачи:		Задачи:
	:* [http://acm.timus.ru/problem.aspx?space=1&num=1022 Timus #1022 — Генеалогическое дерево]		:* [http://acm.timus.ru/problem.aspx?space=1&num=1022 Timus #1022 — Генеалогическое дерево]

Ctrlalt в 21:21, 7 апреля 2021

2021-04-07T21:21:34Z

← Предыдущая версия		Версия от 21:21, 7 апреля 2021
Строка 9:		Строка 9:

	void dfs(int v) {		void dfs(int v) {
	visited[v] = ~~true~~;		visited[v] = 1;
	for (int to : graph[v])		for (int to : graph[v])
	if (!visited[to])		if (!visited[to])

Ctrlalt в 21:10, 7 апреля 2021

2021-04-07T21:10:13Z

← Предыдущая версия		Версия от 21:10, 7 апреля 2021
Строка 9:		Строка 9:

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

Ctrlalt в 13:14, 23 января 2021

2021-01-23T13:14:15Z

← Предыдущая версия		Версия от 13:14, 23 января 2021
Строка 1:		Строка 1:
	* Порядок топологической сортировки ~~—~~ порядок убывания времени выхода из вершины.		== Топологическая сортировка через DFS ==
			* Порядок топологической сортировки — порядок убывания времени выхода из вершины.
	* Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).		* Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).
			* Время работы O(V + E).

	vector<vector<int>> g(n);		vector<vector<int>> graph(vertexCount);
	vector<bool> visited(n);		vector<bool> visited(vertexCount);
	vector<int> order;		vector<int> order;

	void dfs(int v) {		void dfs(int v) {
	visited[v] = 1;		visited[v] = 1;
	for (int to : g[v])		for (int to : graph[v])
	if (!visited[to])		if (!visited[to])
	dfs(to);		dfs(to);
Строка 14:		Строка 16:
	}		}

	for (int v = 0; v < n; v++)		for (int v = 0; v < vertexCount; v++)
	if (!visited[v])		if (!visited[v])
	dfs(v);		dfs(v);
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());

	== ~~Ссылки на задачи~~ ==		== Алгоритм Кана ==
	* ~~[http://acm~~.~~timus~~.~~ru/problem~~.~~aspx?space~~=~~1&num~~=~~1022 Timus #1022 &mdash~~; ~~Генеалогическое дерево~~]		* Пока в графе остались вершины, находим любой исток, добавляем его к ответу и удаляем из графа вместе со всеми исходящими рёбрами.
	* [~~http://codeforces~~.~~ru/gym/100070/problem/B Codeforces #100070~~.~~B &mdash~~; ~~Топологическая сортировка]~~		* Данный алгоритм, в отличие от предыдущего, позволяет найти лексикографически минимальную топологическую сортировку.
			* Время работы O(VlogV + E).

			vector<vector<int>> graph(vertexCount);

			vector<int> inDegree(vertexCount);
			for (int v = 0; v < vertexCount; v++)
			for (int to : graph[v])
			inDegree[to]++;

			set<pair<int, int>> q;
			for (int v = 0; v < vertexCount; v++)
			q.insert({ inDegree[v], v });

			vector<int> order;
			while (!q.empty()) {
			int v = q.begin()->second;
			q.erase(q.begin());

			order.push_back(v);

			for (int to : graph[v]) {
			q.erase({ inDegree[to], to });
			inDegree[to]--;
			q.insert({ inDegree[to], to });
			}
			}

	== Ссылки ==		== Ссылки ==
	* [http://e-maxx.ru/algo/topological_sort e-maxx.ru ~~—~~ Топологическая сортировка]		Теория:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki ~~—~~ Использование обхода в глубину для топологической сортировки]		:* [http://e-maxx.ru/algo/topological_sort e-maxx.ru — Топологическая сортировка]
	* [http://brestprog.by/topics/topsort/ brestprog — Топологическая сортировка]		:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]
	* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]		:* [http://brestprog.by/topics/topsort/ brestprog.by — Топологическая сортировка]
	* [~~http~~://~~informatics.mccme~~.ru/~~course~~/~~view~~.~~php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2~~]		:* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
	* [~~http~~://~~github~~.~~com~~/~~petr-kalinin/progtexts/releases/download~~/~~v2014~~.~~11.01/04_dfs.pdf~~ Калинин П. ~~Поиск в глубину~~]		:* [https://usaco.guide/gold/toposort usaco.guide — Topological Sort]
	* [~~http~~://~~ejudge~~.~~btty~~.su/~~bmstu~~/~~addon~~/~~docs~~/~~articles~~/~~moscow2006-dfs~~.pdf Лахно А. Поиск в глубину и его применение]		:* [https://notes.algoprog.ru/dfs/04_3_topsort.html#id2 Калинин П. Топологическая сортировка]
	* [~~http~~://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures ~~—~~ 4.2 Directed Graphs]		:* [https://archive.lksh.ru/2014/july/Cprime/stuff/Dfs.pdf Лахно А. Поиск в глубину и его применение]
	* [~~http~~://visualgo.net/dfsbfs~~.html~~ VisuAlgo ~~—~~ Graph Traversal]		:* [https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]
	* [~~http~~://github.com/indy256/codelibrary/blob/master/java/~~src~~/~~TopologicalSort~~.java ~~CodeLibrary~~ &~~mdash; Topological sorting~~]		Демонстрация:
			:* [https://visualgo.net/en/dfsbfs VisuAlgo — Graph Traversal]
			Код:
			:* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/dfs/topological_sort.cpp codelibrary/cpp/graphs/dfs/topological_sort.cpp]
			:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Topological.java algs4//Topological.java]
			Задачи:
			:* [http://acm.timus.ru/problem.aspx?space=1&num=1022 Timus #1022 — Генеалогическое дерево]
			:* [http://codeforces.ru/gym/100070/problem/B Codeforces #100070.B — Топологическая сортировка]
			:* [https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2001 UVa #11060 — Beverages]


	[[Category:Поиск в глубину и его приложения]]		[[Category:Поиск в глубину и его приложения]]

Ctrlalt в 15:52, 15 февраля 2020

2020-02-15T15:52:16Z

← Предыдущая версия		Версия от 15:52, 15 февраля 2020
Строка 2:		Строка 2:
	* Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).		* Каждую вершину при выходе из DFS кладём в контейнер, который после переворачиваем (также можно использовать стек).

	vector<int> g~~[V_CNT]~~;		vector<vector<int>> g(n);
	bool ~~u[V_CNT]~~;		vector<bool> visited(n);
	vector<int> order;		vector<int> order;

	void dfs(int v) {		void dfs(int v) {
	u[v] = 1;		visited[v] = 1;
	for (int ~~i = 0; i <~~ g[v]~~.size(); i++~~)		for (int to : g[v])
	if (!u[~~g[v][i]~~])		if (!visited[to])
	dfs(~~g[v][i]~~);		dfs(to);
	order.push_back(v);		order.push_back(v);
	}		}

	for (int i = 0; i < ~~V_CNT~~; ~~i++)~~		for (int v = 0; v < n; v++)
	~~u[i] = 0;~~		if (!visited[v])
	~~for (int i = 0; i < V_CNT; i~~++)		dfs(v);
	if (!u[i])
	dfs(i);
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());

Строка 28:		Строка 26:
	* [http://e-maxx.ru/algo/topological_sort e-maxx.ru — Топологическая сортировка]		* [http://e-maxx.ru/algo/topological_sort e-maxx.ru — Топологическая сортировка]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]
	* [http://brestprog.~~neocities.org~~/~~lections~~/topsort~~.html~~ brestprog~~.neocities.org —~~ Топологическая сортировка]		* [http://brestprog.by/topics/topsort/ brestprog — Топологическая сортировка]
	* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]		* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
	* [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]

Ctrlalt: /* Ссылки */

2019-08-30T13:57:35Z

Ссылки

← Предыдущая версия		Версия от 13:57, 30 августа 2019
Строка 29:		Строка 29:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]
	* [http://brestprog.neocities.org/lections/topsort.html brestprog.neocities.org — Топологическая сортировка]		* [http://brestprog.neocities.org/lections/topsort.html brestprog.neocities.org — Топологическая сортировка]
			* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
	* [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 Калинин П. Поиск в глубину]

Ctrlalt: /* Ссылки */

2016-01-27T20:03:44Z

Ссылки

← Предыдущая версия		Версия от 20:03, 27 января 2016
Строка 28:		Строка 28:
	* [http://e-maxx.ru/algo/topological_sort e-maxx.ru — Топологическая сортировка]		* [http://e-maxx.ru/algo/topological_sort e-maxx.ru — Топологическая сортировка]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]
			* [http://brestprog.neocities.org/lections/topsort.html brestprog.neocities.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 Калинин П. Поиск в глубину]

Ctrlalt: /* Ссылки */

2015-04-30T22:00:13Z

Ссылки

← Предыдущая версия		Версия от 22:00, 30 апреля 2015
Строка 29:		Строка 29:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для топологической сортировки]
	* [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://ejudge.btty.su/bmstu/addon/docs/articles/moscow2006-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://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]		* [http://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]
	* [http://visualgo.net/dfsbfs.html VisuAlgo — Graph Traversal]		* [http://visualgo.net/dfsbfs.html VisuAlgo — Graph Traversal]