dfs.java

采用stack算法的DFS搜索

    //G5BADS Maze Assignment
    //Huang Li Wen
    //Nov 12th, 2004
	
	import java.util.Random;
	import java.util.*;
	import java.util.Hashtable;
	import javax.swing.*;
	import java.awt.*;
	
	public class DFS
	{  
	      private static Hashtable ht=new Hashtable();
	      //create a hashtable in order to set the relationship between
	      //the coordinate of the letter on the GUI and the vertex of the maze
	      
	       
	      public DFS() 
	      {
	      	//Predefine the hash table where the key is the vertex of the maze 
	      	//and the value is the coordinate of the letter 
	      	//which we need to draw to show the path of running dfs
	      	
	         ht.put("A",new Coordinate(54, 131));
	         ht.put("B",new Coordinate(154,131)); 
	         ht.put("C",new Coordinate(379,131));
	         ht.put("D",new Coordinate(479,131));
	         ht.put("E",new Coordinate(154,181));
	         ht.put("F",new Coordinate(154,281));
	         ht.put("G",new Coordinate(304,281));
	         ht.put("H",new Coordinate(154,381));
	         ht.put("I",new Coordinate(154,431));
	         ht.put("J",new Coordinate(304,381)); 
	         ht.put("K",new Coordinate(304,431));
	         ht.put("L",new Coordinate(429,381));
	         ht.put("M",new Coordinate(429,256));
	         ht.put("N",new Coordinate(429,431));
	         ht.put("O",new Coordinate(504,381));
	   	  }
	
	      public void runDFS()
	     {
	         Graph theGraph = new Graph();
	         
	         theGraph.addVertex("A");
	         theGraph.addVertex("B");
	         theGraph.addVertex("C");
	         theGraph.addVertex("D");
	         theGraph.addVertex("E");
	         theGraph.addVertex("F");
	         theGraph.addVertex("G");
	         theGraph.addVertex("H");
	         theGraph.addVertex("I");
	         theGraph.addVertex("J");
	         theGraph.addVertex("K");
	         theGraph.addVertex("L");
	         theGraph.addVertex("M");
	         theGraph.addVertex("N");
	         theGraph.addVertex("O");
	 
	         theGraph.addEdge(0,1);
	         theGraph.addEdge(1,2);
	         theGraph.addEdge(1,4);
	         theGraph.addEdge(2,3);
	         theGraph.addEdge(2,6);
	         theGraph.addEdge(4,5);
	         theGraph.addEdge(4,6);
	         theGraph.addEdge(5,6);
	         theGraph.addEdge(5,7);
	         theGraph.addEdge(7,8);
	         theGraph.addEdge(7,9);
	         theGraph.addEdge(9,10);
	         theGraph.addEdge(9,11);
	         theGraph.addEdge(11,12);
	         theGraph.addEdge(11,13);
	         theGraph.addEdge(11,14);     
	
	
	         
	         theGraph.dfs();  //call dfs method
	     } 
 
	      public static Hashtable get_Hashtable()
	      {
	    	return ht;
	      }
	   
	}
	
	
	
	class Graph
	{
	   private final int vertices = 20;  //set the max number of the vertices
	   private Vertex verticesList[];    
	   private int adjMatrix[][];       // adjacency matrix
	   private int nVertices;              // current number of vertices
	   private Stack1 stack;
	   private Thread th;              //create thread for delay of the DFS      
	   Vector tempv;       
	   private static Vector vect=new Vector();
	   Random rand; 

 
	   public Graph()       //constructor
	   {  
	      verticesList = new Vertex[vertices];
	      adjMatrix = new int [vertices][vertices];
	      nVertices = 0;
	      
	      for (int i=0; i<vertices; i++)
	         for (int j=0; j<vertices; j++)
	            adjMatrix[i][j] = 0;
	            
	      stack = new Stack1();
	      Thread th = new Thread();
		  th.start();	     	  
	   }
	 
	
	   public void addVertex (String label)
	   {
	      verticesList[nVertices++]= new Vertex(label);
	   }
	
	   public void addEdge (int start, int end)
	   {
	      adjMatrix[start][end] = 1;
	      adjMatrix[end][start] = 1;
	   }
	  
	  
	   public void dfs()
	   {  
	      verticesList[0].wasVisited = true;  //set the first vertices is visited
	      stack.push(0);
	      vect.add("A");
	      
	      while(!stack.isEmpty())
	      {  
	         
	         int n = RamGetAdjUnvisitedVertex(stack.peek());
	         //call the method of getting the adjacent vertex randomly
	         
	         
	         if (n==-1)
	           stack.pop();
	         //when there is no unvisited adjacent vertex 
	         //pop the vertex out of the stack
	         
	         
	         else
	         {
	           verticesList[n].wasVisited = true;//mark the vertex to be visited
	           vect.add(verticesList[n].verticesLabel);//store the path 
	           stack.push(n);
	           
	           if (verticesList[14].wasVisited == true)
	           {
	             while(!stack.isEmpty())
	                stack.pop();
	           }//empty the stack when reach the goal
	         }         
	      }
	      
	      for (int j=0; j<nVertices; j++)
	        verticesList[j].wasVisited = false;  
	   }
	   
	   
	   public int RamGetAdjUnvisitedVertex(int n)
	   {
	   	  tempv = new Vector();
	   	  Random rand = new Random();
	 	  
	      for (int j=0; j<nVertices; j++)
	      {
	         if (adjMatrix[n][j] == 1 && verticesList[j].wasVisited == false)
	         {
	            tempv.add(j);   
	         //store all the unvisited and adjacent vertices of the current one               
	         }       
	      } 
	      
	      
	       
	      if (tempv.size() >= 1)
	      { 
	          int m = rand.nextInt(tempv.size());
	          String a = (tempv.elementAt(m)).toString();
	          int j = Integer.parseInt(a);
	          return j;
	      }//get a random unvisited and adjacent vertex  
	      
	      
	      
	       
	      else
	          return -1; 
	         //when there is no unvisited and adjacent vertex
	   }
	   
	   
	   public static Vector get_Vector()
	   {
	   	return vect;
	   }
	   //this method will be called in the actionPerformed 
	   //method of the start button which returns the path
	   
	
	}
	
	
	
	
	class Vertex
	{
	   public String verticesLabel;
	   public boolean wasVisited;
	
	   public Vertex (String label)
	   {
	     verticesLabel = label;
	     wasVisited = false;
	   }
	}
	
	
	
	
	class Stack1
	{
	   private final int size = 20;
	   private int[] st;
	   private int top;
	
	   public Stack1()
	   {
	     st = new int[size];
	     top = -1;
	   }
	 
	   public void push(int i)
	   {
	   	 st[++top] = i;
	   }
	
	   public int pop()
	   {
	   	 return st[top--];
	   }
	
	   public int peek()
	   {
	   	 return st[top];
	   }
	
	   public boolean isEmpty()
	   {
	   	 return (top == -1);
	   }
	
	}
	
	
	class Coordinate
	{
	   private int x, y;
	   
	   public Coordinate(){
	   }
	   
	   public Coordinate(int x, int y)
	   {
	     this.x = x;
	     this.y = y;
	   }
	
	   public void setX(int x)
	   {
	   }
	   
	   public void setY(int y)
	   {
	   }
	   
	   public int getX()
	   {
	   	return x;
	   }
	   
	   public int getY()
	   {
	   	return y;
	   }
	}