С помощью нерекурсивного перебора с возвратом найти гамильтонов цикл в графе, заданном с помощью матрицы смежности на Си(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.

Текст программы: 
Код на 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