Алгоритм Прима - История изменений

Ctrlalt в 03:52, 26 декабря 2021

2021-12-26T03:52:48Z

← Предыдущая версия		Версия от 03:52, 26 декабря 2021
Строка 1:		Строка 1:
			{\| width="100%"
			\| width="50%" \|
			'''O(V<sup>2</sup>)'''
			int prim(vector<vector<Edge>> &graph) {
			vector<bool> visited(graph.size());
			vector<int> dist(graph.size(), 1e9);
			dist[0] = 0;

			int mstWeight = 0;

			for (int i = 0; i < graph.size(); i++) {
			int nearestV = -1;
			for (int v = 0; v < graph.size(); v++)
			if (!visited[v] && (nearestV == -1 \|\| dist[v] < dist[nearestV]))
			nearestV = v;

			visited[nearestV] = true;
			mstWeight += dist[nearestV];

			for (auto &[from, to, weight] : graph[nearestV])
			if (dist[to] > {{Changed\|weight}})
			dist[to] = {{Changed\|weight}};
			}

			return mstWeight;
			}





			Полностью аналогично реализации Дейкстры за O(V<sup>2</sup>).

			Единственная разница — в качестве расстояния до вершины используется длина не всего пути, а последнего ребра.
			\| width="50%" \|
			'''O(ElogV)'''
			int prim(vector<vector<Edge>> &graph) {
			{{Changed\|1=vector<bool> visited(graph.size());}}
			vector<int> dist(graph.size(), 1e9);
			set<pair<int, int>> unvisited;
			dist[0] = 0;
			unvisited.insert({ dist[0], 0 });

			int mstWeight = 0;

			while (!unvisited.empty()) {
			int nearestV = unvisited.begin()->second;
			unvisited.erase(unvisited.begin());

			{{Changed\|1=visited[nearestV] = true;}}
			mstWeight += dist[nearestV];

			for (auto &[from, to, weight] : graph[nearestV]) {
			if ({{Changed\|!visited[to]}} && dist[to] > {{Changed\|weight}}) {
			unvisited.erase({ dist[to], to });
			dist[to] = {{Changed\|weight}};
			unvisited.insert({ dist[to], to });
			}
			}
			}

			return mstWeight;
			}

			Почти аналогично реализации Дейкстры за O(ElogV).

			В качестве расстояния до вершины используется длина не всего пути, а последнего ребра.

			В отличие от Дейкстры, использование visited обязательно (контртест — 1 2 2, 2 3 1).
			\|}

	== Ссылки ==		== Ссылки ==
	* [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима]		* [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима]

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

2016-01-27T20:12:35Z

Ссылки

← Предыдущая версия		Версия от 20:12, 27 января 2016
Строка 2:		Строка 2:
	* [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима]		* [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]
			* [http://brestprog.neocities.org/lections/mst.html brestprog.neocities.org — Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала)]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]
	* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees]		* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees]

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

2014-09-29T20:06:45Z

Ссылки

← Предыдущая версия		Версия от 20:06, 29 сентября 2014
Строка 4:		Строка 4:
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]
	* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees]		* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees]
			* [http://visualgo.net/mst.html VisuAlgo — Minimum Spanning Tree]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/Prim.java CodeLibrary — Prim's algorithm in O(V^2)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/Prim.java CodeLibrary — Prim's algorithm in O(V^2)]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimHeap.java CodeLibrary — Prim's algorithm in O(ElogV)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimHeap.java CodeLibrary — Prim's algorithm in O(ElogV)]

Ctrlalt в 05:35, 19 августа 2014

2014-08-19T05:35:13Z

← Предыдущая версия		Версия от 05:35, 19 августа 2014
Строка 3:		Строка 3:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]
			* [http://algs4.cs.princeton.edu/lectures/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/Prim.java CodeLibrary — Prim's algorithm in O(V^2)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/Prim.java CodeLibrary — Prim's algorithm in O(V^2)]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimHeap.java CodeLibrary — Prim's algorithm in O(ElogV)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimHeap.java CodeLibrary — Prim's algorithm in O(ElogV)]

Ctrlalt в 04:20, 19 августа 2014

2014-08-19T04:20:22Z

← Предыдущая версия		Версия от 04:20, 19 августа 2014
Строка 3:		Строка 3:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]
			* [http://github.com/indy256/codelibrary/blob/master/java/src/Prim.java CodeLibrary — Prim's algorithm in O(V^2)]
			* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimHeap.java CodeLibrary — Prim's algorithm in O(ElogV)]
			* [http://github.com/ADJA/algos/blob/master/Graphs/MSTPrim.cpp Algos — Minimum spanning tree using Prim algorithm]

	[[Category:Минимальное остовное дерево]]		[[Category:Минимальное остовное дерево]]

Ctrlalt: Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима] * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B…»

2014-08-13T19:46:49Z

Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима] * [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B…»

Новая страница

== Ссылки ==
* [http://e-maxx.ru/algo/mst_prim e-maxx.ru — Алгоритм Прима]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Прима]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 8]

[[Category:Минимальное остовное дерево]]