序言，找到一個圖的鄰居

Question

給定圖

G = [1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9] 

我必須找到每一個節點的所有鄰居，並創建一個列表這種形式

Graph = [(1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3, 7, 8, 9]), (7, [4, 5, 6]), (8, [6]), (9, [3, 6])]. 

這裏是我的方法：

search_for_neighbors(Ne,V,Ne,V). 
search_for_neighbors(V,V,Ne,Ne). 
search_for_neighbors(_,_,_,0). 

neigh(_,[],_). 
neigh(N,[(V - Ne)|T],Graph) :- 
    neigh(N,T,Graph1), 
    search_for_neighbors(N,V,Ne,Result), 
    add_first(Result,Graph1,Graph). 

allneigh(0,_,_). 
allneigh(N,G,L) :- 
    N1 is N - 1, 
    allneigh(N1,G,L1), 
    neigh(N,G,L2), 
    add_last((N,L2),L1,L). 

add_first(0, L, L). 
add_first(X, L, [X|L]). 

add_last(X, [], [X]). 
add_last(X, [Y|L1], [Y|L2]):- add_last(X,L1,L2). 

我運行我的Prolog代碼：

?- allneigh(9,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],G). 

這是我的結果，

G = [(1, [5|_464]), (2, [4, 6|_508]), (3, [4, 6, 9|_556]), (4, [2, 3, 7|_606]), (5, [1, 7|_658]), (6, [2, 3, 7, 8, 9|_712]), (7, [4, 5, 6|_769]), (8, [6|_827]), (9, [3, 6|_883])] 

爲什麼我有這樣的行爲？

Answer 1

簡短的回答：因爲在neigh/3第一行第二個下劃線（_）的：

neigh(_,[],_). 
%  ^culprint 

既然你對那部分做遞歸，生成所有名單開放式：

：

?- neigh(N,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],L). 
N = 9, 
L = [3, 6|_G4581] ; 
N = 9, 
L = [0, 3, 6|_G4581] ; 
N = 9, 
L = [0, 3, 6|_G4581] ; 
N = 9, 
L = [0, 0, 3, 6|_G4581] ; 

您可以通過使用一個空的列表，如進行快速修復

neigh(_,[],[]). 

但也有更多的問題：

• add_first/3回溯即使添加0，因爲add_first/3第二行則不排除是X0。
• 反正你爲什麼生成0？

總的來說，我想說的代碼是沒有太多的「聲明」，並使用了大量的約定（如使用0）篩選出角球案件和邊緣情況。你也使用add_last/3等，這通常是你想避免的，因爲它效率很低。

使用解決方案內建

讓我們首先定義一個輔助函數range(N,L).，對於給定N，生成列表L=[1,2,...,N]：

range(N,L) :- 
    range(1,N,L). 

range(I,N,[]) :- 
    I > N. 
range(I,N,[I|L]) :- 
    I =< N, 
    I1 is I+1, 
    range(I1,N,L). 

現在我們可以使用一個複雜的一個班輪建設這樣的圖表：

allneigh(N,G,L) :- 
    range(N,Vs), 
    findall((X,Ys), 
     setof(Y,(member(X,Vs),(member(X-Y,G);member(Y-X,G))),Ys), 
    L). 

哪給出：

?- allneigh(9,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],G). 
G = [ (1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3|...]), (7, [4|...]), (8, [...]), (..., ...)] [write] 
G = [ (1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3, 7, 8, 9]), (7, [4, 5, 6]), (8, [6]), (9, [3, 6])] ; 

（第二行只是輸出寫滿）。

Answer 2

另一種方法是使用與foldl：

:- use_module(library(lambda)). 

all_neighbors(G, N) :- 
    foldl(\X^Y^Z^(X = A - B, 
       ( select((A,V), Y, Y1) 
       -> append(V, [B], V1), 
         sort([(A,V1) | Y1], Y2) 
       ; sort([(A,[B])| Y], Y2)), 
       ( select((B,W), Y2, Y3) 
       -> append(W, [A], V2), 
        sort([(B,V2)|Y3], Z) 
       ; sort([(B,[A]) | Y2], Z))), 
      G, [], N). 

結果

?- all_neighbors([1-5,2-4,2-6,3-4,3-6,3-9,4-7,5-7,6-7,6-8,6-9], N). 
N = [(1,[5]),(2,[4,6]),(3,[4,6,9]),(4,[2,3,7]),(5,[1,7]),(6,[2,3,7,8,9]),(7,[4,5,6]),(8,[6]),(9,[3,6])].