Saturday, April 16, 2011

Depth First Search with Stack


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