PrevNext
Very Frequent
 0/22

Graph 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.

Introduction

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

C++

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

Java

import java.io.*;
import java.util.*;
public class DFSDemo {
static List<Integer>[] adj;
static boolean[] visited;
static int n = 6;
public static void main(String[] args) throws IOException {
visited = new boolean[n];

Python

import sys
sys.setrecursionlimit(10**5) # Python has a default recursion limit of 1000
n = 6
visited = [False] * n
"""
Define adjacency list and read in problem-specific input here.

BFS

Resources
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

Queues

A queue is a First In First Out (FIFO) data structure that supports three operations, all in O(1)\mathcal{O}(1) time.

C++

std::queue

  • push: inserts at the back of the queue
  • pop: deletes from the front of the queue
  • front: 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

Java

  • add: insertion at the back of the queue
  • poll: deletion from the front of the queue
  • peek: which retrieves the element at the front without removing it

Java doesn't actually have a Queue class; it's only an interface. The most commonly used implementation is the LinkedList, declared as follows:

Queue<Integer> q = new LinkedList<Integer>();
q.add(1); // [1]
q.add(3); // [3, 1]
q.add(4); // [4, 3, 1]
q.poll(); // [4, 3]
System.out.println(q.peek()); // 3

Python

Python has a builtin queue module.

  • Queue.put(n): Inserts element to the back of the queue.
  • Queue.get(): Gets and removes the front element. If the queue is empty, this will wait forever, creating a TLE error.
  • Queue.queue[n]: Gets the nth element without removing it. Set n to 0 for the first element.
from queue import Queue
q = Queue() # []
q.put(1) # [1]
q.put(2) # [1, 2]
v = q.queue[0] # v = 1, q = [1, 2]
v = q.get() # v = 1, q = [2]
v = q.get() # v = 2, q = []
v = q.get() # Code waits forever, creating TLE error.

Warning!

Python's queue.Queue() uses Locks to maintain a threadsafe synchronization, so it's quite slow. To avoid TLE, use collections.deque() instead for a faster version of a queue.

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 O(1)\mathcal{O}(1) insertions and deletions from both the front and the back of the deque. Not very common in Bronze / Silver.

C++

std::deque

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 iith element of a deque dq\texttt{dq}, do dq[i]\texttt{dq}[i].

Java

In Java, the deque class is called ArrayDeque. The four methods for adding and removing are addFirst , removeFirst, addLast, and removeLast.

ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
deque.addFirst(3); // [3]
deque.addFirst(4); // [4, 3]
deque.addLast(7); // [4, 3, 7]
deque.removeFirst(); // [3, 7]
deque.addFirst(1); // [1, 3, 7]
deque.removeLast(); // [1, 3]

Python

In Python, collections.deque() is used for a deque data structure. The four methods for adding and removing are appendleft, popleft, append, and pop.

d = collections.deque()
d.appendleft(3) # [3]
d.appendleft(4) # [4, 3]
d.append(7) # [4, 3, 7]
d.popleft() # [3, 7]
d.appendleft(1) # [1, 3, 7]
d.pop() # [1, 3]

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.

Java

import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 6;
boolean[] visited = new boolean[n];
List<Integer>[] adj = new ArrayList[6];
for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
adj[0] = new ArrayList<>(Arrays.asList(1, 2, 4));
adj[1] = new ArrayList<>(Arrays.asList(3, 4));

C++

#include <queue>
#include <vector>
using std::queue;
using std::vector;
int main() {
int n = 6;
vector<vector<int>> adj(n);
vector<bool> visited(n);

Python

from collections import deque
"""
Define adjacency list and read in problem-specific input
In this example, we've provided "dummy input" that's
reflected in the GIF above to help illustrate the
order of the recrusive calls.
"""

Solution - Building Roads

Note that each edge decreases the number of connected components by either zero or one. So you must add at least C−1C-1 edges, where CC is the number of connected components in the input graph.

To compute CC, 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 CC equals the number of times we perform the visiting operation.

There are many valid ways to pick C−1C-1 new roads to build. One way is to choose a single representative from each of the CC components and link them together in a line.

DFS Solution

C++

#include <deque>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
void dfs(int node) {

Java

import java.io.*;
import java.util.*;
public class BuildingRoads {
static List<Integer>[] adj;
static boolean[] visited;
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();

Python

from collections import deque
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
adj[a - 1].append(b - 1)
adj[b - 1].append(a - 1)

However, this code causes a runtime error on nearly half the test cases. What could be going wrong?

An Issue With Deep Recursion

If you run the solution code locally on the line graph generated by the following Python code:

n = 100000
print(n, n - 1)
for i in range(1, n):
print(i, i + 1)

C++

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.

Java

then you might get a StackOverflowError 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 less than a megabyte by default. To resolve this, you can pass an option of the form -Xss... to run the code with an increased stack size. For example, java -Xss512m Main will run the code with a stack size limit of 512 megabytes.

Python

then you will observe a RecursionError that looks like this:

Traceback (most recent call last):
  File "input/code.py", line 28, in <module>
	solve(n, adj)
  File "input/code.py", line 14, in solve
	dfs(start, start)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  File "input/code.py", line 9, in dfs
	dfs(start, next)
  [Previous line repeated 994 more times]
  File "input/code.py", line 7, in dfs
	if next in unvisited:
RecursionError: maximum recursion depth exceeded in comparison

This will occur for N>103N>10^3 since the recursion limit in Python is set to 1000 by default. We can fix this by increasing the recursion limit with sys.setrecursionlimit(10 ** 6), although we still get TLE on two test cases. To resolve this, we can implement a BFS solution, as shown below.

BFS Solution

C++

#include <deque>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
int m;
cin >> n >> m;

Java

import java.io.*;
import java.util.*;
public class BuildingRoads {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int m = io.nextInt();
List<Integer>[] adj = new ArrayList[n];

Python

from collections import deque
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
adj[a - 1].append(b - 1)
adj[b - 1].append(a - 1)

Connected Component Problems

StatusSourceProblem NameDifficultyTags
SilverEasy
Show TagsConnected Components
SilverEasy
SilverEasy
Show TagsConnected Components
KattisEasy
Show TagsConnected Components
ACSLEasy
Show TagsDFS
CSESNormal
GoldNormal
Show TagsBinary Search, Connected Components
SilverNormal
Show TagsBinary Search, Connected Components
SilverNormal
Show Tags2P, Binary Search, Connected Components
SilverNormal
Show TagsDFS
CFNormal
Show TagsConnected Components, DFS
CFHard
Show TagsDFS, Sorted Set
KattisVery Hard
Show TagsBinary Search, Connected Components
SilverVery 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.

C++

#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) {

Java

Warning!

Because Java is so slow, an adjacency list using lists/arraylists results in TLE. Instead, the Java sample code uses the edge representation mentioned in the optional block above.

import java.io.*;
import java.util.*;
public class BuildingTeams {
static List<Integer>[] adj;
static int[] assigned;
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();

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.

C++

#include <deque>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
int m;
cin >> n >> m;

Java

import java.io.*;
import java.util.*;
public class BuildingTeams {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int m = io.nextInt();
List<Integer>[] adj = new ArrayList[n];

Python

from collections import deque
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
adj[a - 1].append(b - 1)
adj[b - 1].append(a - 1)

Graph Two-Coloring Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBipartite
SilverEasy
Show TagsBipartite
CFEasy
Show TagsBipartite
Baltic OIHard
Show TagsDFS, Median
CCHard
Show TagsBipartite, DFS
APIOVery Hard
Show TagsBipartite

Quiz

What's the main difference between DFS and BFS?

Question 1 of 4

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!

PrevNext