DFS-DEPTH FIRST SEARCH CODE- ITERATIVE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

We will be seeing the Iterative way for implementing Depth First Search (DFS). Although there are various ways to write this Iterative code.

However, we will write the code little differently. So that you can corelate it with the Depth First Search (DFS) explanation.

In the Iterative code we will create the stack and maintain it ourselves.

DFS - Depth First Search code for Undirected Graph - Iterative approach

Example :

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

public class DFSIteration {

    static LinkedList<LinkedList<String>>  adjacencyList;
    static LinkedList<String> vertices;
    static boolean visited[];

    void insertVertex(String vertex) {

        vertices.add(vertex);
    }

    void constructAdjacencyList(String vtx, String adjcVertex) {

        int vtxIndex = vertices.indexOf(vtx);

        adjacencyList.add(new LinkedList<String>());
        adjacencyList.get(vtxIndex).add(adjcVertex);
    }

    void depthFirstSearch(String source){

        int sourceIndex = vertices.indexOf(source);

        visited[sourceIndex] = true;

        Stack<String> stack = new Stack<>();

        stack.push(source);

        System.out.print(source+" --> ");

        while (!stack.empty()) {

            source = stack.peek();

            sourceIndex = vertices.indexOf(source);

            String str = "";
            for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) {

                str = iter.next();

                int i = vertices.indexOf(str);

                if (visited[i] == false) {

                    stack.push(str);
                    visited[i] = true;
                    System.out.print(str + " --> ");
                    break;
                }
            }

            if (!stack.peek().equals(str)){
                stack.pop();
            }
        }
        System.out.println("\b\b\b\b");
    }

    public static void main(String[] args) {

        int V = 6;

        DFSIteration dfsIteration = new DFSIteration();

        visited = new boolean[V];

        adjacencyList = new LinkedList<LinkedList<String>>();

        vertices = new LinkedList<>();

        // Insert Vertices

        dfsIteration.insertVertex("a");
        dfsIteration.insertVertex("b");
        dfsIteration.insertVertex("c");
        dfsIteration.insertVertex("d");
        dfsIteration.insertVertex("e");
        dfsIteration.insertVertex("f");

        dfsIteration.constructAdjacencyList("a", "c");
        dfsIteration.constructAdjacencyList("a", "d");

        dfsIteration.constructAdjacencyList("b", "d");
        dfsIteration.constructAdjacencyList("b" ,"e");
        dfsIteration.constructAdjacencyList("b" ,"c");

        dfsIteration.constructAdjacencyList("c", "a");
        dfsIteration.constructAdjacencyList("c", "b");
        dfsIteration.constructAdjacencyList("c", "e");

        dfsIteration.constructAdjacencyList("d", "a");
        dfsIteration.constructAdjacencyList("d" ,"b");
        dfsIteration.constructAdjacencyList("d", "e");
        dfsIteration.constructAdjacencyList("d", "f");

        dfsIteration.constructAdjacencyList("e", "b");
        dfsIteration.constructAdjacencyList("e", "c");
        dfsIteration.constructAdjacencyList("e", "d");
        dfsIteration.constructAdjacencyList("e", "f");

        dfsIteration.constructAdjacencyList("f", "d");
        dfsIteration.constructAdjacencyList("f", "e");

        dfsIteration.depthFirstSearch("a");

    }
}

Output :

a --> c --> b --> d --> e --> f

We have implemented Depth First Search (DFS) on the below graph :

We can take various ways to navigate the graph using Depth First Search (DFS). Just remember our main intension is to visit all the vertices.

In this case we have covered the graph in the following path :

a --> c --> b --> d --> e --> f

Let us see how ?

Code Explanation for DFS - Depth First Search - Iterative :

Below code explains the methods :

void constructAdjacencyList(String vtx, String adjcVertex)

void insertVertex(String vertex)

Almost the same we have discussed in BFS. You can skip it if you want to.

Click Here - To understand the details of the methods 'void constructAdjacencyList(String vtx, String adjcVertex)' and 'void insertVertex(String vertex)'.

Let's list out, what all do we need to support Depth First Search Data Structure.

We need a Linked List to store the vertices.
We need a doubly Linked List to store the adjacency linked list.
We need a Queue and an array to store its Levels.
We need a boolean array to store the Vertices that are already visited.

Now, let us see the above code.

We have a Linked List to store the Vertices.

static LinkedList<String> vertices;

We also have a doubly Linked List to store the Adjacency List.

static LinkedList<LinkedList<String>> adjacencyList;

Similarly, we have a stack defined inside the method 'depthFirstSearch(...)'.

Stack<String> stack = new Stack< >();

And, there is a boolean array to store the Vertices that are visited.

static boolean visited[];

Note :The variables are marked as static, so that they could be accessed from main(...) method.

So, the first thing we will do is, insert the Vertices to the 'LinkedList<String> vertices' Linked List.

vertices = new LinkedList< >();

dfsIteration.insertVertex("a");
dfsIteration.insertVertex("b");
dfsIteration.insertVertex("c");
dfsIteration.insertVertex("d");
dfsIteration.insertVertex("e");
dfsIteration.insertVertex("f");

Explanation of 'void insertVertex(String vertex)' method

void insertVertex(String vertex) {

    vertices.add(vertex);
}

'void insertVertex(String vertex)' is quite simple.

There is just one statement in it.

vertices.add(vertex);

It accepts 'String vertex' as a parameter and adds it to the Linked List, 'vertices'.

The next thing we will do is, create an Adjacency List to track the Adjacent Vertices.

Let us take the example of vertex 'a', to explain the creation of Adjacency List.

As we have seen, 'a' has two adjacent vertices(i.e. c and d). And we have used the constructAdjacencyList(...) method to construct the Adjacency Matrix.

dfsIteration.constructAdjacencyList("a", "c");
dfsIteration.constructAdjacencyList("a", "d");

Note :Just remember, creating an Adjacency List above is same as creating an Edge. As the Adjacency List is actually a group of Edges.

Explanation of 'void constructAdjacencyList(String vtx, String adjcVertex)' method

void constructAdjacencyList(String vtx, String adjcVertex) {

    int vtxIndex = vertices.indexOf(vtx);

    adjacencyList.add(new LinkedList<String>());
    adjacencyList.get(vtxIndex).add(adjcVertex);
}

Although, the above method is explained in 'Adjacency List Code' tutorial. I will give a brief explanation in this tutorial.

When a method call is made,

The variable 'vtx' is assigned with value "a" and 'adjcVertex' is assigned with "b".

Now, the first line,

int vtxIndex = vertices.indexOf(vtx);

Calculates the index/position of Vertex 'a'. And as we can see the index 'a' is 0.

Now, in the next line,

adjacencyList.add(new LinkedList<String>());

We are initialising the first row of the 2D Linked List, 'adjacencyList'.

But with what?

We are initialising it with a Linked List 'new LinkedList<String>()',

adjacencyList.add(new LinkedList<String>());

So that the first row can hold the Adjacency List for vertex 'a'.

a --- c ---> d

Similarly, the second row should hold the Adjacency List for vertex 'b' and so on.

And in this iteration, our target is to find out the first row(To create an Adjacency List for vertex 'a') and insert vertex 'b' to it.

And the below code does that.

adjacencyList.get(vtxIndex).add(adjcVertex);

We get the index of vertex 'a'

vtxIndex = vertices.indexOf(vtx);

As we know 'vtx' is 'a'.

Then add 'adjcVertex'(That contains vertex 'c') to the 0th index of 'adjacencyList'.

adjacencyList.get(0).add("c");

And following it we form the Adjacency List.

Now, we come across the most important method 'void depthFirstSearch(String source)' that performs the Depth First Search (DFS).

Explanation of 'void depthFirstSearch(String source)' method

void depthFirstSearch(String source){

    int sourceIndex = vertices.indexOf(source);

    visited[sourceIndex] = true;

    Stack<String> stack = new Stack< >();

    stack.push(source);

    System.out.print(source+" --> ");

    while (!stack.empty()) {

        source = stack.peek();

        sourceIndex = vertices.indexOf(source);

        String str = "";
        for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) {

            str = iter.next();

            int i = vertices.indexOf(str);

            if (visited[i] == false) {

                stack.push(str);
                visited[i] = true;
                System.out.print(str + " --> ");
                break;
            }
        }

        if (!stack.peek().equals(str)){
            stack.pop();
        }
    }
        System.out.println("\b\b\b\b");
}

We have called the 'void depthFirstSearch(String source)' from the main method passing 'a' as the parameter.

dfsIteration.depthFirstSearch("a");

So, the first thing we will do is, take the index of 'a',

int sourceIndex = vertices.indexOf(source);

Now, if we see the List of vertices,

We can see that 'a' lies in index 0.

Next, we mark 'a' as visited,

visited[sourceIndex] = true;

in the 'visited[]' array,

visited[0] = true;

Then, we create the stack,

Stack<String> stack = new Stack< >();

And the immediate next thing we do is, push 'a' to the stack.

stack.push(source);

Then we print the vertex 'a'.

System.out.print(source+" --> ");

Output :

a -->

Next, we enter the 'while()' loop that continues until the stack is not empty.

while (!stack.empty()) {

    source = stack.peek();

    sourceIndex = vertices.indexOf(source);

    String str = "";
    for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) {

        str = iter.next();

        int i = vertices.indexOf(str);

        if (visited[i] == false) {

            stack.push(str);
            visited[i] = true;
            System.out.print(str + " --> ");
            break;
        }
    }

    if (!stack.peek().equals(str)){
        stack.pop();
    }
}

In the 'while()' loop, we take the top element(i.e. 'a') in the 'source' variable.

source = stack.peek();

Note :Just remember, 'stack.peek()' does not pop the top element from the stack. It just shows the top element of the stack.

The we take the index of the top element(0 is the index of 'a').

sourceIndex = vertices.indexOf(source);

Then comes the 'for(...)' loop, where we find the find the adjacent vertices of the top element(i.e. 'a').

for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) {

    str = iter.next();

    int i = vertices.indexOf(str);

    if (visited[i] == false) {

        stack.push(str);
        visited[i] = true;
        System.out.print(str + " --> ");
        break;
    } 
}

And the 'for' loop itself needs a little explanation.

Click Here - To understand the details of the methods 'void constructAdjacencyList(String vtx, String adjcVertex)' and 'void insertVertex(String vertex)'.

The first statement of the 'for' loop (i.e. The initialisation section of the loop),

Iterator<String> iter = adjacencyList.get(sourceIndex).iterator()

is where we get the Adjacent Vertices of vertex 'c' in the 'Iterator<String> iter'.

Thinking How?

Well ! The 'adjacencyList' is a 2D Linked List that stores the adjacent vertices. And the trick is played in,

adjacencyList.get(sourceIndex).iterator()

As we have seen, the sourceIndex is 0 (Because the index of vertex 'a' is 0).

And the 'iter' variable of 'Iterator<String> iter' gets the adjacency list of vertex 'a' in it.
The next statement,

iter.hasNext()

tells the 'for' loop to continue until there are elements in the list.
And ! Well ! There is no increment section. We have left it blank

'iter' variable of 'Iterator<String> iter', stores the Adjacency List of vertex 'a' in it.So, 'iter' has the elements 'c' and 'd' in it.

Now, 'str' contains the first adjacent vertex 'c'.

str = iter.next();

Next, we find the index of vertex 'c',

int i = vertices.indexOf(str);

Now, if we see the List of vertices,

We can see that 'c' lies in index 2.

So, we check if 'c' is visited or not.

if (visited[i] == false) {

    stack.push(str);
    visited[i] = true;
    System.out.print(str + " --> ");
    break;
}

Now, if we check the visited array,

We found that 'visited[2] = false' and we get into the 'if' statement.

So, we push 'c' to the Queue.

And marked visited[2] = true,

visited[i] = true;

In the visited[] array,

then we break out of the 'for' loop

break;

After getting out of the 'for' loop, we check if the value inside the 'str' variable and the top element are equal or not.

if (!stack.peek().equals(str)){ stack.pop(); }

In this case 'str' has 'c' inside it and the top element of the stack is also 'c'.

So, we don't pop 'c' out of the stack and continue with the 'while' loop.

Note :The statement 'if (!stack.peek().equals(str))' says when we reach a vertex whose adjacent vertices are already visited. The statement 'stack.push(str)' will never be executed. And, 'str' will have a value that is not equal to the top element of the stack.

Similarly, we repeat the same process until all the vertices are visited.

Now, let's visit the 'while()' loop again.

The top element is 'f' now,

source = stack.peek();

So, the value of 'source' variable is 'f' and

sourceIndex = vertices.indexOf(source);

the value of 'sourceIndex' variable would be '5'.

Now, the adjacent vertices of 'f' are 'd' and 'e'.

for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); )

So, the variable 'str' would contain 'd'(Since, the adjacent vertices of 'f' are 'd' and 'e') in the first iteration and would be 'e' in the second iteration.

str = iter.next();

int i = vertices.indexOf(str);

And both 'e' and 'd' are visited. So, the lines under the 'if' statement are never visited.

if (visited[i] == false) { stack.push(str); visited[i] = true; System.out.print(str + " --> "); break; }

So, the 'for' loop completes. And the value of the variable 'str' would be 'e'.

So, after getting out of the 'for' loop, we check if the value inside the 'str' variable and the top element are equal or not.

if (!stack.peek().equals(str)){ stack.pop(); }

In this case the top element is 'f' and the value in 'str' is 'e'.

And the 'if(!stack.peek().equals(str))' condition matches and 'f' is popped out of the queue.

stack.pop();

Continuing in the same way, all the elements are popped out of the Queue and the execution ends.

❮❮ PREV NEXT ❯❯