4

特定のノード間のすべてのパスを返す関数を作成する必要があります。

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 = []

リスト内包表記を使用してそれを実行しようとしましたが、haskellがあまり得意ではなく、修復できない入力エラーが発生します。

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)]]
4

1 に答える 1

6

再帰的に考えてください。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)]
于 2012-06-23T09:26:47.873 に答える