-2

我需要用标准 ML 编写 SCC 算法。但我不知道怎么做。
我有以下必须在代码中使用的类型:

type vertex = int
type edge = int * int
type graph = (vertex * vertex list) list


fun dfs (g: graph) (n: vertex): vertex list = 
  let
    fun helper (todo: vertex list) (visited: vertex list): vertex list =
    case todo of
      [] => []
    | h::t => if (List.exists (fn x => x = h) visited)
                then helper t visited
                else
                  let
                    val adj = case List.find (fn (n, _) => n = h) g of
                                NONE => raise Fail "incomplete adjacency list"
                              | SOME (_, adj) => adj
                  in
                    h :: (helper (adj @ t) (h::visited))
                  end
  in
    helper [n] []
  end

以上代码已编译并正确运行。
我把这些放在代码中是因为我知道在计算 SCC dfs 是需要的。
有没有人有办法解决吗?

4

2 回答 2

2

伪代码 - http://algowiki.net/wiki/index.php/Tarjan's_algorithm

于 2010-02-02T21:52:14.113 回答
-1

我猜您正在尝试使用标准 ML ( http://www.smlnj.org/sml.html )。

在你的课堂时间里,你的老师应该提供一个建模工具来创建你的 SML 代码,或者应该给你推荐一个资源来编写代码。她/他还应该提供示例代码 - 您的书(或书后的 CD)应该包含 SML 代码。

假设你没有建模工具,我的建议如下。首先参考您的老师或书籍提供的示例代码,然后选择解决与您的需求最相似的问题的代码。将其复制并粘贴到您的答案中,绝对确保在答案的开头清楚地引用来源。然后,使用课堂上的其他示例、书中的详细信息以及 smlnj.org 的“文档和文献”部分下的资源(尤其是教程)来实现您的解决方案。

然后,如果你有一个绊脚石——课堂上没有讨论过的事情,你的书没有提到,但你无法解决,你应该和你的助教或老师讨论。如果您向其中一个人提问,那么您的老师会发现课堂上没有明确涵盖该主题。如果你不问他们,那么他们就不会知道,而且你班上的大部分人可能对这个话题有困难。

最后,如果您的老师和助教不在,而您遇到了一个您不知道如何解决的问题,并且您有一个非常具体的问题(例如,“这是我的代码;它不会” t 编译,我不知道为什么”),这时你应该问 Stack Overflow。

于 2010-02-02T22:21:14.260 回答