С помощью нерекурсивного перебора с возвратом найти гамильтонов цикл в графе, заданном с помощью матрицы смежности на Си(C++)
Добавил: | DMT |
Дата создания: | 28 апреля 2008, 14:13 |
Дата обновления: | 28 апреля 2008, 14:13 |
Просмотров: | 7600 последний сегодня, 12:30 |
Комментариев: | 0 |
С помощью нерекурсивного перебора с возвратом найти гамильтонов цикл в графе, заданном с помощью матрицы смежности на Си(C++). Описание алгоритма работы: Введем 3 массива: для учёта посещенных вершин, для сохранения текущего пути, и для запоминания индекса вершины, на которой произошёл переход на очередную ветку маршрута. 1) Флаги посещения устанавливаем в false. Индексы в массиве переходов устанавливаем в -1. Некоторую вершину выбираем текущей. 2) Для каждой смежной с текущей вершины (не учитывая предыдущие пути), если мы ее не посещали, сохраняем ее индекс в массиве переходов («на чём остановились»), текущей делаем найденную вершину и запоминаем ее в массиве пути. Если вершин, смежных с текущей вершиной, на которых мы ещё не были, нет, то в массиве «на чём остановились» для текущей вершины записываем -1, помечаем данную вершину как непосещенную, делаем «откат» на 1 вершину в пути назад, соответственно текущей становится предыдущая вершина. 3) Работа функции прекращается с результатом true, если заполнен массив пути и если существует путь между последней найденной вершиной и первой. Если путь не найден и «откат» невозможен, то возвращаем false. 4) Переходим к шагу 2. Текст программы:
|
