Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def pathFromDFSNonrec(source: V, targetPred: V => Boolean): Option[Seq[V]] = {
- // When visiting a vertex, mark it here so that it does
- // not get visited again
- val visited = scala.collection.mutable.HashSet[V]()
- // The path is constructed here
- var path: List[V] = Nil
- val stack = scala.collection.mutable.Stack[V]()
- stack.push(source)
- visited(source) = true
- path = source :: path
- while (stack.nonEmpty) {
- println(stack)
- var current = stack.pop
- if (!visited(current)) {
- visited(current) = true
- path = current :: path
- }
- val neighbourIterator = neighbours(current).toVector.reverseIterator
- while (neighbourIterator.hasNext) {
- val next = neighbourIterator.next()
- if (!visited(next)) {
- stack.push(next)
- }
- }
- }
- println("path on: " + path)
- Some(path.reverse)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement