Depth First Search for dummies

Depth First Search is an algorithm that is used to search or traverse a graph. The path followed for explanation goes like this :

  1. Introduction
  2. Theory
  3. Basic Code
  4. Questions

If you don’t understand any specific thing, stay tuned. The questions will clear your doubts soon.

Introduction

The depth-first search is a graph algorithm that is used to search within a graph. “DFS” to refer to the Depth-first search, wherever used. One would have heard the story of Hansel and Gretel, in which Hansel dropped bread crumbs so that he does go back easily without getting lost. The depth-first search uses a similar strategy of marking the nodes visited. Also, DFS with little modification can lead to many different Graph algorithms so it's really important to have a strong grip over this basic algorithm before moving into graphs in depth. So DFS is the first algorithm for going into depth of other graph algorithms.

Prerequisites for this article are :

  1. Graph Representations
  2. Graph terminologies

Before starting the theory directly let me put a question for you. Think a bit, because if you get this you already know how to do a depth-first search.

You are in a maze at the starting point. You have to get to the end. How would you?”

So answer to the above question will help you to understand basic DFS! Suppose you start from a position X and reach Y where Y has two different paths to move into. Now you don’t know which one will lead to the endpoint. So you mark this point (this goes into recursion stack ;)) and move into path 1. If you get to the end well and good, else you come back to point Y move into path 2, and reach the end. If both paths don’t get you to the end, mark Y point as visited and move to the starting of the path that led you to Y and follows the same process.

Depth First Search

Theory

So, If you were able to answer the question or get the logic behind the basic maze question then you already know the basics of the DFS algorithm.

We can describe DFS as, let us start from a node X, which can be regarded as a root node, now node X has neighbors denoted by adj[X][i], i denotes ith neighbor. Now I choose one neighbor and search it, and do DFS on it. Now after searching ith I go to (i+1)th and DFS is too, and keep doing until all the neighbors of X are finished. This is done for all the nodes. In three steps I can summarise it as :

  1. Start or pick a starting node, generally 0 if not given.
  2. Now mark it visited, and check its neighbors.
  3. If the neighbor is already then don’t visit it again else DFS the neighbor.

DFS can be implemented using stacks explicitly or implicit through recursion stack. This article will involve recursion DFS.

Algorithm

Step 1. vis[n] are initialised to false and adj[n] list stores neighbour.
Step 2. run dfs from node say i
mark this node visited
for every neighbour:
if(vis[neighbour]) continue
dfs(neighbour)

Step 1: Marks each node as not visited initially.
Step 2: You begin DFS from the ith node and check all its neighbors. If they are visited, you don’t visit them again, else this node i is added to the recursion stack, and the neighbor is processed till all its neighbors are processed. Then you come back to the ith node and move to the next neighbor till all are visited.

Code

Question: Check if the given graph is connected or not. Now a graph (undirected) is connected if all its nodes can be reached from any of the nodes. Thus we will perform DFS to check if all the nodes are visited from node 0 or not. If all are visited, then it is connected else it is not.

The C++ code for basic DFS is given below.

#include <bits/stdc++.h>
using namespace std;
bool vis[10000] = {0};
vector<int> adj[10000];
void dfs(int x){// If visited , don't visited again
if(vis[x]) return;
// else set visited as true and do a DFS on its neighbours
vis[x] = true;
/*
Write conditional code here for pre-order like traversal
*/
// DFS all its neighbours
for(int i=0;i<adj[x].size();i++) {
int next = adj[x][i];
if(vis[next]) continue;
dfs(next);
}
/*
Write your code here for post-order like traversal
*/
}void main()
{
int n; cin >> n;
int x; cin >> x;
for(int i=0;i<x;i++)
{
int y,z;
cin >> y >> z;
adj[y].push_back(z);
adj[z].push_back(y);
}
dfs(0);
bool connected = true;
for(int i=0;i<n;i++)
if(vis[i]!=true) connected=false;
if(connected) cout << "This is connected graph";
else cout << "The graph is not connected";
return 0;
}

The code of DFS remains the same as in the dfs() function, while conditions may change w.r.t the question itself, and these conditions are put into the comments added in the above code.

General Way to Do Matrix form DFS Question

Now may have a question like this :

Suppose you are standing on a board of size n x n at coordinates (0,0) and you have your prize at coordinate (n-1,n-1). Now you have walls in between and you cannot jump over it. Can you take the prize? (You can only move up, down, left, right)

Such type of question can be converted into a graph like a problem where each coordinate is connected to its neighbor. In such cases, we define two things

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

Now dx and dy are defined as the changes in x coordinate and y coordinate you can make. Suppose you are in coordinate x,y right now, then you can have the next coordinate

nx = x + dx[i];
ny = y + dy[i];

Now, you can instead of using adj[x][i] in the above dfs, can preassume that every point or coordinate on the board have 4 neighbors thus DFS changes to :

void dfs(int x,int y)
{
if(vis[x][y]) return;
vis[x][y] = true;
for(int i=0;i<4;i++)
{
int nx = x+dx[i];
int ny = y+dy[i];
if(nx > n || nx < 0 || ny > n || ny < 0) continue;
if(vis[nx][ny]) continue;
dfs(x,y);
}
}

Clearly, you must observe that previously we defined every node with one index that is 1,2,3, etc. Here every node is mapped to two values i.e x,y and thus you have to dfs using these. Now to check if you can take the prize :

dfs(0,0)
if(vis[n-1][n-1] == true)
cout << "Prize is yours" << endl;
else cout << "Poor guy" << endl;

Bonus: Topological sorting of a directed graph involved nothing but observation and tweaking the DFS function. The same goes for Tarjan’s algorithm for SCC and many more! So when you read about these just try to relate them with Depth First Search and it will be much easier then.

Questions

Try to attempt these questions for further checking your understanding.

  1. Basic Graph Adjacency list representation and alike
  2. DFS and Path Finding
  3. DFS/BFS and connected components
  4. DFS with pair nodes
  5. DFS 2
  6. DFS 3
  7. Basic Topological Sorting
  8. Ice Cave

--

--

--

Engineering an Engineer in me.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Don’t Dress to Impress in the Winter

Yes, you live in a simulation.

CASHBACK promotion

Fun with Fixtures for Database Applications

{UPDATE} Словодел - головоломки со слогами, игры в слова Hack Free Resources Generator

The District Weekly — July 18th

How does cloud migration help with compliance in education?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Pulkit Joshi

Pulkit Joshi

Engineering an Engineer in me.

More from Medium

CAN YOU SOLVE IT ?! #01 Construction of a cabled network

Why a masters degree is no longer required to grow in your career?

My Journey To Software Development.

Women Who Code Announces CONNECT Recharge Conference