F#实现广度优先搜索

广度优先的算法原理已经到处都是，只是由于F#在国内资料甚少，本人贴出自己写好的一个广度优先算法F#实现

open System.Collections.Generic

//邻接矩阵
let adjList = [[1; 2; 3]; [2; 4];  [0; 4]; [0; 4];  [1; 2; 3; 5; 6; 7]; [4; 8]; [4; 8]; [4; 8]; [0; 6; 7] ]
//Meaning node0 is adjacent to node1, node2, node3 node1 is adjacent to node0, node4 and so on.

let addToPaths (paths : Dictionary<System.Guid, int list>) (newNode : int) (preNodes : int list) = 
    if paths.Count > 0
        then
        let keys = paths.Keys |> Seq.toList
        if (paths.Item(keys.[0]).Length = (preNodes.Length))
            then
            false
        else
            true        
    else
        true

let BFS (adjList : int list list)  (s : int) (t : int) = 
    let mutable flag = true
    let paths = Dictionary<System.Guid, int list>()
    let historyParents = 
        [System.Guid.NewGuid(), [s]]
        |> dict
        |> Dictionary<System.Guid, int list>
    let rec traverse (historyParent : Dictionary<System.Guid, int list>) = 
        if historyParent.Count > 0
            then
            let newHistoryParent = Dictionary<System.Guid, int list>()
            historyParent
            |> Seq.iter (fun kv -> 
                match kv.Value with
                | endNode :: pre ->                    
                    let neighbors = 
                        adjList.[endNode]
                        |> List.filter (fun node -> not (List.contains (node) (kv.Value)))
                    for newNode in neighbors do
                        if newNode = t
                            then  
                            if (addToPaths paths newNode kv.Value)
                                then
                                paths.Add(System.Guid.NewGuid(), newNode :: kv.Value)
                            else
                                flag <- false
                                
                        else
                            if  flag 
                                then
                                newHistoryParent.Add(System.Guid.NewGuid(), newNode :: kv.Value)
                            else
                                newHistoryParent.Clear()
                                
                | [] ->
                    ()
                )
            traverse newHistoryParent
        else    
            ()        
    traverse historyParents
    paths
    |> Seq.map (fun kv ->
        let pReverse = []
        let rec reverse p pReverse = 
            match p with
            | head :: tail ->
                let newP = head :: pReverse
                reverse tail newP
            | [] ->
                pReverse
        reverse kv.Value pReverse       
        )

        
///调用算法求0到8的所有最短路径
let a = BFS adjList 0 8  |> List.ofSeq