Depth-First Search (DFS)

Learn Depth-First Search (DFS)

Introduction

Depth-first search (DFS) is one of the basic algorithms for working with graphs.

The main idea of DFS is to go as deep as possible from the current vertex, and only return when there are no unvisited adjacent vertices left.

How does it work?

We start from one vertex. After visiting it, we recursively run DFS on each adjacent vertex that has not been visited yet. In this way, we visit all vertices reachable from the starting vertex.

Classification of Graph Edges

When running DFS, edges can be classified using the entry and exit times of their endpoints.

This classification is often useful in graph problems.

Suppose DFS is processing an edge $(x, y)$ .

1. If vertex $y$ has not been visited yet

Tree edge — the edge $(x, y)$ is called a tree edge if DFS goes through it to visit $y$ for the first time.

Depth-First Search (DFS)

Introduction

Classification of Graph Edges

1. If vertex $y$ has not been visited yet

2. If vertex $y$ has already been visited

Implementation

Depth-First Search (DFS)

Introduction

Classification of Graph Edges

1. If vertex yyy has not been visited yet

2. If vertex yyy has already been visited

Implementation

1. If vertex $y$ has not been visited yet

2. If vertex $y$ has already been visited