# Graph Traversal - BFS
###### tags: `DS` `BFS` `GRAPH` `ch6` `Adjacency Lists`

| | DFS | BFS |
| ------------------------- | ------ | ------ |
| 輔助的DS | Stack | Queue |
| 相鄰串列(Adjacency Lists) | O(n+e) | O(n+e) |
| 相鄰矩陣(Adjacency Matrix)| O(n**2) | O(n**2) |

## DS版本 (皆對無向圖) (採用Adjacenty Lists)
KeyPoint!:
1. every vertex should be push into queue.
2. every vertex should be checked whether visited yet.

BFS(v : start vertex){
    //Assume have a global array visited[1..n] of boolean
    //n = num of v
    visited[v] = true;
    Creted Queue Q;
    Enqueue(Q,v)
    while(Q != NULL){
        v = Dequeue(Q);
        foreach(vertex u adjacency v do){
            if(visited[u] == false) {
                visited[u] == true;
                Enqueue(Q,u);
            }
        }
    }
}

**Note:** BFS order並不唯一，故通常會設定值小者優先，如此會唯一。

## Algo版本 (對無向圖) (採用Adjacenty Lists)
Note: the **u.d** and **u.f** in DFS-visit is...
1. u.d == the **distance** from s to u.
2. u.pi == the **last node of u** .
3. u.color == White (haven't been vistied)
4. u.color == Gray (already visit but the adjacency vertex of u didn't finish yet)
5. u.color == Black (finished visit)

keyPoint!
1. every vertex **before visit is white!**
2. every vertex **before visit is NULL!**
3. every vertex **should be checked whether color is white before visit**, if true then visit!

//s為起點,G用Adjacency Lists表示
BFS(G, s){
    foreach(vertex v in G.V-{s} do){
        v.d = infinity;
        v.pi = NULL;
        v.color = white;
    }
    s.color = Gray;
    s.d = 0;
    s.pi = NULL//or itself
    
    Create Queue Q;
    Enqueue(Q,s);
    while(Q != NULL){
        u = Dequeue(Q);
        foreach(vertex w adjacency u do){
            if(w.color == white){
                w.pi = u;
                w.d += 1;
                w.color = Gray;
                Enqueue(Q, w);
            }           
        }
        u.color = Black;
    }
}