Very Frequent

0/13

# Depth First Search (DFS)

Authors: Siyong Huang, Andrew Wang, Jason Chen, Benjamin Qi

Recursively traversing a graph.

## DFS in Undirected Graphs

Resources | |||
---|---|---|---|

CSA | up to but not including "More about DFS" | ||

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

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

Optional: Adjacency List Without an Array of Vectors

See here.

### Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

Silver | Easy | ## Show TagsDFS | External Sol | ||

Silver | Easy | ## Show TagsDFS | |||

Silver | Easy | ## Show TagsDFS | External Sol | ||

Silver | Easy | ## Show TagsTree, DFS | |||

Kattis | Easy | ## Show TagsDFS | |||

Silver | Normal | ## Show TagsSorting | External Sol | ||

Gold | Normal | ## Show TagsDFS, Binary Search | |||

Silver | Normal | ## Show TagsDFS, Binary Search | |||

Kattis | Very Hard | ## Show TagsDFS, Binary Search |

## DFS in Directed Graphs

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CSES | Easy | ||||

CCO | Normal | ||||

Silver | Hard | External Sol |

### Module Progress:

## Give Us Feedback on Depth First Search (DFS)!

### Join the Discussion!

Feel free to voice your thoughts in the comments section.