How Will You Know if Dfs Works

Depth Starting time Search (normally called as DFS ) was first studied in the 19th century past French mathematician Charles Pierre Trémaux as a strategy for solving mazes. It is one of the well-nigh commonly preferred algorithms used for traversing or search in tree or graph data structures by using the thought of backtracking. DFS is also known equally Depth First Traversal in example we are using the algorithm in tree information structures ( Note:  A tree is a special kind of graph with no cycles). The algorithm starts at a node of a graph and goes equally far as possible in a given path, and so backtracks until it finds an unexplored path, and so explores the rest of it. The process is repeatedly followed until all the nodes in the graph are explored.

Table of content

1. Application
2. DFS Algorithm
3. DFS Algorithm Example
4. Pseudocode of DFS
5. Implementation of DFS
6. Complexity Assay of DFS
7. FAQs

Application

DFS algorithm works in the following way

Nigh of the concepts in figurer scientific discipline tin be visualized and represented in terms of graph information structure. DFS is one such useful algorithm for analysing these problems easily.

• Solving maze-similar puzzles with just one solution: DFS can be used to find all solutions to a maze problem by simply considering nodes on the current path in the visited gear up.
• Topological Sorting:
  • This is mainly used for scheduling jobs from the given dependencies amid jobs. DFS is highly preferred arroyo while finding solutions to the following blazon of problems using Topological Sort:
    • teaching/job scheduling
    • ordering of formula cell evaluation when recomputing formula values in spreadsheets
    • determining the social club of compilation tasks to perform in makefiles
    • information serialization
    • resolving symbol dependencies in linkers
• Mapping Routes and Network Analysis
• Path Finding: DFS is used for finding path betwixt two given nodes - source and destination - in a graph.
• Cycle detection in graphs

Depth Start Search Algorithm

• The DFS algorithm is the search algorithm which begins the searching from the root node and goes down till the foliage of a branch at a time looking for a item fundamental. If the key is not plant, the searching retraces its steps back to the point from where the other branch was left unexplored and the same process is repeated for that branch.
• DFS follows the following 3 steps:
  1. Visit a node "S".
  2. Mark "S" every bit visited.
  3. Recursively visit every unvisited node fastened to "South".
• Since DFS is of recursive  nature, this can be implemented using stacks . (Refer the FAQ section to sympathise why we utilize stacks)
• Implementation :
  1. Push the source node to the stack.
  2. Maintain a data structure to marking if a node is visited or non, say,
     

                       boolean[] visited = new boolean[total_nodes_in_graph]  //Default value will be false for all the elements                                  

  3. Mark source node S as visited: visited[S] = True
  4. While stack is not empty repeat steps 5 - 8 below
  5. Pop node, say, A from the stack
  6. If visited[A]  is True go to footstep v, else go to step 7.
  7. Mark visited[A] = True .
  8. Cheque if A is the node that we demand. If yeah, pause dfs. Else, push all the adjacent nodes of A which are not visited into the stack.

• In this fashion, nosotros will traverse a path until it is exhausted. Meaning, either at that place are no next nodes or all the adjacent nodes are already visited.

Note:

• The "next nodes" hateful the "neighbors" of the selected node.
• If the nodes are non marked every bit visited, then we might visit the aforementioned node more one time and we will possibly end up in an infinite loop.

DFS Algorithm Instance

Consider the post-obit graph structure where South is the Source node to begin DFS with:

The goal here is to discover whether the node Eastward is nowadays in the graph.  Merely by seeing the graph, we tin can say that node E is not present. Lets see how DFS works to identify this.

Step 1:  We push S to the STACK

Step two:  Marker S every bit Visited.

Stride 3:  While the stack is not empty, repeat the below steps:

• Pop the top element i.east., node S out of STACK ==>STACK = [ ]
• Is the popped element equal to the node element we were looking for? If yes, render true. Here S != Due east . Hence, continue with the below steps.
• Push all the adjacent nodes of S which are not visited nonetheless into STACK.
• We push nodes C, B, and A into STACK.STACK = [C, B, A]

• Pop the pinnacle chemical element i.eastward., node A out of STACK.

  • Is the popped element equal to the node chemical element we were looking for? If yeah, return true. Here A != Due east . Hence, nosotros proceed with the beneath steps.

• Mark A equally visited. Stack at present becomes STACK = [C, B]

• Push all the adjacent nodes of A which are not visited still into STACK.

  • Nosotros push node D into STACK and stack at present has STACK = [C, B, D]

• Pop the elevation element i.due east., node D out of STACK. Mark D as visited. After popping D, stack is now: STACK = [C, B]

  • Is the popped element equal to the node element we were looking for? If yes, render truthful. Here A != E . Hence, we go along withthe below steps.

• Push all the adjacent nodes of D which are not visited still into STACK.

  • Nosotros button nodes C and B into STACK. STACK = [C, B, C, B]

• Pop the top element i.eastward., node B out of STACK.

  • Is the popped element equal to the node element we were looking for? If yes, return truthful. Here B != E . Hence go on with the beneath steps.

• Mark B as visited. STACK = [C, B, C]

• Push all the adjacent nodes of B which are not visited however into STACK.

  • There are no adjacent nodes of B which are not visited. So stack will withal be STACK = [C, B, C]

• Pop the top element i.due east., node C out of STACK.

  • Is the popped chemical element equal to the node element we were looking for? If yep, return true. Here C != E . Hence proceed with the below steps.

Marker C as visited. Stack becomes STACK = [C, B]

• Button all the adjacent nodes of C which are not visited still into STACK.

  • There are no side by side nodes of C which are non visited. Hence stack will remain: STACK = [C, B]

• Now, we popular B from STACK and see that it was visited earlier. After popping B, stack is STACK = [C]

• We continue with the adjacent iteration and pop C from STACK and see that it was visited earlier. Stack now become southward empty: STACK = [ ]

• STACK is now empty and hence nosotros stop dfs as all the nodes have been visited and we havent found any nodes matching to node E. Hence we return faux.

This is how a depth-first search works, by traversing the nodes depth-wise. We stop DFS and return truthful  when we find the required node (key). We render false  when we have not plant the key despite of exploring all the nodes.

Pseudocode of Depth Beginning Search

Pseudocode of recursive DFS

          /** * Pseudo code for recursive DFS * @Parameters: next list G, source node,  * visited assortment, cardinal (node to be searched) */  DFS(next[][], source, visited[], key) {    if(source == fundamental) render true //We found the fundamental    visited[source] = True        FOR node in adjacent[source]:        IF visited[node] == Faux:           DFS(adjacent, node, visited)        Finish IF    Terminate FOR    render false    // If information technology reaches hither, then all nodes have been explored                    //and we still havent plant the key. }                  

Pseudocode of iterative DFS

          /** * Pseudo lawmaking for iterative DFS * @Parameters: Graph G, source node s, fundamental */  DFS(M, s, cardinal):       stack = new Stack()       stack.button( s )            //Push button due south to stack        mark s equally visited       while ( stack is not empty):             //Pop node from stack and commencement to visit its children             five  =  stack.popular()                          if(v == key) return true //We institute the cardinal                          //Push button all the unvisited neighbours of v to stack              for all neighbours w of 5 in Graph G:                 //unvisited neighbors                 if w is not visited :                         stack.push( west )                               mark w as visited       return false     // If it reaches here, then all nodes have been explored                        //and we notwithstanding havent found the key.        

Implementation Of Depth-showtime Search

• C
• C++
• Java
• Python

                Implementation of Depth-first Search in C:                  #include <stdio.h>                  #include <stdlib.h>                  struct                  node {                  int                  vertex;                  struct                  node* next; };                  struct                  node* createNode(int                  v);                  struct                  Graph {                  int                  numVertices;                  int* visited;                  struct                  node** adjLists;                  // we need int** to shop a ii dimensional assortment. Similarly, we need struct node** to shop an assortment of Linked lists                  };                  struct                  Graph* createGraph(int);                  void                  addEdge(struct                  Graph*,                  int,                  int);                  void                  printGraph(struct                  Graph*);                  void                  DFS(struct                  Graph*,                  int);                  int                  main() {                  struct                  Graph* graph = createGraph(4);     addEdge(graph,                  0,                  ane);     addEdge(graph,                  0,                  ii);     addEdge(graph,                  1,                  2);     addEdge(graph,                  2,                  3);          printGraph(graph);      DFS(graph,                  2);                  render                  0; }                  void                  DFS(struct                  Graph* graph,                  int                  vertex) {                  struct                  node* ptr = graph->adjLists[vertex];                  graph->visited[vertex] =                  1;         printf("Visited %d \n", vertex);                  while(ptr!=Nil) {                  int                  adj_vertex = ptr->vertex;                  if(graph->visited[adj_vertex] ==                  0) {                 DFS(graph, adj_vertex);             }             ptr = ptr->adjacent;         }        }                  struct                  node* createNode(int                  v) {                  struct                  node* new_node = malloc(sizeof(struct                  node));     new_node->vertex = v;     new_node->next = NULL;                  return                  new_node; }                  struct                  Graph* createGraph(int                  vertices) {                  struct                  Graph* graph = malloc(sizeof(struct                  Graph));     graph->numVertices = vertices;       graph->adjLists = malloc(vertices *                  sizeof(struct                  node*));          graph->visited = malloc(vertices *                  sizeof(int));                  int                  i;                  for                  (i =                  0; i < vertices; i++) {         graph->adjLists[i] = NULL;         graph->visited[i] =                  0;     }                  render                  graph; }                  void                  addEdge(struct                  Graph* graph,                  int                  source,                  int                  destination) {                  // Add together edge from src to dest                  struct                  node* newNode = createNode(destination);     newNode->next = graph->adjLists[source];     graph->adjLists[source] = newNode;                  // Add together edge from destination to source                  newNode = createNode(source);     newNode->next = graph->adjLists[destination];     graph->adjLists[destination] = newNode; }                  void                  printGraph(struct                  Graph* graph) {                  int                  v;                  for                  (5 =                  0; v < graph->numVertices; five++)     {                  struct                  node* ptr = graph->adjLists[5];         printf("\n Adjacency list of vertex %d\northward ", v);                  while                  (ptr)         {             printf("%d -> ", ptr->vertex);             ptr = ptr->adjacent;         }         printf("\n");     } }              

                Implementation of Depth-first Search in C++:                  #include <iostream>                  #include <vector>                  void                  dfs(int                  u, vector<vector<int> > &adj, vector<bool> &visited) {     visited[u] = true;                  for(int                  v : adj[u])                  if(!visited[v])             dfs(v, adj, visited);     cout <<                  "Done visiting node:                  "                  << u +                  1                  << endl; }                  int                  main() {                  int                  nodes, edges, u, v;     cin >> nodes >> edges;     vector<vector<int> > adj(nodes);     vector<bool> visited(nodes);                  for(int                  i =                  1; i <= edges; ++i) {         cin >> u >> v;         --u, --five;                  //there is an undirected border betwixt u and 5 (0 based)                  adj[u].push_back(five); adj[v].push_back(u); }  dfs(0, adj, visited);                  //presume root is always node 0                  return                  0; }              

                Implementation of DFS in Java:                  import                  coffee.io.*;                  import                  java.util.*;                  class                  Graph {                  private                  int                  numVertices;                  individual                  LinkedList<Integer> adjLists[];                  individual                  boolean                  visited[];       Graph(int                  vertices)     {         numVertices = vertices;         adjLists =                  new                  LinkedList[vertices];         visited =                  new                  boolean[vertices];                  for                  (int                  i =                  0; i < vertices; i++)             adjLists[i] =                  new                  LinkedList<Integer>();     }                  void                  addEdge(int                  source,                  int                  destination)     {         adjLists[source].add(destination);     }                  void                  DFS(int                  vertex)     {         visited[vertex] =                  truthful;         System.out.print(vertex +                  " ");           Iterator itr = adjLists[vertex].listIterator();                  while                  (itr.hasNext())         {                  int                  adj_node = itr.next();                  if                  (!visited[adj_node])                 DFS(adj_node);         }     }                  public                  static                  void                  main(String args[])     {         Graph g =                  new                  Graph(iv);            grand.addEdge(0,                  1);          thousand.addEdge(0,                  2);          chiliad.addEdge(i,                  two);          yard.addEdge(2,                  3);           Arrangement.out.println("Following is Depth First Traversal");           k.DFS(2);     } }              

                Implementation of DFS                  in                  python:                  def                  dfs(graph, vertex, visited=None):                  if                  visited                  is                  None:         visited = set()     visited.add(vertex)                  print(vertex)                  for                  node                  in                  graph[vertex] :                  if                  node                  not                  in                  visited:         dfs(graph, node, visited)  graph = {'0': set(['ane',                  '2']),                  '1': set(['0',                  '3',                  '4']),                  'two': fix(['0',                  '                  4                  ']),                  '3': set(['one',                  '                  4                  ']),                  'iv': set(['                  1                  ',                  'ii',                  'three'])}  dfs(graph,                  '0')
                              

Complexity Analysis of Depth Get-go Search

Time Complexity

• The time complication of DFS if the entire tree  is traversed is O(V)  where V is the number of nodes.
• If the graph is represented as adjacency list :
  • Here, each node maintains a listing of all its next edges. Let's presume that there are 5 number of nodes and E number of edges in the graph.
  • For each node, we find all its neighbors past traversing its adjacency listing just in one case in linear fourth dimension.
  • For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is Eastward. So, the time complexity in this case is O(V) + O(Eastward) = O(V + East) .
  • For an undirected graph, each edge appears twice. Once in the adjacency list of either stop of the edge. The time complexity for this case volition exist O(V) + O (2E) ~ O(Five + E) .
• If the graph is represented as an adjacency matrix  (a V x V array):
  • For each node, we will accept to traverse an entire row of length V in the matrix to discover all its outgoing edges.
  • Note that each row in an adjacency matrix corresponds to a node in the graph, and that row stores information almost edges emerging from the node. Hence, the fourth dimension complexity of DFS in this example is O(5 * V) = O(V ^two ) .
• The time complexity of DFS really depends on the data structure existence used to correspond the graph.

Space Complexity

• Since nosotros are maintaining a stack to keep rails of the final visited node, in worst example, the stack could take upto the size of the nodes(or vertices) in the graph. Hence, the space complication is O(V) .

FAQs

• Why tin can nosotros not implement DFS using Queues? Why practice we adopt stacks instead of other data structures?

  • In DFS, nosotros ever want to find the final node we visited to get in the other unvisited branches of that node in the most efficient way possible.
  • If we are using queue ( First in First out ) data structure:
    • To retrieve the last node visited, start, we will have to have all the elements out of the queue.
    • Nosotros will too need to store these elements except the last ane so that we can push them dorsum in the queue.
    • The concluding element taken out of the queue will exist the last visited node.
    • Nosotros now have to button all the elements taken out back to queue.
  • The way queue works will give united states the last visited node in O(n)  operations as that will be the last element inserted in the queue.
  • Stacks on the other hand, piece of work in "Terminal In Showtime Out"  manner. It will give the terminal node visited in O(1)  operations as that node will exist the summit element of the stack and we only accept to pop it. Hence, nosotros go for stacks.

• What are the classifications of edges in DFS of a graph?

  • We accept iv kinds  of edges in DFS of a graph.
  • Consider a directed graph every bit shown in the diagram below, DFS of the below graph is 1 ii four 3 5 6 . If DFS is applied on this graph, a tree is obtained which is represented and connected by ways of using green edges. The types of edges are as follows:

• Tree Edge : The border which is nowadays in the tree obtained later on applying  DFS on the graph. All the Greenish edges are tree edges.
• Forwards Edge : Edge (u, v)  such that five is descendant  merely not office of the DFS tree. Edge from node 1 to node six is a forward border.
• Dorsum edge :
  • Edge (u, v)  such that v  is ancestor  of edge u only not role of DFS tree. Edge from node 4 to node ane is a back edge.
  • Presence of back edge indicates a cycle in the directed graph.
• Cantankerous Edge : It is a edge which connects two nodes  such that they do not have any ancestor and a descendant relationship between them. Edge from node 3 to node 2 is a cross border.

• Can DFS be used for finding shortest possible path?

  • No .

• Why tin we non utilize DFS for finding shortest possible path?

  • In the implementation of DFS, there is no deterministic rule on what order the next children/neighbor to be explored is considered.
  • DFS does not guarantee that if node 1 is visited before another node 2 starting from a source vertex. It can not identify what node is closer to the source node.
  • DFS merely visits the 'deeper' nodes in any order. It can even be farther from source nodes. In the worst case, it might get as far as possible from the source node and then returns to unvisited adjacent nodes of visited nodes.
  • Due to this, DFS is not a reliable choice to notice the shortest path betwixt the nodes.

• Is DFS a complete algorithm?

  • A search algorithm is said to be consummate if at least ane solution exists then the algorithm is guaranteed to find a solution in a finite amount of time.
  • DFS is complete if the search tree is finite, meaning for a given finite search tree, DFS will come up with a solution if it exists.

• Is DFS a optimal algorithm?

  • A search algorithm is optimal if it finds a solution, it finds that in the all-time possible style.
  • DFS is non  optimal, meaning the number of steps in reaching the solution, or the cost spent in reaching information technology is loftier.

• When is it all-time to use DFS?

  • The usage of DFS heavily depends on the structure of the search tree/graph and the number and location of solutions needed.
    • If it is known that the solution is not far from the root of the tree, a latitude first search (BFS) might be better.
    • If the tree is very deep and solutions are rare, depth first search (DFS) might accept an extremely long time, merely BFS could be faster.
    • If the tree is very broad, a BFS might need too much retention, and so information technology might be completely impractical. We get for DFS in such cases.
    • If solutions are frequent but located deep in the tree we opt for DFS.

millerblipt1944.blogspot.com

Source: https://www.interviewbit.com/tutorial/depth-first-search/

Share this post