以下是如何透過BFS(廣度優先搜尋)來遍歷整張圖的大致流程
CODE我還不會寫 先用純文字表示用Java實作的流程:
0. 圖本身要用Map<Integer,List<Integer>>型別的物件來表示。
圖的每個節點都需要被記錄是否被訪問,這要用Set<Integer>型別的物件來表示。
不管是樹還是圖的BFS,都以QUEUE物件作為要被訪問的節點的資料結構。
1. 選定一圖的節點,節點在這裡是以一個Integer型別之數字表示。
2. 該數字做為一開始訪問的節點,被加入queue物件內(queue.add())、
接著將其取出(queue.poll())、印出數字、並將該數字加入set物件,表示已訪問過。
3. 檢查該數字對應的list是否有元素(也就是是否有值),若有的話則用迴圈將其
添加至queue、接著一樣一一自queue取出、印出數字、再添加至set物件。
4. 從queue取出數字、印出數字、搜尋時否有連結的數字、添加至queue。
這串動作是只要queue不是空的就要重複做,
故「從queue取出數字、印出數字、搜尋時否有連結的數字、添加至queue」
必須包在while迴圈內。
5. 該迴圈執行完成,表示所有元素都被加入queue且被取出來訪問,
故BFS執行完成。
6. 所以跟該資料結構搭配的演算法,一樣是回溯法。