loading...

Depth-First-Search(DFS) Explained With Visualization

snj profile image Nick Mose Originally published at coderscat.com on ・2 min read

DFS Overview

The Depth First Search(DFS) is the most fundamental search algorithm used to explore the nodes and edges of a graph. It runs with time complexity of O(V+E), where V is the number of nodes, and E is the number of edges in a graph.

DFS is often used as a building block in other algorithms; it can be used to:

  1. A naive solution for any searching problem.
  2. Finding connected components or strongly connected components.
  3. Topological sorting.
  4. Finding the bridges of a graph.
  5. Detect cycles in a graph.

DFS Visualization on Maze

The source is at the position of left-up, and the target is the position of right-bottom.

As we can see, DFS explores as far as possible along each branch before backtracking:

dfs.gif

The maze is generated by disjoint set.

The recursive implementation

#include <list>
#include <vector>
#include <iostream>
using namespace std;

class Graph {
  int V;
  list<int> *adj;
  bool DFS_rec(int v, int t, vector<bool>& visited);

public:
  Graph(int V);
  void addEdge(int v, int w);
  bool DFS(int v, int t);
};

Graph::Graph(int V) {
  this->V = V;
  adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
  adj[v].push_back(w);
}

bool Graph::DFS_rec(int v, int t, vector<bool>& visited) {
  visited[v] = true;
  cout << v << " ";
  if(v == t) return true; // Find a path

  for (list<int>::iterator it; it = adj[v].begin(); it != adj[v].end(); ++it) {
    if (!visited[*it] && DFS_rec(*it, t, visited))
      return true;
  }
  return false;
}

bool Graph::DFS(int v, int t) {
  vector<bool> visited(V, false);
  return DFS_rec(v, t, visited);
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  cout << "Following is Depth First Traversal (0 -> 3): \n";
  if(g.DFS(0, 3)) cout << "\nFind a Path!" << std::endl;
  else cout << "\nNo Path!" << std::endl;
  return 0;
}

The iterative implementation

A non-recursive implementation of DFS needs the data-structure of stack.

The worst-case space complexity is O(E).

bool Graph::DFS(int v, int t) {
  vector<bool> marked(V, false);

  stack<int> S;
  S.push(v);
  marked[v] = true;
  while(!S.empty()) {
    int n = S.top(); S.pop();
    cout << n << " ";
    if(n == t) //Find a path to target
      return true;
    for(list<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
      if(!marked[*it]) {
        marked[*it] = true;
        S.push(*it);
      }
    }
  }
  return false;
}

References

The post Depth-First-Search(DFS) Explained With Visualization appeared first on CodersCat.

Posted on by:

snj profile

Nick Mose

@snj

Programming for 16 years. Write stuff about programming and writing on coderscat.com. Programming languages, security, algorithms.

Discussion

markdown guide