Ответ в теме: Найти Гамильтонов цикл в графе

      Комментарии к записи Ответ в теме: Найти Гамильтонов цикл в графе отключены
#2011

Чтобы найти гамильтонов цикл на Prolog можно чуть-чуть изменить правило поиска пути в глубину.
В статье описывается ориентированный граф, поэтому нужно правило, проверяющее существование ребра (без учета направления):

exist_edge(From, To):-
  edge(From, To); 
  edge(To, From).

Нам не нужно собирать дуги – гораздо удобнее получить все вершины пути, поэтому именно вершины будем помещать в список, накапливающий путь:

dfs(From, To, _, [From, To]):-
  exist_edge(From, To).
dfs(From, To, Buffer, [From|Path]):-
  exist_edge(From, X),
  not(member(X, Buffer)),
  dfs(X, To, [From|Buffer], Path).

Правило ищет путь между двумя вершинами, а не гамильтонов цикл. Если существует дуга, соединяющую текущую вершину с конечной – обе они добавляются к результату. В противном случае выбирается промежуточная вершина, в которую есть путь из текущей. Выполняется рекурсивный поиск пути из новой вершины. Все обработанные вершины добавляются в буфер чтобы исключить зацикливание. При выборе новой вершины выполняется проверка ее отсутствия в буфере. Так как нам нужно найти цикл – то в буфер изначально не помещается начальная вершина (это должно было бы делаться при вызове функции).

hamiltonian_graph(Path):-
  get_nodes(Nodes), length(Nodes, NodesCount),
  dfs(Node, Node, [], Path),
  list_to_set(Path, PathNodesSet),
  length(PathNodesSet, NodesCount), !.

Проверка наличия гамильтонового цикла сводится к поиску такого пути, что мощность множество его вершин совпадет с мощностью множества вершин всего графа.