Functional DFS in Scala

Depth First Search(DFS) is an Algorithm for traversing graphs. DFS explores each node as far as possible before it backtracks. It explores edges in a Depth First manner. Here is an imperative version of dfs in c++

void dfs(vector<vector<int> >&adj, int src, vector<bool> &vis, vector<int> &res) {
    vis[src] = 1;
    res.push_back(src);
    for (int a : adj[src]) {
        if (!vis[a]) {
            dfs(adj, a, vis);
        }
    }
}

For a graph : [[1,4],[2,3,4],[4],[3],[0]], we will have 0 1 2 4 3 in res after call to dfs. The above algorithm is quite trivial. Lets look at the functional version of same algorithm in Scala.

def dfs(adj:List[List[Int]], src:Int, vis:List[Int]): List[Int] = {
    if(vis.contains(src)) vis
    else{
        adj(src)
            .foldLeft(src :: vis)((b, a) => dfs(adj, a, b))
    }
}
println(dfs(List(List(1, 4), List(2, 3, 4), List(4), List(3), List(0)),0,List()).reverse)

if(vis.contains(src)) vis

this line checks if the node src is already visited. If it is visited it simply return the list of visited nodes.

adj(src)
    .foldLeft(src :: vis)((b, a) => dfs(adj, a, b))

Otherwise we traverse on all the neighbors of src using foldLeft. In foldLeft we apply the binary operation (b, a) => dfs(adj, a, b). With initial value src :: vis here we add src node to the list of visited nodes using cons (::) operator. After the last recursive call we will have our result List(0, 1, 2, 4, 3).