Ticker

20/recent/ticker-posts

Advertisement

Depth-First Search

 Depth-First Search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node of an arbitrary node and explores as far as possible in the branch before backtracking.

Properties of Depth-first Search :

  1. The time complexity of DFS to traverse an entire graph takes time O(|V| + |E| ) where V refers to vertices and E for Edges in a graph.
  2. This traversal algorithm takes a total of O(|V|) space for a complete traversal.
  3. DFS internally uses a stack to find the closest path.
  4. In terms of speed, DFS is better compared to Breadth-first search.

How DFS Works?

Depth-first Traversal (or Search) for a graph is similar to traversal in a tree and the approach here is to start from the root node and move to its adjacent unvisited nodes, when there's no adjacent node, we backtrack to the parent node. This avoids visiting of processed node twice in a traversal.





In the above figure, it is an example of a directed graph with the vertices [A, B, C, D, E] with the edges:
  • A to B and A to C
  • B to D
  • C to E
  • D to E
So, the approach is to select any one of the vertexes as a root node and mark it as visited. Then, every other unvisited vertex is visited till there are no unvisited vertices. The main goal of the depth-first search is to visit every vertex in the graph thereby traversing the whole graph.
  • Start by iterating over the array list and pass each of the vertexes to the helper function.
  • The helper function with vertex parameter marks the visited array corresponding to that vertex as true.
  • Traverse each of the adjacent vertexes and mark them as visited.

Algorithm:

  1. Create a multidimensional array list of integer types.
  2. Add the vertices with their respective edges to the list.
  3. Create a boolean array to keep track of visited vertices.
  4. Create a stack of Integer type and push the root vertex.
  5. Print the current vertex and mark it as visited.
  6. Iterate through the adjacent unvisited vertices present in the list till the stack is empty.

Implementation of Depth-first Search  in java:

The following  function requires an index of node and array as parameters.
class DFS { public static void main(String[] args) { ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); int vertex = 5; for (int i = 0; i < vertex; i++) { ArrayList<Integer> l = new ArrayList<Integer>(); list.add(l); } // Here as from the above graph consider A,B,C,D,E as 0,1,2,3,4 // These are following edges: 0->1 & 0->2 // 1->3 & 2->4 & 3->4 list.get(0).add(1); list.get(0).add(2); list.get(1).add(3); list.get(2).add(4); list.get(3).add(4); // set every vertex value as unvisited boolean[] visited = new boolean[vertex]; for (int i = 0; i < vertex; i++) { visited[i] = false; } // pass the parameters to DFS function DFS(list, visited, vertex); } public static void DFS(ArrayList<ArrayList<Integer>> list, boolean visited[], int vertex) { Stack<Integer> s = new Stack<>(); s.push(0); while (!s.empty()) { int temp = s.pop(); System.out.print(temp + " "); visited[temp] = true; for (int i = 0; i < list.get(temp).size(); i++) { if (!visited[list.get(temp).get(i)]) { s.push(list.get(temp).get(i)); } }     } } }
This function prints the vertex by visiting every vertex in the graph.

I hope you guys liked this article and here are some articles you may like:



Post a Comment

0 Comments