上一篇博文介紹了BFS和DFS的原理，現在給出其JAVA代碼實現；

BFS就是維護一個隊列，先依次訪問起始點相鄰的節點，入隊，再訪問相鄰節點的相鄰節點，依次入隊出隊。

DFS就是利用遞歸+回溯，直到遞歸到沒有相鄰節點可以訪問了，就向上回溯。

---

BFS:

import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; /*廣度遍歷是遍歷到某個頂點，然后訪問其連接點a,b；接著訪問a的連接表， 很自然的，這種數據結構就是HashMap，以頂點為key，保存每個頂點的連接表 */ public class BFSbak {public static void main(String args[]){BFSbak bb = new BFSbak();// s頂點的鄰接表LinkedList<Character> list_s = new LinkedList<Character>();list_s.add('w');list_s.add('r');LinkedList<Character> list_w = new LinkedList<Character>();list_w.add('s');list_w.add('i');list_w.add('x');LinkedList<Character> list_r = new LinkedList<Character>();list_r.add('s');list_r.add('v');LinkedList<Character> list_x = new LinkedList<Character>();list_x.add('w');list_x.add('i');list_x.add('u');list_x.add('y');LinkedList<Character> list_v = new LinkedList<Character>();list_v.add('r');LinkedList<Character> list_i = new LinkedList<Character>();list_i.add('u');list_i.add('x');list_i.add('w');LinkedList<Character> list_u = new LinkedList<Character>();list_u.add('i');list_u.add('x');list_u.add('y');LinkedList<Character> list_y = new LinkedList<Character>();list_y.add('u');list_y.add('x');//建立鄰接表HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();//建立鄰接表的鏈表graph.put('s', list_s);graph.put('w', list_w);graph.put('r', list_r);graph.put('x', list_x);graph.put('v', list_v);graph.put('i', list_i);graph.put('y', list_y);graph.put('u', list_u);//建立節點的標識HashMapHashMap<Character, Integer> dist = new HashMap<Character, Integer>();char start = 's';bb.bfs(graph, dist, start);}/*HashMap<Character,LinkedList<Character>> graph* 這個HashMap是用于存放圖中每個node的鄰接表* 表示此映射所維護的鍵的類型為Character，此映射值的類型為LinkedList<Character>* graph 表示將映射關系存放在graph此映射中** LinkedList<Character> 表示在此Collection中保持元素類型為Character** HashMap<Character,Integer> dist* 這個HashMap 是用于存放每個node與距離頂點s的距離的映射關系* 表示此映射所維護的鍵的類型為Character* 此映射所維護的值的類型為Integer，dist表示將映射關系存放到dist此映射中*/private void bfs(HashMap<Character, LinkedList<Character>> graph,HashMap<Character, Integer> dist,char start){ //Queue<Character> 表示在此Collection中所保存的元素的類型為CharacterQueue<Character> q=new LinkedList<Character>();q.add(start);//將指定元素s插入隊列，成功時返回true，如果沒有可用空間，則返回illegalStateException/*put(start,0) start為指定值將要關聯的鍵，0為指定值將要關聯的值， 如果start與0的映射關系已存在，則返回并替換舊值0 如果 start與0的映射關系不存在，則返回null */dist.put(start, 0);int i=0;while(!q.isEmpty())//{char top=q.poll();//獲取并移除隊列的頭，返回隊列的頭，如果隊列為空，返回nulli++;//dist.get(top) 返回指定鍵top所映射的值System.out.println("The "+i+"th element:"+top+" Distance from s is:"+dist.get(top));int d=dist.get(top)+1;//得出其周邊還未被訪問的節點的距離/*graph.get(top)如果此映射包含一個滿足 (key==null ? k==null : key.equals(k)) 的從 k 鍵到 v 值的映射關系，則此方法返回 v；否則返回 null。（最多只能有一個這樣的映射關系。） for（元素變量：元素集合），如果元素集合中所有元素都已遍歷過，則結束此循環， 否則執行for循環里的程序塊 */for (Character c : graph.get(top)){// containskey(key) 如果此映射包含對于指定鍵key的映射關系，則返回trueif(!dist.containsKey(c))//如果dist中還沒有該元素說明還沒有被訪問{ /*關聯指定鍵c與指定值d，如果關聯關系已存在，則替換舊值d，返回舊值d， 如果無映射關系，則返回null*/dist.put(c, d);q.add(c); //將指定元素c插入隊列，成功時返回true，如果沒有可用空間，則返回illegalStateException}}}} }

---

DFS:

/*** 建立鏈表節點*/ class Node {int x;Node next;public Node(int x) {this.x = x;this.next = null;} } public class BinaryTree{public Node first; //左孩子public Node last; //右孩子//保存訪問過的節點值public static int run[] = new int[9];//建立二叉樹節點數組public static BinaryTree head[] = new BinaryTree[9];/*** 訪問起始某點，打上標識表示已經訪問；再訪問這個點的鄰接點，在訪問這個點的鄰接點的鄰接點。。一直遞歸下去，* 直到沒有了鄰接點就返回上層繼續此操作；每次訪問之后就打上標識表示已經訪問過；最后找到所有的節點；* @param current*/public static void dfs(int current) {run[current] = 1;System.out.print("[" + current + "]");while (head[current].first != null) {if(run[head[current].first.x] == 0) { //如果頂點尚未遍歷，就進行dfs遞歸，訪問后就是1啦！！！！dfs(head[current].first.x);}head[current].first = head[current].first.next;}}//判斷當前節點是否為空public boolean isEmpty() {return first == null;}public void print() {Node current = first;while(current != null) {System.out.print("[" + current.x + "]");current = current.next;}System.out.println();}//插入所有當前節點的所有鄰接點；public void insert(int x) {Node newNode = new Node(x);if(this.isEmpty()) {first = newNode;last = newNode;}else {last.next = newNode;last = newNode;}}public static void main(String[] args) {//這此創建不同于上次的鄰接表的創建；這次是直接根據圖然后來寫出節點對的組合，一對表示是連接在一起的鄰接點；int Data[][] = { {1,2}, {2,1}, {1,3}, {3,1}, {2,4}, {4,2},{2,5}, {5,2}, {3,6}, {6,3}, {3,7}, {7,3}, {4,5}, {5,4},{6,7}, {7,6}, {5,8}, {8,5}, {6,8}, {8,6} };int DataNum;int i,j;System.out.println("圖形的鄰接表內容為：");for(i=1;i<9;i++) {run[i] = 0;head[i] = new BinaryTree();System.out.print("頂點" + i + "=>");for (j=0;j<20;j++) {if(Data[j][0] == i) {DataNum = Data[j][1];head[i].insert(DataNum);}}head[i].print();}System.out.println("深度優先遍歷頂點：");dfs(1);System.out.println("");} }

?

?

總結

以上是生活随笔為你收集整理的图：BFS/DFS java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。