Depth-First Search

Depth-First Search

Depth-First Search (DFS) is a graph traversal algorithm that explores all the vertices of a graph by visiting nodes as deep as possible before backtracking. DFS can be implemented using recursion or an explicit stack data structure.

Algorithm

   Start at the source node and mark it as visited.
   For each adjacent node of the source node, if it is not visited, perform a recursive DFS from the adjacent node.

Time Complexity

The time complexity of DFS is O(V + E), where V is the number of vertices in the graph, and E is the number of edges.

C++ Code Example

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> adjList;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << "Visiting node: " << node << endl;

    for (int adjacent : adjList[node]) {
        if (!visited[adjacent]) {
            dfs(adjacent);
        }
    }
}

int main() {
    // Initialize adjacency list and visited vector
    adjList = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
    visited.resize(4, false);

    // Perform DFS from the first node
    dfs(0);

    return 0;
}

Example USACO Silver Problems

Here are some example USACO Silver problems that utilize Depth-First Search:

   2016 December Silver Problem 2: Cities and States
   2017 December Silver Problem 1: The Bovine Shuffle
   2019 January Silver Problem 3: Sleepy Cow Sorting

Example USACO Gold Problems

Here are some example USACO Gold problems that utilize Depth-First Search:

   2015 December Gold Problem 2: Fruit Feast
   2018 February Gold Problem 2: Rental Service
   2020 January Gold Problem 3: Wormhole Sort