Depth First Search (DFS) Pseudocode and Program in Java

[3898 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.


Depth First Search Pseudocode or Algorithm

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); } }
        

Don't Understand Algorithm and Flowchart? Learn quickly using our Expert's Notes



Want to get in-depth understanding of Algorithms?


Are You Good enough in Algorithms? Test it now?


Comments



Search
Recommended Deals End in










Java Interview Questions For Beginner Notes
Quiz for Learners
Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    Depth First Search Pseudocode in Java

    Depth First Search Algorithm in Java

    DFS with example