38. Построение остовного дерева с заданной корневой вершиной.
Цикл – путь, у
которого начальная и конечная вершины
совпадают.
Дерево – граф без
циклов.
Остовное дерево
графа – дерево, включающее в себя все
вершины заданного графа.
Нахождение остовного
дерева – практически важная задача.
Например, при разработке локальных
компьютерных сетей избегают присутствия
в цепи циклов (т.к. в этом случае связь
между некоторыми компьютерами
дублируются), т.е. стремятся спроектировать
компьютерную сеть в виде дерева.
Легко видеть, что
дерево, включающее в себя n
вершин состоит из (n-1)
ребра. Если добавлена новая вершина, то
ее надо соединить с какой-либо вершиной
графа еще одним ребром.
Построение остовного
дерева с заданной корневой вершиной.
Для решения этой задачи можно использовать
оба алгоритма обхода всех вершин графа
(как в глубину, так и в ширину). Каждый
из этих алгоритмов запрещает повторное
посещение уже рассмотренных вершин
(используется признак новая – не новая
вершина). Тем самым гарантируется
отсутствие циклов в маршруте обхода
всех вершин графа, т.е. полученный маршрут
обхода является остовным деревом. Роль
корня в этом дереве исполняет исходная
вершина.
Вид остовного
дерева зависит
1) от выбранного
алгоритма,
2) для алгоритма в
глубину зависит от порядка выбора новых
соседей.
