Table of Contents
IntroductionApplication: Connected ComponentsApplication: Graph Two-ColoringDFSBFSPrerequisite - Queues & DequesQueuesDequesImplementationSolution - Building RoadsDFS SolutionAn Issue With Deep RecursionBFS SolutionConnected Component ProblemsSolution - Building TeamsDFS SolutionBFS SolutionGraph Two-Coloring ProblemsQuizGraph Traversal
Authors: Siyong Huang, Benjamin Qi, Ryan Chou
Contributors: Andrew Wang, Jason Chen, Divyanshu Upreti
Traversing a graph with depth first search and breadth first search.
Table of Contents
IntroductionApplication: Connected ComponentsApplication: Graph Two-ColoringDFSBFSPrerequisite - Queues & DequesQueuesDequesImplementationSolution - Building RoadsDFS SolutionAn Issue With Deep RecursionBFS SolutionConnected Component ProblemsSolution - Building TeamsDFS SolutionBFS SolutionGraph Two-Coloring ProblemsQuizIntroduction
Resources | ||||
---|---|---|---|---|
CPH |
Graph traversal algorithms visit all nodes within a graph in a certain order and can compute some information along the way. Two common algorithms for doing this are depth first search (DFS) and breadth first search (BFS).
Application: Connected Components
Focus Problem – try your best to solve this problem before continuing!
A connected component is a maximal set of connected nodes in an undirected graph. In other words, two nodes are in the same connected component if and only if they can reach each other via edges in the graph.
In the above focus problem, the goal is to add the minimum possible number of edges such that the entire graph forms a single connected component.
Application: Graph Two-Coloring
Focus Problem – try your best to solve this problem before continuing!
Graph two-coloring refers to assigning a boolean value to each node of the graph, dictated by the edge configuration. The most common example of a two-colored graph is a bipartite graph, in which each edge connects two nodes of opposite colors.
In the above focus problem, the goal is to assign each node (friend) of the graph to one of two colors (teams), subject to the constraint that edges (friendships) connect two nodes of opposite colors. In other words, we need to check whether the input is a bipartite graph and output a valid coloring if it is.
DFS
Resources | ||||
---|---|---|---|---|
CSA | up to but not including "More about DFS" | |||
CPH | example diagram + code |
From the second resource:
Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.
Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.
When implementing DFS, we often use a recursive function to visit the vertices and an array to store whether we've seen a vertex before.
#include <bits/stdc++.h>using namespace std;int n = 6;vector<vector<int>> adj(n);vector<bool> visited(n);void dfs(int current_node) {if (visited[current_node]) { return; }visited[current_node] = true;
BFS
Resources | ||||
---|---|---|---|---|
CSA | interactive, implementation | |||
PAPS | grid, 8-puzzle examples | |||
cp-algo | common applications | |||
KA | ||||
YouTube | If you prefer a video format |
In a breadth-first search, we travel through the vertices in order of their distance from the starting vertex.
Prerequisite - Queues & Deques
Resources | ||||
---|---|---|---|---|
CPH | ||||
PAPS |
Queues
A queue is a First In First Out (FIFO) data structure that supports three operations, all in time.
push
: inserts at the back of the queuepop
: deletes from the front of the queuefront
: retrieves the element at the front without removing it.
queue<int> q;q.push(1); // [1]q.push(3); // [3, 1]q.push(4); // [4, 3, 1]q.pop(); // [4, 3]cout << q.front() << endl; // 3
Deques
A deque (usually pronounced "deck") stands for double ended queue and is a combination of a stack and a queue, in that it supports insertions and deletions from both the front and the back of the deque. Not very common in Bronze / Silver.
The four methods for adding and removing are push_back
, pop_back
,
push_front
, and pop_front
.
deque<int> d;d.push_front(3); // [3]d.push_front(4); // [4, 3]d.push_back(7); // [4, 3, 7]d.pop_front(); // [3, 7]d.push_front(1); // [1, 3, 7]d.pop_back(); // [1, 3]
You can also access deques in constant time like an array in constant time with
the []
operator. For example, to access the th element of a
deque , do .
Implementation
When implementing BFS, we often use a queue to track the next vertex to visit. Like DFS, we'll also keep an array to store whether we've seen a vertex before.
#include <queue>#include <vector>using std::queue;using std::vector;int main() {int n = 6;vector<vector<int>> adj(n);vector<bool> visited(n);
Solution - Building Roads
Note that each edge decreases the number of connected components by either zero or one. So you must add at least edges, where is the number of connected components in the input graph.
To compute , iterate through each node. If it has not been visited, visit it and all other nodes in its connected component using DFS or BFS. Then equals the number of times we perform the visiting operation.
There are many valid ways to pick new roads to build. One way is to choose a single representative from each of the components and link them together in a line.
DFS Solution
#include <deque>#include <iostream>#include <vector>using namespace std;vector<vector<int>> adj;vector<bool> visited;void dfs(int node) {
An Issue With Deep Recursion
If you run the solution code locally on the line graph generated by the following Python code:
n = 100000print(n, n - 1)for i in range(1, n):print(i, i + 1)
then you might get a segmentation fault even though your code passes on the
online judge. This occurs because every recursive call contributes to the size
of the call stack, which
is limited to a few megabytes by default. To increase the stack size, refer to
this module.
Short answer: If you would normally compile your code with g++ sol.cpp
,
then compile it with g++ -Wl,-stack_size,0xF0000000 sol.cpp
instead.
BFS Solution
#include <deque>#include <iostream>#include <vector>using namespace std;int main() {int n;int m;cin >> n >> m;
Connected Component Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Silver | Easy | Show TagsConnected Components | |||
Silver | Easy | Show TagsBFS, Connected Components, DFS | |||
Silver | Easy | Show TagsConnected Components | |||
Kattis | Easy | Show TagsConnected Components | |||
ACSL | Easy | Show TagsDFS | |||
CSES | Normal | Show TagsDFS | |||
Gold | Normal | Show TagsBinary Search, Connected Components | |||
Silver | Normal | Show TagsBinary Search, Connected Components | |||
Silver | Normal | Show Tags2P, Binary Search, Connected Components | |||
Silver | Normal | Show TagsDFS | |||
CF | Normal | Show TagsConnected Components, DFS | |||
CF | Hard | Show TagsDFS, Sorted Set | |||
Kattis | Very Hard | Show TagsBinary Search, Connected Components | |||
Silver | Very Hard | Show TagsConstructive, Cycles, Spanning Tree |
Solution - Building Teams
Resources | ||||
---|---|---|---|---|
CPH | Brief solution sketch with diagrams. | |||
IUSACO | ||||
cp-algo | ||||
CP2 |
For each connected component, we can arbitrarily label a node and then run DFS or BFS. Every time we visit a new (unvisited) node, we set its color based on the edge rule. When we visit a previously visited node, check to see whether its color matches the edge rule.
DFS Solution
Optional: Adjacency List Without an Array of Vectors
See here.
#include <iostream>#include <vector>using namespace std;vector<int> assigned;vector<vector<int>> adj;/** @return true only if it's possible to assign each person to a team */bool dfs(int node) {
BFS Solution
The specifics of the algorithm are almost exactly the same; it's just that we do them in an iterative rather than recursive fashion.
#include <deque>#include <iostream>#include <vector>using namespace std;int main() {int n;int m;cin >> n >> m;
Graph Two-Coloring Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CF | Easy | Show TagsBipartite | |||
Silver | Easy | Show TagsBipartite | |||
CF | Easy | Show TagsBipartite | |||
Baltic OI | Hard | Show TagsDFS, Median | |||
CC | Hard | Show TagsBipartite, DFS | |||
APIO | Very Hard | Show TagsBipartite |
Quiz
What's the main difference between DFS and BFS?
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!