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

javalearner

1. //邻接矩阵实现图的广搜和深搜
   
2. import java.util.*;
   
3. public class Graph_DFS_BFS {
   
4.         private int[][] G;//邻接矩阵
   
5.         private int k;//顶点数目
   
6.         private boolean[] visited;//判断顶点是否被访问过
   
7.        
   
8.         public Graph_DFS_BFS(int k,int[][] G){
   
9.             this.k=k;
   
10.             this.G=G;
    
11.             visited = new boolean[k];
    
12.         }
    
13.         public static void main(String[] args) {
    
14.           Scanner sc = new Scanner(System.in);
    
15.           int n;
    
16.           int m, t,k;
    
17.           n = sc.nextInt();//测试次数
    
18.           while (n-->0) {
    
19.             k = sc.nextInt();//图的顶点数
    
20.             m = sc.nextInt();//图的边数
    
21.             t = sc.nextInt();//搜索的起点
    
22.             //构建邻接矩阵
    
23.             int G[][] = new int[k][k];
    
24.             for (int i = 0; i < m; i++) {
    
25.                 int u = sc.nextInt();
    
26.                 int v = sc.nextInt();
    
27.                 G[u][v] = 1;
    
28.                 G[v][u] = 1;//无向图的对称
    
29.              }
    
30.               Graph_DFS_BFS gra=new Graph_DFS_BFS(k,G);
    
31.                  // gra.bfs(t);
    
32.                   gra.dfs(t);
    
33.                    System.out.println();
    
34.                 }
    
35.         }
    

复制代码

1. 
   
2.         //广搜
   
3.         public  void bfs(int v) {
   
4.                 //队列用来保存被访问节点的分支节点
   
5.                 LinkedList< Integer> que = new LinkedList< Integer>();
   
6.                 que.add(v);
   
7.                 while (!que.isEmpty()) {
   
8.                   v = que.poll();
   
9.                  if(!visited[v]){
   
10.                   System.out.print(v+"  ");
    
11.                   visited[v] = true;
    
12.                  }
    
13.                   //将被访问节点的分支节(邻接）点加入到队列中
    
14.                   for (int i = 0; i < k; i++) {
    
15.                         if (G[v][i] == 1 && !visited[i]) {
    
16.                                 que.add(i);
    
17.                                 //visited[i] = true;
    
18.                         }
    
19.                   }
    
20.                 }
    
21.         }
    

复制代码

3、深度优先搜索

1. 遍历.直到图中所有顶点都被访问为止.
2. 
   
3.         //深搜
   
4.         public  void dfs(int v) {
   
5.           visited[v] = true;
   
6.           System.out.print(v+"  ");
   
7.           for (int i = 0; i < k; i++) {
   
8.             //递归调用搜索没有被访问过的当前节点的下一个节点
   
9.                 if (G[v][i] == 1 && !visited[i])
   
10.                   dfs(i);
    
11.           }
    
12.         }
    
13. }
    

复制代码

对上面两个图,程序运行如下:

C:java>java Graph_DFS_BFS(广搜的结果)
2
6
10
0
0 1
0 2
0 3
1 2
1 4
2 4
2 5
2 3
3 5
4 5
0 1 2 3 4 5
5
6
0
0 1
0 3
1 4
1 2
4 2
2 3
0 1 3 2 4
  C:java>java Graph_DFS_BFS(深搜索的结果)
2
6
10
0
0 1
0 2
0 3
1 2
1 4
2 4
2 5
2 3
3 5
4 5
0 1 2 3 5 4
5
6
0
0 1
0 3
1 4
1 2
4 2
2 3
0 1 2 3 4 C:java>
   
     
     
      
      

        
      

        
      
     
   

  


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