在无向图中寻找环

Question

需要实现一个swi-prolog程序，实现对无向图中所有圈的搜索，并无重复输出结果。 例子： ?-find_cycles([a-[b,c,d],b-[a,c],c-[a,b,d],d-[a,c]]) 结果： 循环 = [a,b,c] 循环 = [a,d,c]

我尝试实现dfs算法但是没有成功

Answer 1

我认为这就是你想要的，或者至少这是一个起点：

find_cycle(Conns, Cycle) :-
    member(Start-_, Conns),
    find_cycle_(Cycle, Conns, Start, Start, [Start]).
    
find_cycle_([Pos|Cycle0], Conns, Start, Pos, Seen) :-
    can_move(Conns, Pos, Pos1),
    (   Pos1 == Start
    % Found end of a cycle
    ->  Cycle0 = []
    % Avoid revisiting a position
    ;   \+ memberchk(Pos1, Seen),
        find_cycle_(Cycle0, Conns, Start, Pos1, [Pos1|Seen])
    ).

can_move(Conns, Pos, Pos1) :-
    member(Pos-L, Conns),
    member(Pos1, L).

swi-prolog 中的结果：

?- find_cycle([a-[b,c,d],b-[a,c],c-[a,b,d],d-[a,c]], C).
C = [a, b] ;
C = [a, b, c] ;
C = [a, b, c, d] ;
C = [a, c] ;
C = [a, c, b] ;
C = [a, c, d] ;
C = [a, d] ;
C = [a, d, c] ;
C = [a, d, c, b] ;
C = [b, a] ;
C = [b, a, c] ;
C = [b, a, d, c] ;
C = [b, c, a] ;
C = [b, c] ;
C = [b, c, d, a] ;
C = [c, a, b] ;
C = [c, a] ;
C = [c, a, d] ;
C = [c, b, a] ;
C = [c, b, a, d] ;
C = [c, b] ;
C = [c, d, a, b] ;
C = [c, d, a] ;
C = [c, d] ;
C = [d, a, b, c] ;
C = [d, a, c] ;
C = [d, a] ;
C = [d, c, a] ;
C = [d, c, b, a] ;
C = [d, c] ;
false.