Go语言视频零基础入门到精通

javalearner

深度优先搜索输出数字全排列(递归和栈分别实现)

1. 一、深度优先算法求数字的全排列,递归实现
   
2. import java.util.Scanner;
   
3. public class PaiLie{
   
4. int n;
   
5. boolean u[]; //u[i]标识数字i是否被使用过
   
6. int ans[]; //ans排列的结果
   
7. 
   
8. public PaiLie(int n){
   
9.    this.n=n;
   
10.    u=new  boolean[n+1];
    
11.    ans=new int[n+1];
    
12. }
    
13.    
    
14. private void print(){
    
15.     for (int i=0 ;i< n ;++i)
    
16.       System.out.print(ans[i]+" ");
    
17.    System.out.println();
    
18. }
    
19.   //递归实现深度优先搜索  
    
20.   void dfs(int d){
    
21.     if (d == n) {
    
22.         print();
    
23.         return;
    
24.     }   
    
25.     for (int i=1 ; i<=n; ++i)//当前顶点的所有可能邻接点
    
26.         if (!u[i]){//是邻接点
    
27.             ans[d] = i;
    
28.             u[i] = true;
    
29.             dfs(d+1);
    
30.             u[i] = false; //恢复现场
    
31.         }   
    
32. }   
    
33.     public static void main(String args[]){
    
34.       Scanner in=new Scanner(System.in);
    
35.       int n=in.nextInt();
    
36.       PaiLie p=new PaiLie(n);
    
37.       p.dfs(0);
    
38.   }
    
39. }   

复制代码

运行：
4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

二、深度优先算法求数字的全排列,栈实现

1. import java.util.Stack;
   
2. public class Permutation{
   
3.   private int  M=5;
   
4.   
   
5.    //访问标记, visited[i]=true表示顶点i已访问
   
6.    private boolean visited[];
   
7.    public Permutation(){
   
8.       visited=new boolean[54322];
   
9.    }
   
10.   private void DFS(){
    
11.    visited[0] = true;//从顶点0开始访问
    
12.    Stack< Integer> s=new Stack< Integer>();
    
13.    System.out.print("");
    
14.    s.push(0);
    
15.    while(!s.empty()){
    
16.     int top = s.peek();//查看栈顶元素
    
17.     int i=0;
    
18.    for(i = 1; i <= M; ++i){
    
19.     if(find(top,i)) continue;//找top的邻接点
    
20.     int no=top*10+i;
    
21.     if(!visited[no])
    
22.     {
    
23.      visited[no] = true;
    
24.      s.push(no);//进栈
    
25.      if(no>Math.pow(10,M-1))
    
26.      System.out.print(no+" ");
    
27.      break;
    
28.     }
    
29.    }
    
30.    if( i == M + 1){
    
31.     s.pop();//从栈中删除
    
32.    }
    
33.   }
    
34. }
    
35. 
    
36.   private boolean find(int n,int k){
    
37.     boolean result=false;
    
38.     while(n>0){
    
39.       if(n%10==k){
    
40.         result=true;
    
41.         break;
    
42.        }else
    
43.          n=n/10;
    
44.      }
    
45.     return result;
    
46.    }
    
47. public static void main(String args[]){
    
48.    long start=System.currentTimeMillis();
    
49.    new Permutation().DFS();
    
50.    long end=System.currentTimeMillis();
    
51.    System.out.println();
    
52.    System.out.println("程序运行时间： "+(end-start)+"ms");
    
53.   }
    
54. }
    

复制代码

运行: 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 程序运行时间： 27ms
  
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/5/001025000.zip