Алгоритмы на графах

Алгоритм Крускала (Краскала)

жүктеу/скачать 0,92 Mb.

бет	3/4
Дата	16.11.2022
өлшемі	0,92 Mb.
	#50601

1 2 3 4

Алгоритм Крускала (Краскала)

Крускал, Джозеф Б. (Kruskal, Joseph B.) 29.01.1928 –19.09.2010 Почетный профессор. Bell Labs, Lucent Technologies, Room 2C-281, Murray Hill, NJ 07974, USA

Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Минимальное остовное дерево

Пример связного графа и двух его остовных деревьев

Минимальным остовным деревом называется остовное дерево с минимальным общим весом его ребер.
2
3
5
2
1
4
3
6
2

Формулировка задачи

Для связного взвешенного графа G=(V,E) построить минимальный остов S=(V,T).

Вход: связный граф G=(V,E) и функция стоимости (весов) ребер c: E -> R.

Выход: минимальный остов S=(V,T).

Шаги алгоритма

Создается список ребер E, содержащий длину ребра, номер исходной вершины ребра, номер конечной вершины ребра.
Данный список упорядочивается в порядке возрастания длин ребер.
Просматривается список E и выбирается из него ребро с минимальной длиной, еще не включенное в результирующее дерево S и не образующее цикла с уже построенными ребрами.
Если все вершины графа включены в дерево S и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Пусть E содержит m ребер.

Пусть E содержит m ребер.
Упорядочим их по возрастанию стоимостей:
Последовательно для каждого i =1, ... , m определим множество ребер Ti:
Положим T=Tm. Выдать в качестве результата граф S=(V,T).

Шаги алгоритма

Пример работы алгоритма Крускала

Исходный граф
Минимальный остов графа
минимальный остов S=(V,T), где T=T8 ={ (a,g), (g,e), (g,c), (e,d), (a,b), (f,g)}

жүктеу/скачать 0,92 Mb.

Достарыңызбен бөлісу:

1 2 3 4