Алгоритмы построения остовных деревьев

Остовное дерево (каркас) - это дерево, построенное из множества вершин исходного графа, и подмножества ребер исходного графа.

Мы будем решать задачу построения каркаса взвешенного графа, имеющего минимальный возможный вес. Естественно, что задача построения каркаса ставится только для неориетированных графов. Если исходный граф не является связным, то построить каркас не получится.

Алгоритм Прима

Разбиваем все вершины графа на два множества - уже включенные в каркас и еще не включенные. Изначально ни одна вершина графа в каркас не включена.

Алгоритм Краскала (в некоторых переводах - Крускала)

Отсортируем все ребра графа по возрастанию веса. Далее просматриваем все ребра в этом порядке и каждое следующее ребро добавляем к каркасу, если его добавление не приводит к появлению цикла.

Как это реализовать. Для каждой вершины полезно хранить, какой компоненте связности она принадлежит. Изначально у нас нет ни одного ребра, и каждая вершина сама себе компонента связности (т.е. вершина с номером i принадлежит компоненте с номером i).

Теперь мы начинаем по очереди просматривать все ребра. Пусть мы берем очередное ребро. Если его концы принадлежат одной компоненте связности, то добавление этого ребра к каркасу приведет к появлению цикла - такое ребро мы отбрасываем. Если же вершины ребра принадлежат разным компонентам связности, то добавление этого ребра к появлению цикла не приведет, и мы это ребро к каркасу добавляем. Однако в результате добавления ребра эти две компоненты связности объединяются. Пусть мы добавили ребро, соединяющее вершины v и w, которые принадлежали компонентам связности b[v] и b[w] соответственно. Тогда нужно все значенияб равные b[w] в массиве b заменить на значения b[v]. Заметьте, что не достаточно заменить только значение в вершине w, так как эта вершина могла уже лежать в одной компоненте связности с еще какими-то вершинами, и это все становится теперь одной компонентой.