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

ASA в 07:03, 6 июля 2022

2022-07-06T07:03:43Z

← Предыдущая версия		Версия от 07:03, 6 июля 2022
Строка 48:		Строка 48:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html kruskal_min_spanning_tree]</code>), сложность <math>O(m \ln m)</math>.
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]
	** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#merge-local-minimum-spanning-trees merge_local_minimum_spanning_trees]</code> реализует алгоритм Крускала;
	** функции <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</code> сочетают [[алгоритм Борувки]] и алгоритм Крускала.
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html minimum_spanning_tree]</code>).
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html KruskalMinimumSpanningTree]</code>).

	== Литература ==		== Литература ==

ASA в 13:46, 14 марта 2018

2018-03-14T13:46:57Z

← Предыдущая версия		Версия от 13:46, 14 марта 2018
Строка 72:		Строка 72:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Kruskal's algorithm]]

ASA в 14:12, 6 марта 2018

2018-03-06T14:12:44Z

← Предыдущая версия		Версия от 14:12, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:15, 29 июля 2015

2015-07-29T11:15:18Z

← Предыдущая версия		Версия от 11:15, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Строка 6:		Строка 6:
	В отличие от алгоритмов [[Алгоритм Прима\|Прима]] и [[Алгоритм Борувки\|Борувки]], алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до <math>O(m \alpha(m, n))</math>.		В отличие от алгоритмов [[Алгоритм Прима\|Прима]] и [[Алгоритм Борувки\|Борувки]], алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до <math>O(m \alpha(m, n))</math>.

	=== Математическое описание ===		=== Математическое описание алгоритма ===

	Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).		Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).
Строка 18:		Строка 18:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Строка 28:		Строка 28:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Основная часть алгоритма Крускала является последовательной, так как рёбра рассматриваются в порядке возрастания веса строго одно за другим. На начальном этапе может быть применена параллельная быстрая сортировка для упорядочения рёбер по весу.		Основная часть алгоритма Крускала является последовательной, так как рёбра рассматриваются в порядке возрастания веса строго одно за другим. На начальном этапе может быть применена параллельная быстрая сортировка для упорядочения рёбер по весу.
Строка 41:		Строка 41:
	Параллельная схема вычисления устроена следующим образом. Рёбра графа распределяются между процессами примерно поровну. Каждый процесс строит минимальный остовный лес из своих рёбер, используя алгоритм Крускала. После этого процессы выполняют коллективную операцию редукции по приведённой формуле, используя алгоритм Крускала без сортировки рёбер, так как построенные ранее деревья уже записаны в порядке возрастания весов рёбер.		Параллельная схема вычисления устроена следующим образом. Рёбра графа распределяются между процессами примерно поровну. Каждый процесс строит минимальный остовный лес из своих рёбер, используя алгоритм Крускала. После этого процессы выполняют коллективную операцию редукции по приведённой формуле, используя алгоритм Крускала без сортировки рёбер, так как построенные ранее деревья уже записаны в порядке возрастания весов рёбер.

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
Строка 62:		Строка 68:

	<references />		<references />

			[[Категория:Начатые статьи]]

Daryin: /* Описание ресурса параллелизма алгоритма */

2015-07-08T13:07:58Z

Описание ресурса параллелизма алгоритма

@@ Строка 29: / Строка 29: @@
 === Информационный граф ===
 === Описание ресурса параллелизма алгоритма ===
 === Описание входных и выходных данных ===
 === Свойства алгоритма===

Daryin: Отмена правки 2086, сделанной участником Daryin (обс.)

2015-07-08T12:54:41Z

Отмена правки 2086, сделанной участником Daryin (обс.)

← Предыдущая версия		Версия от 12:54, 8 июля 2015
Строка 29:		Строка 29:
	=== Информационный граф ===		=== Информационный граф ===
	=== Описание ресурса параллелизма алгоритма ===		=== Описание ресурса параллелизма алгоритма ===

	Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

	~~Алгоритм Борувки основан на следующих двух свойствах задачи:~~
	* '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву.
	* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

	В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются.

	=== Описание входных и выходных данных ===		=== Описание входных и выходных данных ===
	=== Свойства алгоритма===		=== Свойства алгоритма===

Daryin: /* Описание ресурса параллелизма алгоритма */

2015-07-08T12:53:22Z

Описание ресурса параллелизма алгоритма

← Предыдущая версия		Версия от 12:53, 8 июля 2015
Строка 29:		Строка 29:
	=== Информационный граф ===		=== Информационный граф ===
	=== Описание ресурса параллелизма алгоритма ===		=== Описание ресурса параллелизма алгоритма ===

			Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

			Алгоритм Борувки основан на следующих двух свойствах задачи:
			* '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву.
			* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

			В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются.

	=== Описание входных и выходных данных ===		=== Описание входных и выходных данных ===
	=== Свойства алгоритма===		=== Свойства алгоритма===

Daryin: /* Математическое описание */

2015-07-08T12:52:18Z

Математическое описание

← Предыдущая версия		Версия от 12:52, 8 июля 2015
Строка 14:		Строка 14:
	* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.		* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

	В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На каждом шаге из рёбер, ещё не рассмотренных на предыдущих шагах, выбирается ребро с минимальным весом. Если оно соединяет два различных фрагмента, то оно добавляется в минимальное ~~опорное~~ дерево, а фрагменты склеиваются. В противном случае это ребро отбрасывается.		В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На каждом шаге из рёбер, ещё не рассмотренных на предыдущих шагах, выбирается ребро с минимальным весом. Если оно соединяет два различных фрагмента, то оно добавляется в минимальное остовное дерево, а фрагменты склеиваются. В противном случае это ребро отбрасывается.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

Daryin: /* Математическое описание */

2015-07-08T12:49:06Z

Математическое описание

← Предыдущая версия		Версия от 12:49, 8 июля 2015
Строка 7:		Строка 7:

	=== Математическое описание ===		=== Математическое описание ===

			Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

			Алгоритм Крускала основан на следующих двух свойствах задачи:
			* '''Минимальное ребро графа'''. Если <math>e^*</math> – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву..
			* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

			В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На каждом шаге из рёбер, ещё не рассмотренных на предыдущих шагах, выбирается ребро с минимальным весом. Если оно соединяет два различных фрагмента, то оно добавляется в минимальное опорное дерево, а фрагменты склеиваются. В противном случае это ребро отбрасывается.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

Daryin: /* Последовательная сложность алгоритма */

2015-07-08T12:41:11Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 12:41, 8 июля 2015
Строка 12:		Строка 12:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время <math>m \ln m</math>, затем просматриваются в порядке увеличения веса за время <math>O(m)</math> ~~(например, с помощью быстрой сортировки)~~, при этом для хранения информации о текущих фрагментах используется [[система непересекающихся множеств]]<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> с общим временем работы <math>O(m \alpha(m, n))</math>. Итоговая сложность алгоритма <math>O(m \ln m)</math>.		Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время <math>m \ln n</math> (например, с помощью быстрой сортировки), затем просматриваются в порядке увеличения веса за время <math>O(m)</math>, при этом для хранения информации о текущих фрагментах используется [[система непересекающихся множеств]]<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> с общим временем работы <math>O(m \alpha(m, n))</math>. Итоговая сложность алгоритма <math>O(m \ln n)</math>.

	Как видно, наибольшую сложность имеет этап сортировки, при этом большая часть рёбер сортируется напрасно: они всё равно будут отброшены, как принадлежащие одному фрагменту. Использование инкрементальной быстрой сортировки<ref>Navarro, Gonzalo, and Rodrigo Paredes. “On Sorting, Heaps, and Minimum Spanning Trees.” Algorithmica 57, no. 4 (March 23, 2010): 585–620. doi:10.1007/s00453-010-9400-6.</ref> (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет <math>O(m + n \ln^2 n)</math>.		Как видно, наибольшую сложность имеет этап сортировки, при этом большая часть рёбер сортируется напрасно: они всё равно будут отброшены, как принадлежащие одному фрагменту. Использование инкрементальной быстрой сортировки<ref>Navarro, Gonzalo, and Rodrigo Paredes. “On Sorting, Heaps, and Minimum Spanning Trees.” Algorithmica 57, no. 4 (March 23, 2010): 585–620. doi:10.1007/s00453-010-9400-6.</ref> (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет <math>O(m + n \ln^2 n)</math>.