Depth First Поиск списка смежности в F # - PullRequest
Новая
       46

Depth First Поиск списка смежности в F #

0 голосов
/ 08 июля 2019

У меня есть список, который структурирован следующим образом: 

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]]

Я хочу получить это же значение для синих цепочек, но без использования глобальной переменной

1 Ответ

1 голос
/ 09 июля 2019

Это то, что я наконец-то сделал благодаря @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
...