Алгоритм Краскала: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Алгоритм Краскала''' (''J.B.Kruskal'') - '''1.''' Алгоритм построения каркаса графа пу...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Алгоритм Краскала''' (''J.B.Kruskal'') - | '''Алгоритм Краскала''' ([[J.B.Kruskal|''J.B.Kruskal'']]) - | ||
'''1.''' Алгоритм построения каркаса графа путем | '''1.''' [[Алгоритм|Алгоритм]] построения [[каркас|каркаса]] [[граф|графа]] путем | ||
последовательного удаления в соответствии с некоторой | последовательного удаления в соответствии с некоторой | ||
упорядоченностью ребер графа без нарушения связности | упорядоченностью [[ребро|ребер]] графа без нарушения связности | ||
получаемой части графа. '''2.''' Алгоритм построения каркаса | получаемой части графа. '''2.''' Алгоритм построения каркаса | ||
наименьшего веса описанным выше методом, но с предварительным | наименьшего веса описанным выше методом, но с предварительным | ||
Версия от 15:09, 24 сентября 2009
Алгоритм Краскала (J.B.Kruskal) - 1. Алгоритм построения каркаса графа путем последовательного удаления в соответствии с некоторой упорядоченностью ребер графа без нарушения связности получаемой части графа. 2. Алгоритм построения каркаса наименьшего веса описанным выше методом, но с предварительным упорядочением ребер в порядке неубывания весов.
На основе А.К. созданы многочисленные модификации.
Литература
[Кристофидес],
[Евстигнеев-Касьянов/94]