Обход графа в Scala

Question

Реализации обхода графа (DFS и BFS), которых я знаю, используют набор mutable"посещенных" вершин.Как бы вы реализовали их только с неизменными структурами данных?

Я видел этот вопрос .Теперь интересно, есть ли и другие решения

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.

Answer 2

Следующий код выполняет несколько обходов ориентированных графов.Он использует только неизменяемые структуры данных и является хвостовой рекурсивной, но с некоторыми затратами:

List toVisit может содержать много дубликатов, поскольку содержит все вершины, которые мы планируем посетить в будущем.В худшем случае мы можем добавить вершину в список почти для каждого ребра графа.Следовательно, пространственная сложность хвостовой рекурсии равна O (| E | + | V |).

Для плотных графов стандартное не хвостовое рекурсивное решение, пространственная сложность которого равна O (| V |) более эффективен, хотя он требует сохранения стека вызовов длины O (| V |).

Поскольку для хранения самого входного графа требуется пространство O (| V | + | E |), вышеуказанная стоимость может быть приемлемой.Возможный способ улучшить пространственную сложность описанного выше - заменить toVisit на List [Iterator [Vertex]].Поскольку итераторы вычисляются лениво, это уменьшит сложность пространства до O (| V |).

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

Answer 3

вы можете пройти как ниже -

object FindPathsFromANode extends App {

      val startNode = "a"
      val inputNodes = List(Node("a", "x"), Node("a", "b"), Node("b", "c"), Node("c", "d"), Node("b", "y"), Node("b", "z"), Node("d", "a"))

      def findPaths(allNodes: List[Node], newNode: Node, path: List[Node] = Nil, isVisited: List[String] = Nil, allPaths: List[List[Node]] = Nil): List[List[Node]] = {
        if (isVisited.contains(newNode.dest)) {
          allPaths ++ List(path)
        } else {
          val nextNodes = allNodes.filter(_.source == newNode.dest)
          if (nextNodes.isEmpty) {
            allPaths ++ List(path :+ newNode)
          } else if (nextNodes.size > 1) {
            nextNodes.flatMap { node =>
              findPaths(allNodes, node, path :+ newNode, isVisited :+ newNode.source)
            }
          } else {
            findPaths(allNodes, nextNodes.head, path :+ newNode, isVisited :+ newNode.source)
          }
        }
      }

      val startNodes = inputNodes.filter(_.source == startNode)
      startNodes.flatMap(node => findPaths(inputNodes, node)).foreach(println)

    }

Проверьте решение по адресу: https://github.com/svsachin13/GraphTraversal-scala

Answer 4

Предыдущее решение имеет несколько проблем:

Это неэффективно: (graph (next) - посещения - toVisit) .toSeq может быть линейным по размеру графика.

Неправильная версия DFS, поскольку она не посещает в соответствии с порядком DFS: например, если у вас есть следующий график:

Карта («A» -> Set («B»), "D"), "B" -> Set ("C", "D"), "C" -> Set (), "D" -> Set ("E"), "E" -> Set ())

Тогда, если вы запускаете DFS, начиная с A, официальные порядки посещения DFS:

A, B, C, D, EA, B, D, E, CA, D,E, B, C

Приведенный выше алгоритм может посещать вершины в следующем недопустимом порядке: A, D, B, C, E

Поскольку в первой итерации вы добавляете оба D и B для последовательности toVisit.