Поиск циклов и петель в графе

      Комментарии к записи Поиск циклов и петель в графе отключены

Помечено: , , , ,

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 8 мес. назад.

  • Автор
    Сообщения
  • #2506

    questioner
    Участник

    Мне необходимо выполнить поиск циклов и петель в графе чтобы проверить является граф деревом или нет. Как подойти к решению задачи? Использовать поиск в ширину?

    Вложения:
  • #2507

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

    self_loop(Node):-
      edge(Node, Node).

    Однако для поиска циклов граф удобнее преобразовать в список (не использовать записи базы данных), т.к. при поиске в ширину пройденные дуги удобно удалять, но при этом не хотелось бы испортить исходный граф. При этом если вы используете SWI Prolog, то записи базы данных могли бы быть такими — edge(From, To), однако при использовании Visual Prolog с этим могли бы возникнуть проблемы — чтобы получить набор дуг можно хранить в базе данных записи следующего вида: data(edge(From, To)). Формат записей не сильно скажется на функции сбора всех записей в список:

    database_to_graph_list(Graph):-
      findall(Edge, data(Edge), Graph).

    Теперь наш граф представлен в виде списка, для поиска элемента в котором можно применять функцию member, а для удаления — delete. Для поиска цикла (т.е. пути, начало и конец которого совпадают) из некоторой вершины мы можем:

    • постепенно (поиском в глубину) выбирать (и удалять) дуги, ведущие из текущей вершины, и помещать концы дуг в список пройденных вершин (ProcessedNodes) до тех пор пока очередная вершина не окажется в списке пройденных (цикл найден);
    • если из текущей вершины некуда пойти (из нее не выходит ни одна дуга) — выполняется откат (срабатывает механизм поиска в возвратами) и поиск другого (обходного) пути.

    loop_graph(A, Graph, ProcessedNodes, [A|ProcessedNodes]):-
      member(edge(A, X), Graph),
      member(X, [A|ProcessedNodes]), !.
    loop_graph(A, Graph, ProcessedNodes, [A|Loop]):-
      member(edge(A, X), Graph),
      delete(Graph, edge(A, X), NewGraph),
      loop_graph(X, NewGraph, [A|ProcessedNodes], Loop).

    Данный фрагмент ищет не только циклы, но и петли благодаря тому, что к списку пройденных вершин в последнем вызове member в первом правиле добавляется исходный узел.
    Приведенный фрагмент кода вернет все найденные циклы с началом в заданной вершине. Для того, чтобы получить все циклы в графе нужно оставить начальную вершину анонимной. При этом, если мы захотим проверить является ли граф деревом, мы должны будем использовать оператор NOT:
    NOT(loop_graph(_X, Graph, [], _Loop))
    Однако Visual Prolog при этом вернет ошибку, связанную с тем, что цель оператора NOT содержит анонимную переменную:

    Free variable are not allowed in ‘not’ or ‘retractall’

    Для решения проблемы достаточно написать вспомогательную функцию, выполняющую поиск любого цикла или петли в графе:

    loop_graph(Graph):-
      loop_graph(_X, Graph, [], _Loop), !.

    Вызов такой функции не содержит анонимных переменных, поэтому может использоваться совместно с оператором NOT.

    На скриншоте показаны циклы, которые программа найдет для заданного Вами графа.

Для ответа в этой теме необходимо авторизоваться.