Построение МОД жадным алгоритмом
Обозначим вершины в графе:
Составим таблицу ребер графа:
1) выбираем ребро с минимальным весом, которое не вызывает появление цикла в остове ah=1 2) bi=1 3) ef=1 4) ai=2 5) de=2 6) fg=2 7) cd=3 8) ce=3 пропускаем, т.к. появится цикл. 9) ei=3 10) все остальные ребра образуют циклы. МОД графа получено. Построение МОД алгоритмом Прима Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Таким образом, при выполнении каждого шага алгоритма, высота формируемого дерева увеличивается на 1. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.
1) В качестве начальной выберем вершину E и найдем инцидентное ей ребро с минимальным весом ef=1 2) Далее найдем ребро с минимальным весом среди инцидентных вершинам дерева: ed=2 3) fg=2 4) cd=3 5) ei=3 6) bi=1 7) ai=2 8) ah=1 9) Все вершины задействованы, МОД графа получено
|
