維護圖表算法中的數據結構完整性的功能方式

我試圖解決從UVA在線法官網站，特別是539問題，我需要使用DFS找到最長的路徑，我可以解決它的迫切需求，但我想用功能更強大的慣用方式來使用scala，問題是當算法從分支返回時，數據結構不會更新以供其他分支使用，不想使用瓦爾，又無副作用，我的繼承人代碼：維護圖表算法中的數據結構完整性的功能方式

type Vertex=Int 

type Graph = Map[Vertex,Set[Vertex]] 

def DFS(start: Vertex, g: Graph): Int = { 

    def loop(v: Vertex, visited: List[Vertex], size: Int = 0): Int = { 

    val neighbours: List[Vertex] = (g(v) filterNot visited.contains).toList 
    if (neighbours == Nil) size 
    else { 
    (for (elem <- neighbours) yield loop(elem, v :: visited, size + 1)).max } 
    } 
loop(start, List()) 
}

來源

2016-08-02 matos416

看起來你需要一起返回'visited'你'max'和使用'foldLeft'，而不是'for'穿過狀態下一'loop'和摺疊後返回它。 –

你想要foldLeft之類的東西傳遞修改後的'visited'嗎？編輯：嘿，@VictorMoroz，快照！ –

您需要存儲的路徑，而不是頂點被訪問的設置（除名單包含運行性能更好）。你也應該從所有的頂點開始嘗試。檢查：

type Vertex = Int 

type Graph = Map[Vertex, Set[Vertex]] 

def DFS(g: Graph): Int = { 

    def loop(current: Vertex, visited: Set[(Vertex, Vertex)]): Int = { 
    val neighbours = g(current).filterNot(contains(visited, current, _)) 
    if (neighbours.isEmpty) 
     visited.size 
    else { 
     (for { 
     elem <- g(current).filterNot(contains(visited, current, _)) 
     } yield (loop(elem, add(visited, current, elem)))).max 
    } 
    } 

    (for { 
    elem <- g.keys 
    } yield (loop(elem, Set()))).max 
} 

def add(set:Set[(Vertex,Vertex)], v1:Vertex, v2:Vertex): Set[(Vertex,Vertex)] = 
    if(v1 < v2) add(set, v2,v1) else set.+((v1,v2)) 
def contains(set:Set[(Vertex,Vertex)], v1:Vertex, v2:Vertex):Boolean = 
    if(v1 < v2) contains(set, v2,v1) else set.contains((v1,v2))

來源

2016-08-02 20:12:11 Mikel

維護圖表算法中的數據結構完整性的功能方式

回答

相關問題