Showing posts with label DFS implementation using Java. Show all posts
Showing posts with label DFS implementation using Java. Show all posts

Sunday, 16 December 2012

DFS implementation using Java


import java.io.*;
class stcklist
{
  public int top;
  public int maxsize;
  public int[] stck;

  public stcklist(int size)
  {
    maxsize = size;
    stck = new int[size];
    top= -1;
  }

  public void push(int x)
  {
     stck[++top]=x;
  }

  public int pop()
  {
    int temp = stck[top];
    top--;
    return temp;
  }
  public int top()
  {
    int temp = stck[top];
    return temp;
  }
  public boolean isempty()
  {
    return(top==-1);
  }
}  

class vertex
{
 public char label;
 public boolean wasvisited;

 public vertex(char lab)
 {
   label = lab;
   wasvisited = false;
 }
}

class graph
{
  public final int MAX = 20;
  public int nverts;
  public int adj[][];
  public vertex vlist[];
  stcklist st;

  public graph()
  {
   nverts = 0;
   vlist = new vertex[MAX];
   adj = new int[MAX][MAX];
   st = new stcklist(MAX);
   for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
     adj[i][j] = 0;
  }

  public void addver(char lab)
  {
    vlist[nverts++] = new vertex(lab);
  }

  public void addedge(int start,int end)
  {
    adj[start][end] = 1;
    adj[end][start] = 1;
  }
 
  public int getadjunvis(int i)
  {
    for(int j=0;j<nverts;j++)
      if((adj[i][j]==1)&&(vlist[j].wasvisited==false))
      return j;
    return (MAX+1);  
  }

  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }

  public void drfs()
  {
    vlist[0].wasvisited = true;
    System.out.print(vlist[0].label);
    st.push(0);
    int v2;
    while(!(st.isempty()))
    {
     int v1 = st.top();
// v2=getadjunvis(v1));
     if((v2=getadjunvis(v1))!=(MAX+1))
      {
    vlist[v2].wasvisited = true;
        System.out.print(vlist[v2].label);
        st.push(v2);
      }
 else
 st.pop();
    }
  }
}

Best geography books for UPSC prelims, mains

This post is intended to clear the confusion that prevails among the aspirants over how to prepare for UPSC geography and the best books f...