-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 回答