Depth-first search

Follow one path as far as it goes, then back up and try the next branch.

Time O(V + E)Space O(V)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Recursion keeps a stack of where you came from. When a node has no unseen neighbours the call returns, which is the backtracking step.

Code

C++PythonC#

void dfs(unordered_map<char, vector<char>>& graph, char u, unordered_set<char>& seen) {
    seen.insert(u);
    for (char v : graph[u])
        if (!seen.count(v))
            dfs(graph, v, seen);
}

def dfs(graph: dict[str, list[str]], u: str, seen: set[str]) -> None:
    seen.add(u)
    for v in graph[u]:
        if v not in seen:
            dfs(graph, v, seen)
    # back to the caller

public static void Dfs(Dictionary<char, List<char>> graph, char u, HashSet<char> seen) {
    seen.Add(u);
    foreach (char v in graph[u])
        if (!seen.Contains(v))
            Dfs(graph, v, seen);
}

Tips

Swap the recursion for an explicit Stack<T> if the graph is deep enough to overflow the call stack.
Use it for connected components, cycle detection, topological sort, and counting islands.

In the .NET library

Dictionary<char, List<char>> is the usual adjacency list in C#. For nodes numbered 0..n-1, a List<int>[] is faster.