Depth First Search (DFS) with Explanation and Code

Introduction

In this article, you'll learn about the depth-first search algorithm with an example and implementation in C++.

Depth-first search or depth-first traversal is a recursive algorithm for searching all vertices of a graph or tree data structure. Traversing means visiting all nodes of the graph.

Depth First Search Algorithm

Algorithms known as "deep-first search" are used to navigate or search tree or graph data structures. The algorithm starts at the root node (for graphs, choose any node as the root node) and goes as deep as possible along each branch before backtracking.

So the basic idea is to start from the root or any node, mark a node, then move to the next unmarked node and repeat this loop until there are no more unmarked neighbors. is. Then go back and look for other unmarked nodes and traverse them. Finally, print the nodes of the path.

The nodes can be split into two categories. Eventually, all the nodes will be marked as visited.

1. Visited
2. Not Visited

Implementation

The goal of this algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

1. We start by putting any vertex of the graph onto the stack.
2. Get the top item on the stack and add it to the visited list.
3. Create a list of neighbors of this node.
4. Add anything, not in the visit list to the top of the stack.
5. Repeat #2 & #3 until all nodes are marked as visited

The only problem is that, unlike trees, graphs can contain cycles (a node can be visited twice). To avoid processing a node multiple times, use a boolean visited array. A graph can contain multiple DFS traversals.

Passing the input:

 vector edges = { //node 0 is unconnected        {1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11}    };

Output: 0, 1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12