[[
✎ pl:prolog:pllib:graph_path_2
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Graph path 2 ====== {{tag>graphs}} ===== Description ===== Testing connectivity breadth-first in a graph **Source**: The Art of Prolog ===== Download ===== Program source code: {{graph_path_2.pl}} ===== Listing ===== <code prolog> /* connected(X,Y) :- Node X is connected to node Y in the graph defined by edge/2 facts. */ :- op(40,xfx,\). connected(X,Y) :- enqueue(X,Q\Q,Q1), connected_bfs(Q1,Y,[X]). connected_bfs(Q,Y,Visited) :- empty(Q), !, fail. connected_bfs(Q,Y,Visited) :- dequeue(X,Q,Q1), X=Y. connected_bfs(Q,Y,Visited) :- dequeue(X,Q,Q1), findall(N,edge(X,N),Edges), filter(Edges,Visited,Visited1,Q1,Q2), connected_bfs(Q2,Y,Visited1). filter([N|Ns],Visited,Visited1,Q,Q1) :- member(N,Visited), !, filter(Ns,Visited,Visited1,Q,Q1). filter([N|Ns],Visited,Visited1,Q,Q2) :- not member(N,Visited), !, enqueue(N,Q,Q1), filter(Ns,[N|Visited],Visited1,Q1,Q2). filter([],Visited,Visited,Q,Q). enqueue(X,Qh\[X|Qt],Qh\Qt). dequeue(X,[X|Qh]\Qt,Qh\Qt). empty([]\[]). % Data edge(a,b). edge(a,c). edge(a,d). edge(a,e). edge(d,j). edge(c,f). edge(c,g). edge(f,h). edge(e,k). edge(f,i). edge(x,y). edge(y,z). edge(z,x). edge(y,u). edge(z,v). % Program 16.5: Testing connectivity breadth-first in a graph </code> ===== Comments =====
pl/prolog/pllib/graph_path_2.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry