深度优先搜索学习五例之二（JAVA）

继续“深度优先搜索学习五例之一 ”中的第一例子:http://128kj.iteye.com/blog/1701628

例:写出数字1,2,3,4,5的所有全排列（深搜用栈实现,上文中是用递归）

import java.util.Stack;
public class Permutation{
  private int  M=5;
  

   //访问标记, visited[i]=true表示顶点i已访问
   private boolean visited[];

   public Permutation(){
      visited=new boolean[54322];//这个状态数组如何优化啊?
   }

  private void DFS(){
   visited[0] = true;//从顶点0开始访问
   Stack<Integer> s=new Stack<Integer>();
   System.out.print("");
   s.push(0);
   while(!s.empty()){
    int top = s.peek();//查看栈顶元素
    int i=0;
   for(i = 1; i <= M; ++i){
    if(find(top,i)) continue;//找top的邻接点
    int no=top*10+i;
    if(!visited[no])
    {
     visited[no] = true;
     s.push(no);//进栈
     if(no>Math.pow(10,M-1))
     System.out.print(no+" ");
     break;
    }
   }
   if( i == M + 1){
    s.pop();//从栈中删除
   }
  }
}
 
  private boolean find(int n,int k){
    boolean result=false;
    while(n>0){
      if(n%10==k){
        result=true;
        break;
       }else 
         n=n/10;
     }
    return result;
   }

 public static void main(String args[]){ 
   long start=System.currentTimeMillis();
   new Permutation().DFS();
   long end=System.currentTimeMillis(); 
   System.out.println();
   System.out.println("程序运行时间： "+(end-start)+"ms");
  }
 }

运行:
D:\java>java   Permutation
12345 12354 12435 12453 12534 12543 13245 13254 13425 13452 13524 13542 14235 14253 14325 14352 14523 14532 15234 15243 15324 15342 15423 15432 21345 21354 21435 21453 21534 21543 23145 23154 23415 23451 23514 23541 24135 24153 24315 24351 24513 24531 25134 25143 25314 25341 25413 25431 31245 31254 31425 31452 31524 31542 32145 32154 32415 32451 32514 32541 34125 34152 34215 34251 34512 34521
35124 35142 35214 35241 35412 35421 41235 41253 41325 41352 41523 41532 42135 42153 42315 42351 42513 42531 43125 43152 43215 43251 43512 43521 45123 45132 45213 45231 45312 45321 51234 51243 51324 51342 51423 51432 52134 52143 52314 52341 52413 52431 53124 53142 53214 53241 53412 53421 54123 54132 54213 54231 54312 54321

程序运行时间： 31ms

我测试过，这个运行时间比“深度优先搜索学习五例之一”中用递归实现的明显要快一倍以上，但这个程序也有一个明显的缺点，就是状态数组开的很大，列位看官，有好的表示状态的方法,或有对本程序有更好的改进请附后,不胜感激!!!

评论

1 楼 casy2008 2012-10-20  

你cpu比较慢，我是3ms