Jump to content

Algorithm Implementation/Graphs/Depth-first search

From Wikibooks, open books for an open world

In C++:

/*
   Depth-first search
   running time is O(|E|+|V|)
   g - adjacency list
   used - bool array, to check if node is visited

vector<vector<int>> g;
vector<bool> used;

void dfs(int v) {
    used[v] = true;
    // ...
    for (int &to:g[v]) {
        //...
        if(!used[to])
            dfs(to);
    }
}