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
Прикрепленные файлы:
186350-271210.jpg