Algorithm - BFS - INCLAVIC

Course

可以參考我做的課程簡報：

Breadth-First Search BFS 廣度優先搜尋

不斷找出尚未遍歷的點當作起點
- 把起點塞入 queue
- 重複以下步驟，直到 queue 裡沒有東西為止：
  1. 從 queue 中取出一點
  2. 找出與此點相鄰的點、且尚未遍歷的點，並將這些點依序塞入 queue

Example

BFS - queue

bool visited[12+5];
bool M[12+5][12+5];

queue<int> q;
for(int i = 0; i <= 12; i++){
	visited[i] = false;
}

int parent, child;
while(cin >> parent >> child){
	M[parent][child] = true;
}

for(int k = 0; k <= 12; k++){
	if(!visited[k]){
		q.push(k);
		visited[k] = true;
	}

	while(!q.empty()){
		int i = q.front();
		q.pop();

		for(int j = 0; j <= 12; j++){
			if(M[i][j] && !visited[j]){
				q.push(j);
				visited[j] = true;
			}
		}
	}
}

UVA Problem

UVA 00572 - Oil Deposits UVA 00439 - Knight Moves UVA 10189 - Minesweeper