recursion - 在 F# 中深度优先搜索邻接列表
问题描述
我有一个结构如下的列表:
0 ; (0,0,G) ; []
1 ; (9,0,B) ; []
2 ; (9,9,R) ; []
3 ; (-1,-1,E) ; []
4 ; (-1,-1,E) ; []
5 ; (-1,-1,E) ; []
6 ; (-1,-1,E) ; []
7 ; (-1,-1,E) ; []
8 ; (-1,-1,E) ; []
列表中的每个项目都有一个索引、一个元组和一个包含邻居索引的附近邻居列表。
我的搜索从索引 1 或索引 2 开始,我需要从它们到索引 0 的所有路径。此外,我还需要一个包含路径上所有索引的列表。
我使用递归来实现这一点,并使用全局可变变量(blueChains)来存储所有可能的路径。我想在不使用全局变量的情况下做同样的事情,但相反,我希望函数返回所有路径的列表,因为它在我的代码的其他部分引起了问题。
这就是我的函数的外观:
let rec traverseBlue index visited =
match index with
| 0 ->
let newVisited = 0 :: visited
blueChains <- newVisited :: blueChains
printfn "Golden Cog Reached! Blue wins the game!"
currentGameStatus <- WonByB
| ind ->
if not (List.contains ind visited) then
let newVisited = ind :: visited
blueChains <- newVisited :: blueChains
printfn "INDEX: %i VISITED: %A" ind newVisited
for i in tree.[ind].connectedNodes do
traverseBlue i newVisited
我得到的输出是:
INDEX: 1 VISITED: [1]
INDEX: 3 VISITED: [3; 1]
BLUE CHAINS : [[1]; [1; 3]]
我想为蓝色链获得相同的值,但不使用全局变量
解决方案
这就是我最终所做的,感谢@glennsl 解决了我的问题。
let rec traverseBlue index visited oldBlueChains =
let mutable blueChains = []
match index with
| 0 ->
let newVisited = 0 :: visited
blueChains <- newVisited :: oldBlueChains
printfn "Golden Cog Reached! Blue wins the game!"
currentGameStatus <- WonByB
blueChains
| ind ->
if not (List.contains ind visited) then
let newVisited = ind :: visited
blueChains <- newVisited :: oldBlueChains
printfn "INDEX: %i VISITED: %A" ind newVisited
for i in tree.[ind].connectedNodes do
blueChains <- (traverseBlue i newVisited blueChains) @ blueChains
推荐阅读
- react-native - TypeError: undefined is not an object (evalating 'config.glyphs.forEach') using icomoon in react native
- python - `TypeError:'module' object is not callable` 当我使用 line profiler 执行性能统计时发生
- apache-spark - Spark-Sql无法访问阿里云(阿里云)OSS上的Hive表
- php - 在 Symfony 中注入“容器”
- javascript - 在Javascript中将UTC时间转换为本地时间,给出未来日期
- python-3.x - RegexpParser 在 JupyterLab 中使 Python 3.8.6 内核崩溃
- javascript - javascript中是否有删除以“<”开头并以“>”结尾的单词的功能?
- bash - 如何在终端上将所有目录中的文件重命名为相同的名称
- mysql - 从包含组的多个表中选择并加入
- ios - 我们可以通过 IOS API 在后台扫描 Ibeacons,只提供 Major 和 Minot 编号作为参数吗?