Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Пример 2.2



Задан граф. Требуется:

1) найти остовное дерево с помощью метода поиска в ширину,

2) найти остовное дерево с помощью метода поиска в глубину.

Решение.

1) Выберем в качестве первой вершины, например, вершину , которая будет корнем остовного дерева. С вершиной смежными являются две вершины и . Поэтому в строящееся дерево добавляем два ребра и . Вершины и будут вершинами первого уровня.

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

2) При использовании метода поиска в глубину, как и в предыдущем методе в качестве первой вершины выберем, например, вершину . Эта вершина будет корнем остовного дерева.

В результате получаем корневое остовное дерево, которое изображено на рисунке.

,





Дата публикования: 2014-10-19; Прочитано: 725 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...