Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.03.2011, 22:51   #1
djds
Новичок
Джуниор
 
Регистрация: 28.03.2011
Сообщений: 1
По умолчанию Обобщенный поиск на графе, основанный на очереди с приоритетами

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

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


ЗЫ: Заранее Огромное Спасибо=))
djds вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск маршрута в графе. 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