С помощью нерекурсивного перебора с возвратом найти гамильтонов цикл в графе, заданном с помощью матрицы смежности на Си(C++)


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

Текст программы:
Код на C++
  1. #include <stdio.h>
  2.  
  3. #define n 10
  4.  
  5. bool c[n];
  6. int path[n], r[n];
  7.  
  8. int a[n][n]=
  9. {
  10. 0,0,0,0,0,1,0,0,0,0,
  11. 0,0,1,0,0,0,1,0,0,0,
  12. 0,1,0,1,0,0,0,1,0,0,
  13. 0,0,1,0,1,0,0,0,1,0,
  14. 1,0,0,1,0,0,0,0,0,1,
  15. 0,0,0,0,0,0,1,0,0,1,
  16. 0,0,0,1,0,0,0,1,0,0,
  17. 0,0,0,0,1,0,0,0,0,0,
  18. 0,0,0,0,0,0,0,0,0,1,
  19. 0,0,0,0,0,0,0,0,0,0
  20. };
  21.  
  22. bool gamilton(int start)
  23. {
  24. int cur = start;
  25. int next = 0;
  26. path[next++] = cur;
  27. bool found;
  28. while (true)
  29. {
  30. found = false;
  31. c[cur] = true;
  32. for (int i = r[cur] + 1; i < n; i++)
  33. if (i != cur && (a[i][cur] || a[cur][i]) && !c[i])
  34. {
  35. found = true;
  36. r[cur] = i;
  37. path[next++] = cur = i;
  38. break;
  39. }
  40. if (!found)
  41. {
  42. if (next == 1) return false;
  43. r[cur] = -1;
  44. c[cur] = false;
  45. cur = path[--next - 1];
  46. }
  47. else
  48. if (next == n && (a[cur][start] || a[start][cur])) return true;
  49. }
  50. }
  51.  
  52. main()
  53. {
  54. int i;
  55. printf("Solution:\n");
  56. for (i = 0; i < n; i++) { c[i] = false; r[i] = -1; }
  57. if (gamilton(1))
  58. {
  59. for (i = 0; i < n; i++) printf("%d ", path[i]);
  60. printf("%d\n", path[0]);
  61. }
  62. else
  63. printf("Solution Not Found!\n");
  64. }
При использовании обязательна ссылка на http://DMTSoft.ru
up