Консультация № 186350
11.06.2012, 15:04
95.44 руб.
0 1 1
Здравствуйте! Прошу помощи в следующем вопросе:
1.Используя граф на рис. (источник — вершина A), проиллюстрировать алгоритм просмотра вершин графа и построения остового дерева:
a.в глубину;
b.в ширину.
В решении указать порядок просмотра вершин графа, динамику изменения состояния стека и очереди, маркировку вершин. Решение проиллюстрировать рисунком.

Обсуждение

давно
Профессор
230118
3054
12.06.2012, 10:18
общий
это ответ
Здравствуйте, Андрей!

Для просмотра дерева в глубину используем стек.
Вершина A
Стек A J
Стек A J D
Стек A J D G
Стек A J D G I
Стек A J D G I C
Стек A J D G I C K
Стек A J D G I C K B
Стек A J D G I C K B H
Стек A J D G I C K B H F
Стек A J D G I C K B H F L
Стек A J D G I C K B H F L M
Все соседние с M вершины просмотрены
Стек A J D G I C K B H F L
Стек A J D G I C K B H F
Стек A J D G I C K B H
Стек A J D G I C K B
Стек A J D G I C K
Стек A J D G I C
Стек A J D G I
Стек A J D G
Стек A J D
Стек A J
Стек A
Стек пуст, все вершины просмотрены
Для просмотра дерева в глубину используем очередь.
Просмотренные вершины помечаем
Вершина A
очередь A
очередь J L
очередь D G F M
очередь I C K B H
Все вершины просмотрены
Алгоритм Краскала построения остовного дерева
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
Выбираем ребро AJ
Выбираем ребро JL
Выбираем ребро DL
Выбираем ребро DG
Выбираем ребро IG
Выбираем ребро IC
Выбираем ребро KC
Выбираем ребро KB
Выбираем ребро HF
Выбираем ребро HM
Прикрепленные файлы:
Форма ответа