Ответ в теме: Алгоритм Крускала – минимальное остовное дерево

      Комментарии к записи Ответ в теме: Алгоритм Крускала – минимальное остовное дерево отключены
#2808

Остовное дерево (каркас) графа – это связный подграф, в который входят все вершины исходного графа. Требование связности означает, что из любой вершины дерева должен существовать путь в любую другую вершину.

Алгоритм Крускала строит минимальное остовное дерево, т.е. такой каркас, что сумма длин ребер в нем должна быть минимальной возможной. При этом он последовательно выбирает и добавляет ребра, придерживаясь жадной стратегии – на каждом шаге выбирается ребро минимального веса, соединяющее ранее не соединенные поддеревья (локально наилучший вариант, однако конкретно для этого алгоритма доказано, что полученное решение будет глобально оптимальным).

На вход алгоритма подается:

  1. начальный начальный список поддеревьев (называемый лесом в теории графов), представляющий собой просто список всех вершин графа;
  2. список дуг графа, упорядоченный по возрастанию.

Цель алгоритма – выбрать такое подмножество дуг исходного графа, чтобы все вершины были соединены, а длинна дуг была минимальной.

Согласно алгоритму, последовательно перебираются ребра (в порядке возрастании веса), если концы ребра принадлежат разным поддеревьям – ребро добавляется к остову, поддеревья объединяются, иначе – ребро пропускается. В обоих случаях остальные ребра обрабатываются рекурсивно. Процесс продолжается до тех пор, пока не остается одно дерево – оно и будет являться остовом. Рассмотрим этот процесс на примере, пусть дан граф:

graph_example

Изначально, у нас есть семь деревьев (каждая вершина рассматривается как дерево) и набор дуг, отсортированных по возрастанию:

kruskal_algorithm_init

На рисунке цветом выделено текущее рассматриваемое ребро. Его концы принадлежат различным деревьям, поэтому деревья можно объединить, а ребро необходимо добавить к каркасу:

kruskal_algorithm_first_step

Аналогично выполняется обработка второго ребра (d-c):

kruskal_algorithm_second_step

Так, на каждом шаге  количество несвязанных друг с другом деревьев будет уменьшаться на единицу и к пятому шагу от семи деревьев останется лишь три. При этом для дуги (b-c) окажется, что оба ее конца принадлежат одному и тому же дереву, поэтому ее следует просто пропустить (ведь между этими вершинами уже существует путь):

kruskal_algorithm_shift_edge

После этого к остову может быть добавлена дуга (e-g) и пропущена дуга (a-b):

kruskal_algorithm_step_6

Дуга (f-g) будет последней, добавленной к остову, т.к. все вершины графа окажутся связаны остовом (останется лишь одно дерево):

kruskal_algorithm_finished

В результате получен минимальный каркас графа.

Формально алгоритм Крускала можно представить в виде следующей блок-схемы:

kruskal_algorithm_flowchart