Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 9. Графы. Каркас. Алгоритмы Прима и Краскала.

Пусть дан взвешенный неориентированный связный граф с N вершинами и M ребрами.

Введем несколько определений:
Остовное дерево или каркас графа - подграф графа, который:
  1) содержит все вершины графа,
  2) является деревом.

Компонента связности - это такой связный подграф нашего графа, что добавление любой вершины ведет к потере связности.

Требуется найти каркас минимального вес для заданного графа.

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

Удалим все ребра из нашего графа. Теперь отсортируем их по неубыванию весов и будем по очереди пытаться добавить их в наш граф. Если в результате добавления ребра образуется цикл, то добавлять это ребро не будем, иначе добавим его. При добавлении ребра в граф цикл образуется тогда и только тогда, когда вершины, которые соединяет ребро, находятся в одной компоненте связности. В результате у нас получится минимальное остовное дерево.

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

На каждом шаге алгоритма Прима есть множество помеченных вершин. Вначале оно состоит из одной произвольной вершины. Шаг алгоритма представляет собой следующую последовательнность действий:

• Среди всех ребер, соединяющих помеченную и непомеченную вершины, выберем ребро с минимальным весом.
• Добавим это ребро в каркас; вершину, являющуюся непомеченным концом данного ребра, добавим в множество помеченных вершин.