我正在尝试在ocaml中编写拓扑排序,但我是初学者(在OCaml和图算法中),我不能自己做.
我更容易考虑拓扑排序,例如C++(并且在互联网上有很多关于C++拓扑排序的例子),但我想学习一些新东西.此外,我已经找到了一些用OCaml编写的拓扑排序的例子,坦率地说,我不明白它们.
假设我有一个列表(int * int list) list,例如:
myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;
这意味着,我需要"做"任务1任务之前2,任务4任务之前3和1等
我想,这个列表的输出应该是:
[8; 5; 6; 7; 4; 3; 1; 2]
(但我不确定,因为我刚刚做了这个例子,所以如果我错了,请纠正我)
另外,我已经读过,拓扑排序对于图中的循环不起作用,因此循环必须有某种条件 - 当给定图形有循环时,我们引发异常(我认为这是一个好主意) .
AFAIK,我需要在算法中使用DFS进行拓扑排序,其中(DFS)我不知道如何在OCaml中实现(我理解主要思想,但我不觉得,这在OCaml /函数编程中是如何工作的).
我非常感谢你帮助我理解这个概念(我的意思是拓扑排序,OCaml /函数编程中的DFS).如果可以的话,如果您向我展示示例代码,那将会很棒,因为阅读代码(对我来说)是理解算法概念的最佳方法.
我知道,对于大多数人来说,这是一个简单的问题,但我希望,它不会阻止你帮助我.
PS:我自己学习OCaml(我在高中),所以我没有扎实的理论背景(在OCaml或算法中).我开始学习OCaml,因为我想理解递归概念,现在这种语言看起来很有趣,因为它与C++真的不同,所以我还在尝试学习OCaml中的新东西.