基於Java完成的圖的廣度優先遍歷算法。本站提示廣大學習愛好者:(基於Java完成的圖的廣度優先遍歷算法)文章只能為提供參考,不一定能成為您想要的結果。以下是基於Java完成的圖的廣度優先遍歷算法正文
本文以實例情勢講述了基於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的下一個鄰接點
完成代碼以下:
package com.teradata.lsw.sort; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class BFS { // 存儲節點信息 private Object[] vertices; // 存儲邊的信息數組 private int[][] arcs; // 邊的條數 private int vexnum; // 記載第i個節點能否被拜訪過 private boolean[] visited; //構建一個暫時鏈表存曾經遍歷過的節點 private List<Object> temp = new ArrayList<Object>(); /** * @param args * * @author TD_LSW */ public static void main(String[] args) { // TODO Auto-generated method stub BFS g = new BFS(8); Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; g.addVertex(vertices); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(2, 6); g.addEdge(2, 7); System.out.println("圖的廣度優先遍歷:"); g.bfs(); } // 廣度優先遍歷完成 private void bfs() { // TODO Auto-generated method stub for (int i = 0; i < vexnum; i++) { visited[i] = false; } Queue<Integer> q = new LinkedList<Integer>(); for (int i = 0; i < vexnum; i++) { if (!visited[i]) { visited[i] = true; visit(i); q.add(i); while (!q.isEmpty()) { int j = (Integer) q.remove().intValue(); //斷定假如全體遍歷完了就不須要輪回了 if (temp.size() == vexnum) { q.removeAll(q); return; } for (int k = this.firstAdjVex(j); k >= 0; k = this .nextAdjVex(j, k)) { if (!visited[k]) { q.add(k); visited[k] = true; visit(k); } } } } } } // 查找下一個節點 public int firstAdjVex(int i) { for (int j = 0; j < vexnum; j++) { if (arcs[i][j] > 0) return j; } return -1; } public int nextAdjVex(int i, int k) { for (int j = k + 1; j < vexnum; j++) { if (arcs[i][j] > 0) return j; } return -1; } // 初始化圖的邊 private void addEdge(int i, int j) { // TODO Auto-generated method stub if (i == j) return; arcs[i][j] = 1; arcs[j][i] = 1; } // 初始化圖的節點 private void addVertex(Object[] object) { // TODO Auto-generated method stub this.vertices = object; } // 圖的初始化 public BFS(int n) { // TODO Auto-generated constructor stub vexnum = n; vertices = new Object[n]; arcs = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { arcs[i][j] = 0; } } } private void visit(int i) { // TODO Auto-generated method stub temp.add(vertices[i]); System.out.print(vertices[i] + " "); } }