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

javalearner

深度优先搜索(栈实现)框架流程:

实例:

1. import java.util.Stack;
   
2. public class DfsStack{
   
3.   private int  M= 8;//图有八个顶点,如下所示
   
4. //图及图的邻接矩阵表示
   
5. //1------5
   
6. //|      |
   
7. //2--4---6----8
   
8. //|      |   
   
9. //3------7
   
10.   private int matrix[][] ={
    
11.     {0, 1, 0, 0, 1, 0, 0, 0},
    
12.     {1, 0, 1, 1, 0, 0, 0, 0},
    
13.     {0, 1, 0, 0, 0, 0, 1, 0},
    
14.     {0, 1, 0, 0, 1, 1, 0, 0},
    
15.     {1, 0, 0, 1, 0, 0, 0, 0},
    
16.     {0, 0, 0, 1, 0, 0, 1, 1},
    
17.     {0, 0, 1, 0, 0, 1, 0, 0},
    
18.     {0, 0, 0, 0, 0, 1, 0, 0}
    
19.   };
    
20.    //访问标记, visited[i]=true表示顶点i已访问
    
21.    private boolean visited[];
    
22.    public DfsStack(){
    
23.       visited=new boolean[M+1];
    
24.    }
    
25.   private void GT_DFS(){
    
26.    visited[1] = true;//从顶点1开始访问
    
27.    Stack< Integer> s=new Stack< Integer>();
    
28.    System.out.print("1 ");
    
29.    s.push(1);
    
30.    while(!s.empty()){
    
31.     int top = s.peek();
    
32.     int i=0;
    
33.    for(i = 1; i <= M; ++i){
    
34.     if(!visited[i] && matrix[top - 1][i - 1 ] == 1)
    
35.     {
    
36.      visited[i] = true;
    
37.      s.push(i);
    
38.      System.out.print(i+" ");
    
39.      break;
    
40.     }
    
41.    }
    
42.    if( i == M + 1){
    
43.     s.pop();
    
44.    }
    
45.   }
    
46. }
    
47. public static void main(String args[]){
    
48.    new DfsStack().GT_DFS();
    
49.   }
    
50. }
    

复制代码

运行:
D:java>java DfsStack
1 2 3 7 6 4 5 8
  


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