|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.03.2011, 22:51 | #1 |
Новичок
Джуниор
Регистрация: 28.03.2011
Сообщений: 1
|
Обобщенный поиск на графе, основанный на очереди с приоритетами
Доброго времени суток!=) Помогите, пожалуйста, создать программу: "Обобщенный поиск на графе, основанный на очереди с приоритетами", входные данные:количество вершин графа, ребра и их вес, выход: порядок посещения вершин.
Уточнение: Обобщение состоит между методом поиска в глубину и поиском в ширину. Основной принцип: на примере поиска в ширину, но вместо понятия очередь употребляется термин бахрома для описания множества ребер, которые являются кандидатами для следующего включения в дерево поиска. Начав с петли исходной вершины в бахроме и пустого дерева до тех пор, пока бахрома не станет пустой, выполняется следующая операция: берем ребро с наименьшим весом из заданной исходной вершины и переносим его в дерево, если вершина в которую оно ведет еще не посещалась, переходим на эту вершину и помещаем в бахрому все ребра, которые ведут из этой вершины в еще не посещенные вершины, затем из бахромы снова выбираем ребро с наименьшим весом и повторяем действия. Суть очереди с приоритетами в данном случае заключается в последовательном извлечении ее элементов (ребер) в зависимости от их значения (веса). Все вершины графа должны быть посещены. ЗЫ: Заранее Огромное Спасибо=)) |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск маршрута в графе. | vedro-compota | Общие вопросы по программированию, компьютерный форум | 4 | 16.04.2013 09:23 |
Поиск Эйлерова цикла в графе | Danion | Помощь студентам | 3 | 22.05.2010 18:47 |
Поиск циклов в графе.Си. | Karabas | Помощь студентам | 0 | 22.10.2009 23:57 |
Алгоритм Дейкстры поиска путей в графе. Как реализовать с помощью приоритетной очереди? | Zefick | Помощь студентам | 0 | 04.06.2009 14:03 |
Поиск в графе | Selebro | Общие вопросы C/C++ | 0 | 14.12.2008 17:06 |