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