(Java) 圖形串列表示法 DFS BFS

1. /* 
2.  * 圖形串列表示法 與 DFS BFS 走訪使用 
3.  */  
4. public class DFS_BFS {  
5.  static GraphLink[] g = new GraphLink[6];  //此類別請參照 文章:圖形串列表示法
6.  static int[] run = new int[6];  
7.  public static void main(String[] args) {  
8.    
9.    int[][] am = {{1,2},{2,1},{1,5},{5,1},{2,3},{3,2},  
10.               {2,4},{4,2}, {3,4},{4,3},  
11.               {5,3},{3,5},{5,4},{4,5},  
12.              };//每個邊  
13.    int[][] am2 = {{1,2},{2,3},{2,4},{4,3}};  
14.    System.out.println("無向圖形");  
15.      for(int i = 1 ; i < 6 ; i++){  
16.       g[i] = new GraphLink();  
17.       System.out.print("頂點"+i+"=>");  
18.       for(int j = 0 ; j < 14 ; j++){  
19.        if(i == am[j][0])   
20.         g[i].Insert(am[j][1]);  
21.          }  
22.       g[i].print();  
23.      }  
24.            /* System.out.println("先身後廣 :"); 
25.             dfs(1);*/  
26.             System.out.println("\n先廣後深 :");  
27.             bfs(1);       
28.  }  
29.  public static void dfs(int vertice){  
30.   run[vertice] = 1;//代表走訪過  
31.   System.out.print(" ( "+vertice+" )  ");  
32.   while(g[vertice].frist != null){  
33.    if(run[g[vertice].frist.vertice] == 0)  
34.     dfs(g[vertice].frist.vertice);  
35.    g[vertice].frist = g[vertice].frist.next;  
36.   }  
37.  }  
38.  static int[] queue = new int[10];  
39.  static int front = -1 , rear = -1 ;  
40.  public static  void enqueue(int value){  
41.   if(rear >= 10){  
42.    System.out.println("已滿");  
43.    return ;  
44.   }  
45.   rear++ ;  
46.   queue[rear] = value ;  
47.  }  
48.  public static void bfs(int vertice){  
49.     run[vertice] = 1;//代表走訪過  
50.     enqueue(vertice);//加入佇列  
51.     System.out.print(" ( "+vertice+" )  ");  
52.     while( (vertice = dequeue()) != -1){ //取出佇列值  
53.     if(run[vertice] == 0)  
54.     System.out.print(" ( "+vertice+" )  ");  
55.     run[vertice] = 1;  
56.       
57.     while(g[vertice].frist != null){  
58.      if(run[g[vertice].frist.vertice] == 0){  
59.       enqueue(g[vertice].frist.vertice) ;  
60.      }  
61.      g[vertice].frist = g[vertice].frist.next;  
62.     }  
63.       
64.     }  
65.  }  
66.  private static int dequeue() {  
67.   if(rear == front)  
68.   return -1;  
69.   front++;  
70.   return queue[front ];  
71.  }  
72.    
73. }