Depth First Search (DFS)

Author: Siyong Huang

Prerequisites

Recursively traversing a graph.

DFS in Undirected Graphs Solution - Building Roads Problems DFS in Directed Graphs

DFS in Undirected Graphs

Resources
CSA	Depth First Search	up to but not including "More about DFS"
CPH	12.1 - DFS	example diagram + code

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.

Building Roads

CSES - Easy

Focus Problem – read through this problem before continuing!

For example, the goal of this problem above is to add edges such that the entire graph is a single connected component.

Solution - Building Roads

Solution

Problems

Source	Problem Name	Difficulty	Tags	Solution
Silver	Closing the Farm	Easy	Show Tags DFS	External Sol
Silver	Moocast	Easy	Show Tags DFS	Internal Sol
Silver	Fence Planning	Easy	Show Tags DFS	External Sol
Silver	Mootube	Easy	Show Tags Tree, DFS	Internal Sol
Kattis	Birthday Party	Easy	Show Tags DFS	Internal Sol
Silver	Moo Particle	Normal	Show Tags Sorting	External Sol
Gold	Moocast	Normal	Show Tags DFS, Binary Search	Internal Sol
Silver	Wormhole Sort	Normal	Show Tags DFS, Binary Search	Internal Sol
Kattis	Lane Switching	Very Hard	Show Tags DFS, Binary Search	Internal Sol

DFS in Directed Graphs

Source	Problem Name	Difficulty	Solution
CSES	Flight Routes Check	Easy	Internal Sol
CCO	Escape Room	Normal	Internal Sol
Silver	Snow Boots	Hard	External Sol

Give Us Feedback on Depth First Search (DFS)!

Module Progress:

DFS in Undirected Graphs Solution - Building Roads Problems DFS in Directed Graphs Edit on Github

Depth First Search (DFS)

Prerequisites

Table of Contents

DFS in Undirected Graphs

Solution - Building Roads

Problems

DFS in Directed Graphs

Give Us Feedback on Depth First Search (DFS)!

Module Progress:

Table of Contents

Depth First Search (DFS)

Prerequisites

Table of Contents

DFS in Undirected Graphs

Solution - Building Roads

Problems

DFS in Directed Graphs

Give Us Feedback on Depth First Search (DFS)!

Module Progress:Not Started

Table of Contents

Module Progress: