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

      Комментарии к записи Алгоритм Крускала — минимальное остовное дерево отключены

Главная Форумы Программирование Алгоритмы и структуры данных Алгоритмы теории графов Алгоритм Крускала — минимальное остовное дерево

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 10 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #2806

    questioner
    Участник

    Нужно описать и рассмотреть на примерах построение  кратчайшего остовного дерева (минимального покрывающего дерева, оптимального каркаса) алгоритмом Крускала. Этот алгоритм является жадным, т.е. на каждом шаге должно выбираться самое короткое ребро, принадлежащее остову. Опишите алгоритм в деталях. Желательно построить блок-схему.

  • #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

Для ответа в этой теме необходимо авторизоваться.