本文以實例形式講述了基于Java的圖的廣度優先遍歷算法實現方法，具體方法如下：

用鄰接矩陣存儲圖方法：

1.確定圖的頂點個數和邊的個數

2.輸入頂點信息存儲在一維數組vertex中

3.初始化鄰接矩陣；

4.依次輸入每條邊存儲在鄰接矩陣arc中

輸入邊依附的兩個頂點的序號i,j；
將鄰接矩陣的第i行第j列的元素值置為1；
將鄰接矩陣的第j行第i列的元素值置為1；

廣度優先遍歷實現：

1.初始化隊列Q
2.訪問頂點v；visited[v]=1;頂點v入隊Q;
3.while(隊列Q非空)

v=隊列Q的隊頭元素出隊；
w=頂點v的第一個鄰接點
while(w存在)

如果w未被訪問，則訪問頂點w;visited[w]=1;頂點w入隊列Q

w=頂點v的下一個鄰接點

實現代碼如下：

1. package com.teradata.lsw.sort; 
2.   
3. import java.util.ArrayList; 
4. import java.util.LinkedList; 
5. import java.util.List; 
6. import java.util.Queue; 
7.   
8. public class BFS { 
9.   
10. // 存儲節點信息 
11. private Object[] vertices; 
12. // 存儲邊的信息數組 
13. private int[][] arcs; 
14. // 邊的條數 
15. private int vexnum; 
16. // 記錄第i個節點是否被訪問過 
17. private boolean[] visited; 
18. //構建一個臨時鏈表存已經遍歷過的節點 
19. private List<Object> temp = new ArrayList<Object>(); 
20.   
21. /** 
22. * @param args 
23. * 
24. * @author TD_LSW 
25. */ 
26. public static void main(String[] args) { 
27. // TODO Auto-generated method stub 
28.   
29. BFS g = new BFS(8); 
30. Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; 
31. g.addVertex(vertices); 
32. g.addEdge(0, 1); 
33. g.addEdge(0, 2); 
34. g.addEdge(1, 3); 
35. g.addEdge(1, 4); 
36. g.addEdge(3, 5); 
37. g.addEdge(4, 5); 
38. g.addEdge(2, 6); 
39. g.addEdge(2, 7); 
40.   
41. System.out.println("圖的廣度優先遍歷："); 
42. g.bfs(); 
43. } 
44.   
45. // 廣度優先遍歷實現 
46. private void bfs() { 
47. // TODO Auto-generated method stub 
48. for (int i = 0; i < vexnum; i++) { 
49. visited[i] = false; 
50. } 
51. Queue<Integer> q = new LinkedList<Integer>(); 
52. for (int i = 0; i < vexnum; i++) { 
53. if (!visited[i]) { 
54. visited[i] = true; 
55. visit(i); 
56. q.add(i); 
57. while (!q.isEmpty()) { 
58. int j = (Integer) q.remove().intValue(); 
59. //判斷如果全部遍歷完了就不需要循環了 
60. if (temp.size() == vexnum) { 
61. q.removeAll(q); 
62. return; 
63. } 
64. for (int k = this.firstAdjVex(j); k >= 0; k = this 
65. .nextAdjVex(j, k)) { 
66. if (!visited[k]) { 
67. q.add(k); 
68. visited[k] = true; 
69. visit(k); 
70. } 
71. } 
72. } 
73. } 
74. } 
75.   
76. } 
77.   
78. // 查找下一個節點 
79. public int firstAdjVex(int i) { 
80. for (int j = 0; j < vexnum; j++) { 
81. if (arcs[i][j] > 0) 
82. return j; 
83. } 
84. return -1; 
85. } 
86.   
87. public int nextAdjVex(int i, int k) { 
88. for (int j = k + 1; j < vexnum; j++) { 
89. if (arcs[i][j] > 0) 
90. return j; 
91. } 
92. return -1; 
93. } 
94.   
95. // 初始化圖的邊 
96. private void addEdge(int i, int j) { 
97. // TODO Auto-generated method stub 
98. if (i == j) 
99. return; 
100. arcs[i][j] = 1; 
101. arcs[j][i] = 1; 
102.   
103. } 
104.   
105. // 初始化圖的節點 
106. private void addVertex(Object[] object) { 
107. // TODO Auto-generated method stub 
108. this.vertices = object; 
109. } 
110.   
111. // 圖的初始化 
112. public BFS(int n) { 
113. // TODO Auto-generated constructor stub 
114. vexnum = n; 
115. vertices = new Object[n]; 
116. arcs = new int[n][n]; 
117. visited = new boolean[n]; 
118. for (int i = 0; i < vexnum; i++) { 
119. for (int j = 0; j < vexnum; j++) { 
120. arcs[i][j] = 0; 
121. } 
122. } 
123. } 
124.   
125. private void visit(int i) { 
126. // TODO Auto-generated method stub 
127. temp.add(vertices[i]); 
128. System.out.print(vertices[i] + " "); 
129. } 
130.   
131. }