37. DEPTH FIRST SEARCH IN JAVA

Code:

import java.util.Scanner;

class Stack

{

    int stk[]=new int[10];

    int top;

    Stack()

    {

        top=-1;

    }

    void Push (int item)

    {

        if (top==9)

            System.out.println("Stack overflow");

        else

        stk[++top]=item;

    }

    boolean isEmpty()

    {

    if (top<0)

        return true;

    else

        return false;

    }

    int Pop()

    {

        if (isEmpty())

        {

            System.out.println("Stack underflow");

            return 0;

        }

        else

            return (stk[top--]);

    }

    void stackTop()

    {

        if(isEmpty())

            System.out.println("Stack underflow ");

        else

            System.out.println("Stack top is "+(stk[top]));

    }

    void Display()

    {

        System.out.println("Stack-->");

        for(int i=0;i<=top;i++)

            System.out.println(stk[i]);

    }

}

class Graph

{

    int MAXSIZE=51;

    int adj[][]=new int[MAXSIZE][MAXSIZE];

    int visited[]=new int [MAXSIZE];

    Stack s=new Stack();

    void createGraph()

    {

        int n,i,j,parent,adj_parent,initial_node;

        int ans=0,ans1=0;

        System.out.print("\nEnter total number elements in a Undirected Graph :");

        n=getNumber();

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                adj[i][j]=0;

        for (int c=1;c<=50;c++)

            visited[c]=0;

        System.out.println("\nEnter graph structure for BFS  ");

        do

        {

            System.out.print("\nEnter parent node :");

            parent=getNumber();

            do

            {

                System.out.print("\nEnter adjacent node for node "+parent+ " : ");

                adj_parent=getNumber();

                adj[parent][adj_parent]=1;

                adj[adj_parent][parent]=1;

                System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?");

                ans1= getNumber();

            } while (ans1==1);

        System.out.print("\nContinue to add graph node?");

        ans= getNumber();

        }while (ans ==1);

        System.out.print("\nAdjacency matrix for your graph is :\n");

        for (i=1;i<=n;i++)

        {

            for (j=1;j<=n;j++)

            System.out.print(" "+adj[i][j]);

            System.out.print("\n");

        }

        System.out.println("\nYour Undirected Graph is :");

        for(i=1;i<=n;i++)

        {

            System.out.print("\nVertex "+i+"is connected to : ");

            for (j=1;j<=n;j++)

            {

                if (adj[i][j]==1)

                    System.out.print(" "+j);

            }

        }

        System.out.println("\nEnter the initial node for BFS traversal:");

        initial_node=getNumber();

        DFS (initial_node, n);

    }

    void DFS (int initial_node,int n)

    {

        int u,i;

        s.top = -1;

        s.Push(initial_node);

        System.out.println("\nDFS traversal for given graph is : ");

        while(!s.isEmpty())

        {

            u=s.Pop();

            if(visited[u]==0)

            {

                System.out.print("\n"+u);

                visited[u]=1;

            }

            for (i=1;i<=n;i++)

            {

                if((adj[u][i]==1) && (visited[i]==0))

                {

                    s.Push(u);

                    visited[i]=1;

                    System.out.print(" "+i);

                    u = i;

                }

            }

        }

    }

    int getNumber()

    {

        Scanner in = new Scanner(System.in);

        int ne=0;

        ne=in.nextInt();

        return ne;

    }

}

class DFS

{

    public static void main(String args[])

    {

        Graph g=new Graph();

        g.createGraph();

    }

}

Need the code??

Download Link = https://www.dropbox.com/s/rnx8eou3rvfhnwf/dfs.docx