Распечатайте все гамильтоновы циклы в неориентированном графе

Опубликовано: 22 Сентября, 2022

Для заданного неориентированного графа, состоящего из N узлов в виде графа матрицы смежности[][] размера N*N , задача состоит в том, чтобы напечатать все гамильтоновы циклы, возможные в данном неориентированном графе (принимая начальную вершину за «0»).

A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in the graph) from the last vertex to the first vertex of the Hamiltonian Path.

Примеры:

Input: graph[][] = {{0, 1, 1, 0, 0, 1}, {1, 0, 1, 0, 1, 1}, {1, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1}, {1, 1, 0, 0, 1, 0}}
Output: 
0 1 2 3 4 5 0 
0 1 5 4 3 2 0 
0 2 3 4 1 5 0 
0 2 3 4 5 1 0 
0 5 1 4 3 2 0 
0 5 4 3 2 1 0 
Explanation:
All Possible Hamiltonian Cycles for the following graph (with the starting vertex as 0) are 

  1. {0 → 1 → 2 → 3 → 4 → 5 → 0}
  2. {0 → 1 → 5 → 4 → 3 → 2 → 0}
  3. {0 → 2 → 3 → 4 → 1 → 5 → 0}
  4. {0 → 2 → 3 → 4 → 5 → 1 → 0}
  5. {0 → 5 → 1 → 4 → 3 → 2 → 0}
  6. {0 → 5 → 4 → 3 → 2 → 1 → 0}

Input: graph[][] = {{0, 1, 0, 1, 1, 0, 0}, {1, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 1}, {1, 0, 1, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 1, 1, 0, 1}, {0, 0, 1, 0, 0, 1, 0}}
Output: No Hamiltonian Cycle possible
Explanation:
For the given graph, no Hamiltonian Cycle is possible: 

Подход: данная проблема может быть решена с помощью поиска с возвратом для генерации всех возможных гамильтоновых циклов. Выполните следующие шаги, чтобы решить проблему:

  • Создайте вспомогательный массив, скажем, path[] для хранения порядка обхода узлов и логический массив посещений[] для отслеживания вершин, включенных в текущий путь.
  • Сначала добавьте исходную вершину (в данном случае «0») к пути .
  • Теперь рекурсивно добавляйте вершины к пути одну за другой, чтобы найти цикл.
  • Перед добавлением вершины в путь проверьте, является ли рассматриваемая вершина смежной с ранее добавленной вершиной или нет, и не находится ли она уже в пути . Если такая вершина найдена, то добавляем ее в путь и помечаем ее значение как истинное в массиве Visit[] .
  • Если длина пути становится равной N и есть ребро из последней вершины пути в 0 , то выведите массив путей.
  • После выполнения вышеуказанных шагов, если такого пути не существует, выведите Нет гамильтоновых циклов возможных .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N!)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ