algorithm - 新泽西州 SML 中的图表

Question

我需要使用 ML 编写一些函数，该函数接收有向图[(1,2),(1,3),(3,2)]的边列表，这意味着从 1 到 2 的有向边和从 1 到 3 ...，并且我还收到两个顶点，我需要找到从第一个顶点到第二个顶点的所有可能方式以及可能路径的列表，例如对于顶点1、2，我需要显示列表 [[ 1,2],[1,3,2]]，如果无法存储有关顶点的数据，我该怎么做 ML，提前感谢您的任何想法。

Answer 1

如果要存储有关顶点的数据，则需要从顶点到数据的有限映射。该地图可能会提供这样的签名：

type 'a vmap (* vertex map *)
val empty : 'a vmap  (* empty map *)
val insert : vertex * 'a * 'a vmap -> 'a vmap  (* add info about a vertex *)
val lookup : vertex * 'a vmap -> 'a option  (* look for info about a vertex *)

为了实现这个签名，你可以考虑一个简单的vertex * 'a对列表，或者更雄心勃勃的东西，比如平衡二叉搜索树。

Answer 2

您可以存储有关顶点的数据！

例如，你想记录你访问过哪些顶点吗？

假设您有一个函数，它递归地探索当前顶点中所有可能的未探索边。

它可以接受未探索边的向量，加上当前顶点和目标顶点。它将返回一个成功到达目标顶点的路径向量。

在内部，它将定位从该顶点开始的边集，并针对该集中的每条边递归到自身，从未探索边列表中删除所选边到每个子函数中。

Answer 3

对不起，我无法抗拒

我在Yahoo!上看到了同样的谜题（呃问题）弹出窗口！答案，我回答了。

该实现最初是基于创建树来遍历图的设计。但它最终与Alex Brown之前表达的设计相匹配。

最初计划是在 Haskell 中完成的，因此这个辅助函数：

fun replicate len el = 
    if len = 0 then nil else el::replicate (len -1) el

主要实现：

fun routes  dst (edges:(int * int) list) src  = 
    let val (very_possible,remotely_possible) =
            if null edges
            then (nil,nil)
            else List.partition ((fn s=> s = src) o #1) edges 
        val (raw_solutions,dsts_is_nx_srcs) = 
            List.partition  ((fn d => d = dst) o #2) very_possible
        val solutions = replicate  (length raw_solutions) [src,dst]
        val full_rest_routes =
            let val rest_rest_routes = 
                    map (routes dst remotely_possible)  
                            ( map #2 dsts_is_nx_srcs )
              in map (fn lst => src::lst) (List.concat rest_rest_routes)
     end
     in case (very_possible, solutions, remotely_possible)
        of (nil, _,  _)       => nil
         |  (_::_, (p::ps), _) =>  solutions @ full_rest_routes
         |  (_::_, nil, _::_)  =>  full_rest_routes
  |  (_   , nil, nil )  => nil
     end

用户界面：

fun getPaths edges src dst  =  routes dst edges src 

上面的代码来自routes4.sml；但是省略了测试和IO。即使这不是太长，我仍然希望它可以更简单。