The simplest BFS and DFS templates for algorithms in Swift

Subscribe to my newsletter and never miss my upcoming articles

Hello everyone, Leo here.

Today we'll explore two very important concepts and crucial for problem solving involves search on graphs, trees, etc.

So let's go!

The problem

I need to traverse some data structure in breadth or in depth.

Long story short, the difference will be the structure you use to traverse. When using BFS we use a queue to store the next nodes to process. When using DFS the stack is the way to go for processing items.

So the code template looks like this:

Let's suppose this classic tree example.

struct SimpleTree {
    var value : Int
    var children : [SimpleTree]?
}

Just a struct with value and his children. And we can populate the tree with this info:

var simpleNode = SimpleTree(value: 2, children: [SimpleTree(value: 5, children: nil), SimpleTree(value: 6, children: nil)])
var simpleRoot = SimpleTree(value: 1, children: [simpleNode,
                                                 SimpleTree(value: 4, children: nil),
                                                 SimpleTree(value: 3, children: [SimpleTree(value: 12, children: nil)])])

Resulting in this structure:

Screen Shot 2020-10-09 at 11.12.34.png

This approach in this case will traverse one level at time. First we process the root node, second we process all the children of the root, third we process all the children of children of the root node and so goes on.

It's important to think BFS a wider search than an exhaustive search, like when you are searching the first thing to match some criteria. The code follows:

func resolveBFS(_ tree: SimpleTree) -> [Int] {

    var result = [Int]()
    var queueTree = [tree]

    while !queueTree.isEmpty {

        let current = queueTree.remove(at: 0) // FIFO - remove the first entry
        result.append(current.value) // process node
        if let children = current.children { // here you explore all the children, if was a binary tree you should just explore left and right node, for example.
            for tree in children {
                queueTree.append(tree)
            }
        }
    }

    return result
}

The implementation above use the print func as a "processor" of each node, but on your real implementation you should just do what you are searching for there.

The bfs use a queue as backing data structure but the curiously we can use the swift's array implementation as a queue ( remember the remove(at:) operation in swift is O(N), so be careful)

The result of the code above is:

Screen Shot 2020-10-12 at 14.31.11.png

You can see, we first visited the root, after that we visited the next level, and so on.

The DFS we can use the same template but instead using a queue(FIFO) we can use a stack(LIFO). The logic is every time we have to process next element, we always process the last one inserted, this way going deeper on the data structure.

func resolveDFS(_ tree: SimpleTree) -> [Int] {

    var stackResult = [Int]()
    var stackTree = [tree]

    while !stackTree.isEmpty {

        let current = stackTree.popLast() // remove the last one added, O(1)
        guard let currentUnwrap = current else {return stackResult}
        stackResult.append(currentUnwrap.value) // process node
        if let children = currentUnwrap.children {
            for tree in children {
                stackTree.append(tree)
            }
        }
    }

    return stackResult
}

And the result is:

Screen Shot 2020-10-12 at 14.34.13.png

You can observe that in DFS case we first process the 12 to after return to node 4. This demonstrates that the algorithm is going Deep First and only after it processed all the children of the children of there first child from the root, it would look to the second child and continue going deep until it has exhausted all the children possibilities.

It's amazing where you can get only with this two templates. You should try yourself!

Conclusion

If you want try the whole template, just copy paste the code in your playgrounds:

struct SimpleTree {
    var value : Int
    var children : [SimpleTree]?
}

var simpleNode = SimpleTree(value: 2, children: [SimpleTree(value: 5, children: nil), SimpleTree(value: 6, children: nil)])
var simpleRoot = SimpleTree(value: 1, children: [simpleNode,
                                                 SimpleTree(value: 4, children: nil),
                                                 SimpleTree(value: 3, children: [SimpleTree(value: 12, children: nil)])])

func resolveBFS(_ tree: SimpleTree) -> [Int] {

    var result = [Int]()
    var queueTree = [tree]

    while !queueTree.isEmpty {

        let current = queueTree.remove(at: 0) // FIFO - remove the first entry
        result.append(current.value) // process node
        if let children = current.children {
            for tree in children {
                queueTree.append(tree)
            }
        }
    }

    return result
}

print(resolveBFS(simpleRoot).debugDescription, "BFS")

func resolveDFS(_ tree: SimpleTree) -> [Int] {

    var stackResult = [Int]()
    var stackTree = [tree]

    while !stackTree.isEmpty {

        let current = stackTree.popLast() // remove the last one added, O(1)
        guard let currentUnwrap = current else {return stackResult}
        stackResult.append(currentUnwrap.value) // process node
        if let children = currentUnwrap.children {
            for tree in children {
                stackTree.append(tree)
            }
        }
    }

    return stackResult
}

print(resolveDFS(simpleRoot).debugDescription, "DFS")

That's it, I hope this was helpful to you and the challenge now is to make this algorithm recursive... Maybe next time!

Thanks for the reading and... That's all folks!

More resources: youtube.com/watch?v=TIbUeeksXcI

raywenderlich.com/661-swift-algorithm-club-..

Credits: image

No Comments Yet