Editing Depth-First Search (section)

== 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 ===

<pre>
#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;
}

</pre>

=== Example USACO Silver Problems ===

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

    [[USACO_2016_December_Silver_P2|2016 December Silver Problem 2: Cities and States]]
    [[USACO_2017_December_Silver_P1|2017 December Silver Problem 1: The Bovine Shuffle]]
    [[USACO_2019_January_Silver_P3|2019 January Silver Problem 3: Sleepy Cow Sorting]]

=== Example USACO Gold Problems ===

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

    [[USACO_2015_December_Gold_P2|2015 December Gold Problem 2: Fruit Feast]]
    [[USACO_2018_February_Gold_P2|2018 February Gold Problem 2: Rental Service]]
    [[USACO_2020_January_Gold_P3|2020 January Gold Problem 3: Wormhole Sort]]


[[Category:Depth-First Search]]
[[Category:Algorithms]]
[[Category:Graph]]