Advertisement
Guest User

Untitled

a guest
Nov 5th, 2018
1,570
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.91 KB | None | 0 0
  1. def pathFromDFSNonrec(source: V, targetPred: V => Boolean): Option[Seq[V]] = {
  2. // When visiting a vertex, mark it here so that it does
  3. // not get visited again
  4. val visited = scala.collection.mutable.HashSet[V]()
  5. // The path is constructed here
  6. var path: List[V] = Nil
  7. val stack = scala.collection.mutable.Stack[V]()
  8. stack.push(source)
  9. visited(source) = true
  10. path = source :: path
  11. while (stack.nonEmpty) {
  12. println(stack)
  13. var current = stack.pop
  14. if (!visited(current)) {
  15. visited(current) = true
  16. path = current :: path
  17. }
  18. val neighbourIterator = neighbours(current).toVector.reverseIterator
  19. while (neighbourIterator.hasNext) {
  20. val next = neighbourIterator.next()
  21. if (!visited(next)) {
  22. stack.push(next)
  23. }
  24. }
  25. }
  26. println("path on: " + path)
  27. Some(path.reverse)
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement