Поиск в ширину - История изменений

Ctrlalt в 15:25, 24 мая 2023

2023-05-24T15:25:15Z

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

	== Стандартный BFS ==		== Стандартный BFS ==
	vector<int> bfs(vector<vector<int>> &graph, int start) {		vector<int> bfs(vector<vector<int>> &graph, int start) {

Ctrlalt: /* BFS на неявном графе */

2023-02-23T19:58:44Z

BFS на неявном графе

← Предыдущая версия		Версия от 19:58, 23 февраля 2023
Строка 41:		Строка 41:
	int tx = x + dx[d];		int tx = x + dx[d];

	if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[y][x] && dist[ty][tx] > dist[y][x] + 1) {		if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[ty][tx] && dist[ty][tx] > dist[y][x] + 1) {
	dist[ty][tx] = dist[y][x] + 1;		dist[ty][tx] = dist[y][x] + 1;
	q.push({ ty, tx });		q.push({ ty, tx });

Ctrlalt: /* BFS на неявном графе */

2023-02-23T19:19:16Z

BFS на неявном графе

← Предыдущая версия		Версия от 19:19, 23 февраля 2023
Строка 41:		Строка 41:
	int tx = x + dx[d];		int tx = x + dx[d];

	if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[y][x] && dist[ty][tx] ~~== 1e9~~) {		if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[y][x] && dist[ty][tx] > dist[y][x] + 1) {
	dist[ty][tx] = dist[y][x] + 1;		dist[ty][tx] = dist[y][x] + 1;
	q.push({ ty, tx });		q.push({ ty, tx });

Ctrlalt в 02:15, 28 января 2023

2023-01-28T02:15:53Z

← Предыдущая версия		Версия от 02:15, 28 января 2023
Строка 1:		Строка 1:
			== Стандартный BFS ==
			vector<int> bfs(vector<vector<int>> &graph, int start) {
			vector<int> dist(graph.size(), 1e9);
			queue<int> q;

			dist[start] = 0;
			q.push(start);

			while (!q.empty()) {
			int v = q.front();
			q.pop();

			for (int to : graph[v]) {
			if (dist[to] > dist[v] + 1) {
			dist[to] = dist[v] + 1;
			q.push(to);
			}
			}
			}

			return dist;
			}

			== BFS на неявном графе ==
			vector<vector<int>> bfs(vector<vector<int>> &a, int startY, int startX) {
			vector<vector<int>> dist(a.size(), vector<int>(a[0].size(), 1e9));
			queue<pair<int, int>> q;

			dist[startY][startX] = 0;
			q.push({ startY, startX });

			vector<int> dy = { -1, 0, 1, 0 };
			vector<int> dx = { 0, 1, 0, -1 };

			while (!q.empty()) {
			auto [y, x] = q.front();
			q.pop();

			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[y][x] && dist[ty][tx] == 1e9) {
			dist[ty][tx] = dist[y][x] + 1;
			q.push({ ty, tx });
			}
			}
			}

			return dist;
			}

	== Ссылки на задачи ==		== Ссылки на задачи ==
	* [http://acmp.ru/?main=task&id_task=127 ACMP #127 — Путь]		* [http://acmp.ru/?main=task&id_task=127 ACMP #127 — Путь]

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

2020-01-02T18:19:36Z

Ссылки

← Предыдущая версия		Версия от 18:19, 2 января 2020
Строка 20:		Строка 20:
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]
	* [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/breadth-first-search-bfs Brilliant.org — Breadth-First Search]
	* [http://visualgo.net/sssp.html VisuAlgo — Single-Source Shortest Paths]		* [http://visualgo.net/sssp.html VisuAlgo — Single-Source Shortest Paths]

	[[Category:Кратчайшие пути из одной вершины]]		[[Category:Кратчайшие пути из одной вершины]]

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

2019-08-30T13:48:36Z

Ссылки

← Предыдущая версия		Версия от 13:48, 30 августа 2019
Строка 17:		Строка 17:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki — Обход в ширину]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki — Обход в ширину]
	* [http://brestprog.neocities.org/lections/bfs.html brestprog.neocities.org — Обход в ширину (BFS)]		* [http://brestprog.neocities.org/lections/bfs.html brestprog.neocities.org — Обход в ширину (BFS)]
			* [http://algorithmica.org/tg/bfs algorithmica.org — Поиск в ширину]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]
	* [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]

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

2016-01-27T19:56:36Z

Ссылки

← Предыдущая версия		Версия от 19:56, 27 января 2016
Строка 16:		Строка 16:
	* [http://e-maxx.ru/algo/bfs e-maxx.ru — Поиск в ширину]		* [http://e-maxx.ru/algo/bfs e-maxx.ru — Поиск в ширину]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki — Обход в ширину]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83 neerc.ifmo.ru/wiki — Обход в ширину]
			* [http://brestprog.neocities.org/lections/bfs.html brestprog.neocities.org — Обход в ширину (BFS)]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]
	* [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]

Ctrlalt: /* Ссылки на задачи */

2014-10-26T00:50:42Z

Ссылки на задачи

← Предыдущая версия		Версия от 00:50, 26 октября 2014
Строка 11:		Строка 11:
	* [http://acmp.ru/?main=task&id_task=509 ACMP #509 — Игра Jammed]		* [http://acmp.ru/?main=task&id_task=509 ACMP #509 — Игра Jammed]
	* [http://acmp.ru/?main=task&id_task=695 ACMP #695 — Мифические шахматы]		* [http://acmp.ru/?main=task&id_task=695 ACMP #695 — Мифические шахматы]
			* [http://codeforces.ru/gym/100082/problem/C Codeforces #100082.C — Обход в ширину]

	== Ссылки ==		== Ссылки ==

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

2014-09-29T20:10:15Z

Ссылки

← Предыдущая версия		Версия от 20:10, 29 сентября 2014
Строка 17:		Строка 17:
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 3]
	* [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://visualgo.net/sssp.html VisuAlgo — Single-Source Shortest Paths]

	[[Category:Кратчайшие пути из одной вершины]]		[[Category:Кратчайшие пути из одной вершины]]

Ctrlalt: /* Ссылки на задачи */

2014-09-10T16:14:42Z

Ссылки на задачи

← Предыдущая версия		Версия от 16:14, 10 сентября 2014
Строка 9:		Строка 9:
	* [http://acmp.ru/?main=task&id_task=426 ACMP #426 — Lines - 2]		* [http://acmp.ru/?main=task&id_task=426 ACMP #426 — Lines - 2]
	* [http://acmp.ru/?main=task&id_task=431 ACMP #431 — Путь коня]		* [http://acmp.ru/?main=task&id_task=431 ACMP #431 — Путь коня]
			* [http://acmp.ru/?main=task&id_task=509 ACMP #509 — Игра Jammed]
	* [http://acmp.ru/?main=task&id_task=695 ACMP #695 — Мифические шахматы]		* [http://acmp.ru/?main=task&id_task=695 ACMP #695 — Мифические шахматы]