Depth-First Search (DFS)

Learn Depth-First Search (DFS)

Introduction

Depth First Search, usually called DFS, is one of the most important graph traversal algorithms. It is used when we start from one vertex and want to visit every vertex that can be reached from it.

The word “depth” means that DFS tries to go as deep as possible along one path before coming back. From the current vertex, it chooses an unvisited neighbor, goes there, then continues in the same way. When there are no more unvisited neighbors, the recursion returns to the previous vertex and tries other directions.

This is why DFS is very natural to write using recursion. Each recursive call is responsible for one vertex: mark this vertex as visited, then recursively visit all of its unvisited neighbors.

Problem statement

You are given an undirected graph with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$. You are also given a starting vertex $s$.

For every vertex $i$ from to , print one integer: