[DataStructure]BFS(廣度優先)

BFS主要邏輯

• 從樹根開始當母節點
• 把子節點塞進queue
• 把一開始的母節點紀錄起來
• 從queue拉出子節點繼續

當然如果是做子圖的話還需要判斷該節點是否已經走訪過了

範例：
Java簡易二元樹BFS走訪

import java.util.LinkedList;
import java.util.Iterator;
public class bfs {
    public static void main(String [] argv) {
        //值與index相同的二元樹
        int [] arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        LinkedList<Integer> queue = new LinkedList<Integer>();
        LinkedList<Integer> result = new LinkedList<Integer>();
        int length = arr.length;
        //從樹根開始
        queue.add(arr[1]);
        while (!queue.isEmpty()) {
            int parent_node = queue.getFirst();
            //樹根的子節點寫入queue
            for (int i = 0; i < 2; i++) {
                if (parent_node * 2 + i < length) {
                    queue.add(arr[parent_node * 2 + i]);
                }
            }

            //將父節點移進result
            result.add(parent_node);
            queue.removeFirst();
        }

        //顯示
        Iterator it = result.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}