Fehler bei der Aufrechterhaltung der Integrität der Datenstruktur in einem Graphenalgorithmus in einer funktionalen Art und Weise

Question

Ich versuche, ein Problem von der UVA Online-Richter Website zu lösen, insbesondere 539, wo ich ein DFS verwenden müssen, um den längsten Pfad zu finden, d kann es dringend lösen, aber ich möchte es auf eine funktionale idiomatische Art und Weise mit Hilfe von Scala tun, das Problem ist, dass, wenn der Algorithmus von einem Zweig zurückkehren die Datenstruktur nicht für die Verwendung in anderen Branchen aktualisiert wird, nicht verwenden möchten vars, noch Nebenwirkungen, herer mein Code:

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()) 
} 

Answer 1

Sie müssen die Pfade speichern, nicht die Vertex in dem besuchten Set (bessere Leistung als Liste in Betrieb enthält). Auch sollten Sie dies in allen Vertex starten. Prüfen Sie dies:

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