Depth First Search (DFS) Pseudocode and Program in Java

[5548 views]

What is Depth First Search(DFS)?

It is a kind of algorithm technique for traversing a tree, where the traversing starts from a node and moves along the path as far as possible before backtracking and visiting the other branches.

Image Reference: Wikipedia

Depth First Search Pseudocode

Void Dfs(LinkedList<Integer> arr[], int source ) Initialize Stack S; S.Push(source); Initialize Boolean array v to keep track of visited nodes Mark source as visited While(Q is not empty) { Source = S.pop Print source While(iterate over arr[]) { int k = iterated element If k is not marked , mark k and add to Stack} }

Depth First Search Implementation in Java

package graph; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class graph { public void initalize(LinkedList<Integer> arr[], int length) { for (int i = 0; i < length; i++) { arr[i] = new LinkedList<Integer>(); } } protected void add(int src, int dest, LinkedList<Integer> arr[]) { arr[src].add(dest); arr[dest].add(src); } void dfs(LinkedList<Integer> arr[], int n) { Stack<Integer> s = new Stack<Integer>(); boolean v[] = new boolean[6]; s.push(n); v[n] = true; while (!s.isEmpty()) { n = s.pop(); System.out.println(n); Iterator<Integer> it = arr[n].iterator(); while (it.hasNext()) { int k = it.next(); if (!v[k]) { s.push(k); v[k] = true; } } } } public static void main(String args[]) { LinkedList<Integer> arr[] = new LinkedList[6]; graph s = new graph(); s.initalize(arr, 5); s.add(0, 1, arr); s.add(0, 4, arr); s.add(1, 3, arr); s.add(3, 4, arr); s.add(3, 2, arr); s.dfs(arr, 0); } }