Haskell - 노드 간의 모든 경로를 생성합니다.

Question

특정 노드 사이의 모든 경로를 반환하는 함수를 작성해야합니다.

connect :: Int -> Int-> [[(Int,Int)]]

Data.Graph 라이브러리는 저 그래프를 생성 함수 'buildG을'내 유용한 준다. 내가

let g = buildG (1,5) [(1,2),(2,3),(3,4),(4,5),(2,5)]

,

를 호출하면 나는 모든 노드가 자신의 이웃에 매핑되는 배열을 얻을 것이다. 예 :

g!1 = [2] 
g!2 = [3,5] 
.. 
g!5 = [] 

내가 지능형리스트를 사용하여 일을하려고했지만, 나는 하스켈에서 아주 좋은 아니에요 그리고 내가 복구 할 수 점점 입력 오류입니다.

connect x y g 
    | x == y = [] 
    | otherwise = [(x,z) | z <- (g!x), connect z y g] 

주기에 대해서는 지금 걱정할 필요가 없습니다. 다음은 내가 원하는 것입니다.

connect 1 5 g = [[(1,2),(2,3),(3,4),(4,5)],[(1,2),(2,5)]] 

Answer 1

재귀 적으로 생각해보십시오. s에서 e까지의 경로는 첫 번째 가장자리 (s,t)과 t에서 e까지의 경로로 구성되며, 경로가 비어있는 경우 s == e이 아니면 경로가 비어 있어야합니다. 그래서 첫 번째 시도가

connect x y g 
    | x == y = [[]] 
    | otherwise = [(x,t):path | t <- g!x, path <- connect t y g] 

자체에 대한 노드에서 모든 대상 경로의 목록이 다른 경우에, 우리는 위의 논리에 의해 모든 대상 경로의 목록을 얻을, 하나의 요소 []와 목록입니다, 첫 번째 가장자리를 선택하고 그 끝에서 경로를 찾으십시오.

문제는주기 때문에 멈추는 문제입니다. 이를 방지하려면 이미 방문한 노드를 기억하고 경로를 탐색하지 않아야합니다.

connect x y g = helper x y g [x] 
    where 
    helper a b g visited 
     | a == b = [[]] 
     | otherwise = [(a,c):path | c <- g!a, c `notElem` visited, path <- helper c b g (c:visited)]