Описание алгоритма нахождения минимального порождающего дерева

Число вершин заданного графа n≥2. Этот алгоритм приводит к искомому результату за n-1 шаг.

1-й шаг. Пометим произвольную вершину графа. Из ребер звезды, порожденной этой вершиной, выберем ребро наибольшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результате две вершины графа оказываются помеченными.

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

2-шаг. Каждая из двух помеченных вершин графа порождает свою звезду. Рассмотрим все ребра этих звезд, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину в которую входит это выбранное ребро. В результате выделенными оказываются два ребра графа, а помеченными уже три его вершины. Обозначим полученное дерево через λ₂. Ясно, что λ₁ λ₂.

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

3-й шаг. Каждая их трех помеченных вершин графа порождает свою звезду. Рассмотрим все ребра этих звезд, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результате выделенными оказываются три ребра графа, а помеченными уже четыре его вершины.

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

На каждом шаге и число выделенных ребер графа, и число помеченных увеличиваются ровно на единицу. Тем самым, после n — 1-го шага количество выбранных ребер станет равным n—1 и все n вершин графа окажутся помеченными.

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

Задача №2.

Найти кратчайшие маршруты из А в любой другой пункт данного графа