我需要用标准 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 是需要的。
有没有人有办法解决吗?