图中的可达节点

Question

我想检查一个节点可以从哪些节点到达。

所以我想给出一个图和节点，return 一个我可以从中访问该图的所有节点的列表。（我知道有Data.Graph，但我想试着从头理解它，不要故意使用它。

为了构建图表，我得到了以下数据。

data Node = Node String [Node]

字符串只是节点名称的表示。

这是图形的表示。

node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]

我还（直接）到达了以下节点：

canReachNext (Node x y) = y

现在我的基本想法是这样的：

listForReachables:: Node n => n -> [n]
listForReachables x
    | contains[x] (canReachNext x) == False = listForReachables (head(canReachNext (x)))
    | contains [x] (canReachNext x)== True = [x]
    | otherwise = []

如果我运行

这将以无限循环结束

listForReachables node1

我明白了它以循环结束的原因。因为在这个例子中，头部总是有一个其他列表。

我的问题和我被卡住的地方是，我习惯了 OOP，在这种情况下，感觉我需要一个列表来记住我已经检查了哪些节点，以及我仍然需要检查哪些节点。

Answer 1

在Haskell中，一个具有所需类型的函数调用另一个具有许多参数的函数是很常见的。您可以使用这些来捕获中间状态。

在这种情况下，我添加了一个已经访问过的节点列表。第一个参数是要探索的节点列表。当程序遇到已经通过的节点时，将其丢弃并从第一个参数开始继续其他节点。

您的退出条件不会发生，因为 Bool 只有 True 和 False 值。这些就不用再比了。

我有一个问题，标准类 Show 和 Eq 在应用于 node1 时挂起，所以我做了一个不完整的 contains 和 name 为我自己。

如果您在骑行时遇到问题，请务必检查 show node1 和 contains 是否正常。或者，制作一个非循环测试图。

node6 = Node "node6" [node7]
node7 = Node "node7" []

代码：

data Node = Node String [Node]

node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]

canReachNext :: Node -> [Node]
canReachNext (Node x y) = y

name :: Node -> String
name (Node x y) = x

contains :: [Node] -> [Node] -> Bool
contains (x:xs) ys = any ((\(Node a b) -> \(Node c d) ->  a == c) x) ys

listForReachables :: Node -> [Node]
listForReachables x = listForReachables' (x:[]) []

listForReachables' :: [Node] -> [Node] -> [Node]
listForReachables' (x:xs) ys
    | contains [x] ys  = listForReachables' xs ys
    | otherwise = listForReachables' (xs ++ canReachNext x) (x:ys)
listForReachables' [] ys = ys

测试：

map name $ listForReachables node1

输出：

["node5","node4","node3","node2","node1"]

注1.: There is convention to name a helper function "go".

listForReachables :: Node -> [Node]
listForReachables x = go (x:[]) [] where
 go (x:xs) ys
    | contains [x] ys  = go xs ys
    | otherwise = go (xs ++ canReachNext x) (x:ys)
 go [] ys = ys

Answer 2

it feels like I need a list to remember which nodes I've checked, and which nodes I still have to check.

我同意。所以让我们使用一个！

listForReachables :: Node -> [String] -> ([String], [Node])
listForReachables node@(Node src tgts) visited
    | src `elem` visited = (visited, [])
    | otherwise = loopOver tgts (src:visited)
    where
    loopOver [] visited = (visited, [node])
    loopOver (tgt:tgts) visited = let
        (visited', reachables) = listForReachables tgt visited'
        (visited'', reachables') = loopOver tgts visited'
        in (visited'', reachables ++ reachables')

实际上，有经验的 Haskeller 会注意到这种模式：

(visited', reachables) = listForReachables tgt visited'
(visited'', reachables') = loopOver tgts visited'

并意识到这正是 State [String] monad 的 (>>=) 的实现。所以他们可能会这样改变实现：

listForReachables :: Node -> State [String] [Node]
listForReachables node@(Node src tgts) = do
    done <- gets (src `elem`)
    if done then pure [] else do
        modify (src:)
        reachables <- mapM listForReachables tgts
        pure (node : concat reachables)

非常紧凑！让我们试试吧：

> name (Node nm _) = nm
> map name (evalState (listForReachables node1) [])
["node1","node2","node3","node4","node5"]

图中的可达节点

Reachable nodes in a graph

haskell

graph