Новые сообщения · Правила  
  • Страница 1 из 1
  • 1
Обобщенный поиск на графе, основанный на очереди с приоритет
Доброго времени суток!=) Помогите, пожалуйста, создать программу: "Обобщенный поиск на графе, основанный на очереди с приоритетами", входные данные:количество вершин графа, ребра и их вес, выход: порядок посещения вершин.

Уточнение:
Обобщение состоит между методом поиска в глубину и поиском в ширину. Основной принцип: на примере поиска в ширину, но вместо понятия очередь употребляется термин бахрома для описания множества ребер, которые являются кандидатами для следующего включения в дерево поиска. Начав с петли исходной вершины в бахроме и пустого дерева до тех пор, пока бахрома не станет пустой, выполняется следующая операция: берем ребро с наименьшим весом из заданной исходной вершины и переносим его в дерево, если вершина в которую оно ведет еще не посещалась, переходим на эту вершину и помещаем в бахрому все ребра, которые ведут из этой вершины в еще не посещенные вершины, затем из бахромы снова выбираем ребро с наименьшим весом и повторяем действия. Суть очереди с приоритетами в данном случае заключается в последовательном извлечении ее элементов (ребер) в зависимости от их значения (веса). Все вершины графа должны быть посещены.

ЗЫ: Заранее Огромное Спасибо=))

1 | Автор: djds | 2011-03-28, 22:28   |  Репутация: [ + 0 ]
1 | Автор: djds | 2011-03-28, 22:28   |  Репутация: [ + 0 ]
  • Страница 1 из 1
  • 1
Поиск: