स्कैला

Question

ग्राफ़ ट्रैवर्सल (डीएफएस और बीएफएस) कार्यान्वयन में ग्राफ़ ट्रैवर्सल मुझे पता है कि "विज़िट" वर्टिस के परिवर्तनीय सेट का उपयोग करें। आप उन्हें केवल अपरिवर्तनीय डेटा संरचनाओं के साथ कैसे कार्यान्वित करेंगे?

मैंने this question देखा। अब मुझे आश्चर्य है कि अगर वहाँ भी कर रहे हैं अन्य समाधान

Answer 1

यहाँ एक तरह से यह करने के लिए है:

def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = { 
    if(toVisit.isEmpty) { 
    Seq.empty 
    } else { 
    val next = toVisit.head 
    val succ = (graph(next) -- visited -- toVisit).toSeq 
    // DFS : 
    // next +: traverse(graph, sucC++ toVisit.tail, visited + next) 
    // BFS : 
    next +: traverse(graph, toVisit.tail ++ succ, visited + next) 
    } 
} 

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) = 
    traverse(graph, Seq(initial), Set.empty) 

चाल नोड्स की सूची के आसपास पारित करने के लिए यात्रा करने के लिए (जो आपके ढेर या कतार के अनुरूप होगा बस है एक अनिवार्य एल्गोरिदम में), और दौरे वाले राज्यों का सेट।

@annotation.tailrec 
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = { 
    if(toVisit.isEmpty) { 
    accumulator 
    } else { 
    val next = toVisit.head 
    val succ = (graph(next) -- visited -- toVisit).toSeq 
    // DFS : 
    //traverseTR(graph, sucC++ toVisit.tail, visited + next, accumulator :+ next) 
    // BFS : 
    traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next) 
    } 
} 

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) = 
    traverseTR(graph, Seq(initial), Set.empty, Seq.empty) 

यह आपको कुशल के रूप में एक संस्करण दे देंगे जैसे कि आप ने लिखा है:

आप कॉल स्टैक प्रत्येक पुनरावर्ती कॉल के साथ बढ़ रहा बारे में चिंतित हैं, तो आप इसे पूंछ पुनरावर्ती एक अतिरिक्त तर्क का उपयोग करके बनाने के यह while लूप का उपयोग कर रहा है। .toSeq ग्राफ के आकार में रैखिक हो सकता है (tovisit - - दौरा ग्राफ (अगले)):

यह अक्षम है:

Answer 2

पिछले समाधान समस्याओं की एक जोड़ी है।

डीएफएस संस्करण, वह सही नहीं है, क्योंकि यह डीएफएस आदेश के अनुसार की यात्रा नहीं करता है: उदाहरण के लिए यदि आप निम्नलिखित ग्राफ है:

मानचित्र ('ए' -> सेट ('बी', 'डी ")," बी "-> सेट (" सी "," डी ")," सी "-> सेट()," डी "-> सेट (" ई ")," ई "-> सेट())

तो अगर आप डीएफएस एक पर शुरू चलाने के लिए, कानूनी डीएफएस जाकर आदेश हैं:

ए, बी, सी, डी, ई ए, बी, डी, ई, सी ए, डी, ई, बी , सी

उपरोक्त एल्गोरिथ्म निम्नलिखित अवैध क्रम में कोने की यात्रा हो सकती है: ए, डी, बी, सी, ई

पहले चरण में जब से तुम tovisit अनुक्रम को दोनों डी और बी जोड़ें।

Answer 3

निम्नलिखित कोड कुछ निर्देशित ग्राफ ट्रैवर्सल करता है। यह केवल अपरिवर्तनीय डेटा संरचनाओं का उपयोग करता है और पूंछ रिकर्सिव है, लेकिन कुछ लागत के साथ:

सूची में विविस में कई डुप्लिकेट हो सकते हैं, क्योंकि इसमें भविष्य में आने वाले सभी शिखर सम्मिलन शामिल हैं। सबसे बुरे मामले में हम ग्राफ में लगभग हर किनारे के लिए सूची में एक चरम जोड़ सकते हैं। इसलिए, पूंछ रिकर्सन की स्पेस जटिलता ओ (| ई | + | वी |) है।

घने ग्राफ के लिए, मानक गैर-पूंछ रिकर्सिव समाधान जिसका अंतरिक्ष जटिलता ओ (| वी |) अधिक कुशल है, भले ही इसे लंबाई ओ (| वी |) के कॉल स्टैक को बचाने की आवश्यकता हो।

इनपुट ग्राफ़ को संग्रहीत करने के बाद ही ओ (| वी | + | ई |) स्थान की आवश्यकता होती है, उपरोक्त लागत स्वीकार्य हो सकती है। उपर्युक्त की अंतरिक्ष जटिलता में सुधार करने का एक संभावित तरीका है सूची [Iterator [Vertex]] के साथ विजिट को प्रतिस्थापित करना।चूंकि इटरेटर्स का आलसी मूल्यांकन किया जाता है, इसलिए यह अंतरिक्ष जटिलता को ओ (| वी |) में कम कर देगा।

object DirectedGraphTraversals { 

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

    def dfs[Vertex](graph: Graph[Vertex], initialVertex: Vertex) = 
    dfsRec(DfsNeighbours)(graph, List(initialVertex), Set(), Set(), List()) 

    def topologicalSort[Vertex](graph: Graph[Vertex]) = 
    graphDfsRec(TopologicalSortNeighbours)(graph, graph.keySet, Set(), List()) 

    def stronglyConnectedComponents[Vertex](graph: Graph[Vertex]) = { 
    val exitOrder = graphDfsRec(DfsNeighbours)(graph, graph.keySet, Set(), List()) 
    val reversedGraph = reverse(graph) 

    exitOrder.foldLeft((Set[Vertex](), List(Set[Vertex]()))){ 
     case ((visitedAcc, connectedComponentsAcc), vertex) => 
     val connectedComponent = dfsRec(DfsNeighbours)(reversedGraph, List(vertex), visitedAcc, visitedAcc, List()).toSet 
     (visitedAcC++ connectedComponent, connectedComponent :: connectedComponentsAcc) 
    }._2.filterNot(_.isEmpty) 
    } 

    def reverse[Vertex](graph: Graph[Vertex]) = { 
    val reverseList = for { 
     (vertex, neighbours) <- graph.toList 
     neighbour <- neighbours 
    } yield (neighbour, vertex) 

    reverseList.groupBy(_._1).mapValues(_.map(_._2).toSet) 
    } 

    private sealed trait NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]):Set[Vertex] 
    } 

    private object DfsNeighbours extends NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = 
     graph.getOrElse(vertex, Set()).filterNot(entered) 
    } 

    private object TopologicalSortNeighbours extends NeighboursFunc { 
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = { 
     val neighbours = graph.getOrElse(vertex, Set()) 
     if(neighbours.exists(neighbour => entered(neighbour) && !exited(neighbour))) 
     throw new IllegalArgumentException("The graph is not a DAG, it contains cycles: " + graph) 
     else 
     neighbours.filterNot(entered) 
    } 
    } 

    @tailrec 
    private def dfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], toVisit: List[Vertex], 
                  entered: Set[Vertex], exited: Set[Vertex], 
                  exitStack: List[Vertex]): List[Vertex] = { 
    toVisit match { 
     case List() => exitStack 
     case hd :: tl => 
     if(exited(hd)) 
      dfsRec(neighboursFunc)(graph, tl, entered, exited, exitStack) 
     else if(entered(hd) && !exited(hd)) 
      dfsRec(neighboursFunc)(graph, tl, entered, exited + hd, hd :: exitStack) 
     else { // not entered yet 
      dfsRec(neighboursFunc)(graph, neighboursFunc(graph, hd, entered, exited) ++: toVisit, entered + hd, exited, exitStack) 
     } 
    } 
    } 

    @tailrec 
    private def graphDfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], notVisited: Set[Vertex], 
                    visited: Set[Vertex], order: List[Vertex]): List[Vertex] = { 
    if(notVisited.isEmpty) 
     order 
    else { 
     val orderSuffix = dfsRec(neighboursFunc)(graph, List(notVisited.head), visited, visited, List()) 
     graphDfsRec(neighboursFunc)(graph, notVisited -- orderSuffix, visited ++ orderSuffix, orderSuffix ::: order) 
    } 
    } 
} 

object DirectedGraphTraversalsExamples extends App { 
    import DirectedGraphTraversals._ 

    val graph = Map(
    "B" -> Set("D", "C"), 
    "A" -> Set("B", "D"), 
    "D" -> Set("E"), 
    "E" -> Set("C")) 

    //println(dfs(graph, "A")) 
    println("dfs A " + dfs(graph, "A")) 
    println("dfs B " + dfs(graph, "B")) 

    println("topologicalSort " + topologicalSort(graph)) 
    println("dfs B " + dfs(graph, "B")) 

    println("reverse " + reverse(graph)) 
    println("stronglyConnectedComponents graph " + stronglyConnectedComponents(graph)) 

    val graph2 = graph + ("C" -> Set("D")) 
    println("stronglyConnectedComponents graph2 " + stronglyConnectedComponents(graph2)) 
    println("topologicalSort graph2 " + Try(topologicalSort(graph2))) 
}