Haskell深度优先搜索图形-Java 学习之路

几个小时，我正在尝试实现Haskell的深度优先搜索 . 我的depthfirst算法给出了一个起始节点和一个图 . 这就是我到目前为止图形数据类型的定义 .

data Graph a = G [a] (BRfun a)

有：

type BRfun a = a -> [a]

目前的尝试：

depthFirst :: Eq a => a -> Graph a -> [a]
depthFirst a (G [a] sucs) = [a]

因此，如果节点列表中只有一个元素是我必须放在最终列表中的唯一元素（我认为应该是取消条件） . 但现在我正在努力创建一个递归算法来首先获得最深的节点 .

2 回答

0
对于像DFS和BFS这样的图形搜索，您需要保留先前访问过的顶点列表 . 这样就可以检查你之前是否看过一个顶点，这样你就不会访问一个顶点两次（这也会处理周期，虽然它实际上无法检测周期是否存在） .

这是我的实施 . visited 列表跟踪已访问的顶点 . 对于我们遇到的每个顶点，我们通过遍历列表来检查它是否被访问过 . 当我们"visit"一个顶点（即在 else 分支中）时，我们将顶点添加到列表中 . 访问列表通过在 foldl 中传递来保持最新 .

在这种方法中，我们实际上可以劫持 visited 列表以记录深度优先顺序 . 由于我们在第一次看到顶点时将顶点添加到列表中，因此 visited 列表按反向深度优先顺序排列 . 所以我们只需在搜索完成后撤消它 .
```
depthFirst source (G _ sucs) = reverse (search [] source)
  where
    search visited v =
      if v `elem` visited
      then visited -- already seen v, so skip it
      else foldl search (v:visited) (sucs v)
```
我建议逐步了解代码在小图上的执行情况，以了解代码的工作原理以及代码的正确性 . 例如，从源0开始，按照以下定义的图表进行尝试 .
```
edges = [[1,2,3],[4],[5],[4,6],[5],[1],[4]]
g = G [0,1,2,3,4,5,6] (edges!!)
```
最后，请注意，此实现是正确的但效率非常低，为n个顶点和m个边的图形花费时间O（nm），因为我们遍历每个边缘的访问列表一次 . 在一个更有效的实现中，您可能希望保留两个数据结构，一个用于查找是否已访问过顶点（例如哈希集或二进制搜索树），另一个用于查找深度优先排序 .
回复于 2024-04-27T18:14:17+08:00
0
我喝了太多酒，对我正在谈论的内容有点模糊，但这是我提出的解决方案 .
```
depthFirst :: Eq a => a -> Graph a -> [a]
depthFirst root (G _nodes edges)
  = reverse $ go [] root
  where
    go seen x
      | x `elem` seen = seen
      | otherwise = foldl' go (x:seen) (edges x)
```
我在 Data.List 使用了 foldl' 因为我们想要从左到右遍历节点，这对于 foldr 来说有些挑战 . 直接使用没有 ' 的 foldl 通常不是一个好主意，因为除非强迫（强制正好是 foldl' ），它会构建thunks .

因此，正如我在评论中所概述的那样，总体思路如下 . 在第一次机会下到树下，保持你沿途看到的节点列表 . 如果一个节点没有传出边缘，很酷，你就完成了 . 如果你已经看过一个给定的节点，保释，你就不需要无限递归了 .

折叠从当前节点开始，前面是已经看过的节点列表（在开头，空列表） . 然后，从左到右，它访问从当前节点直接可到达的每个节点 . 在每个“下一个”节点，它构建子树的反向深度优先顺序加上已经看过的节点 . 已经看到的节点被转移到每个“下一个”节点（从左到右的顺序） . 如果没有可从当前节点到达的节点，则它仅返回所有看到的节点列表前面的当前节点 .

看到的节点列表被反转，因为前置是 O(1) ，而追加是 O(n) . 更容易逆转一次并且变得复杂 O(n) 而不是每次追加并且大致复杂 O(n²) （复杂性来自我的头脑，而且我有点醉了，所以应用盐自由）

如果 elem x seen ，函数会返回到目前为止看到的所有节点的列表 . 它确保我们已经访问过了，因此避免了循环图上的无限递归 .

这是经典的深度优先搜索 . 它可以被优化，并且优化的可能性相当明显（对于一个， elem x seen 具有最坏情况的复杂性，而它可能是 O(log n) . 可以随意改进代码 .

作为最后一点建议， Graph 的类型不保证节点是唯一的 . 更严格的实现看起来像这样： data Graph a = G (Set a) (BRfun a) ，其中 Set 来自 Data.Set （或类似的东西） . 鉴于列表中所述的定义，重新标记所有节点，f.ex . 可能是个好主意 . nodes' = zip [1..] nodes 或类似的东西 .
回复于 2024-04-27T18:14:17+08:00

Haskell深度优先搜索图形

2 回答

相关问题