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

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

При поиске Эйлерова цикла необходимо удалять пройденные дуги, т.к. второй раз по ним пройти все равно не получится, но за счет удаления возможно значительно оптимизировать программу. В связи с этим, ребра необходимо описывать как динамический предикат:
:- dynamic edge/2.
Если считать ребра неориентированными, то граф, соответствующий вашей картинке можно следующим образом:

edge(a, b).
edge(b, c).
edge(c, d).
edge(d, e).
edge(e, a).

edge(a, f).
edge(b, f).
edge(c, f).
edge(f, d).

edge(a, c).
edge(b, d).

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

remove_edge(From, To):-
  retract(edge(From, To)), !;
  retract(edge(To, From)).

Алгоритм поиска в глубину при этом должен быть изменен:

  • для проверки существования ребра используется exist_edge;
  • пройденные ребра удаляются из графа, но если путь не подошел – то восстанавливаются для продолжения поиска с возвратами;
  • в связи с удалением ребер отпадает необходимость накапливать информацию о пройденных дугах (она была необходима для избежания зацикливания), а следовательно, становятся ненужными проверки принадлежности текущей вершины к списку пройденных.
  • dfs(From, To, [From, To]):-
      exist_edge(From, To).
    dfs(From, To, [From|Path]):-
      exist_edge(From, X),
      remove_edge(From, X),
      (
        dfs(X, To, Path);
        assert(edge(From, X)), fail
      ).

    В таком случае, поиск Эйлерова цикла в графе сводится к запуску поиска в ширину (из вершины Node в вершину Node, т.к. путь должен являться циклом), и проверки того, что найденный при поиске путь содержит все ребра:

    eulerian_graph(Path):-
      dfs(Node, Node, Path),
      
      findall(edge(From, To), edge(From, To), Edges),
      length(Edges, 1).

    Проверка пути заключается в сборе всех ребе и сравнения их количества с единицей (т.к. все остальные ребра при поиске будут удалены). При этом все ребра помещаются в список и определяется его длина при помощи функции length.