너비 우선 탐색 BFS

bool BFS(int cost)
{
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int currNode = q.front();	//현재 너비에 있는 것을 순차적으로 검색
		q.pop();	//검색한 곳은 삭제

		if (currNode == finish) return true;

		for (int i = 0; i < nodes[currNode].size(); i++)
		{
			int nextNode = nodes[currNode][i].first;
			int weight = nodes[currNode][i].second;

			if (!visited[nextNode] && cost <= weight)	//방문한 곳이 아니고 cost가 가중치보다 적을때
			{
				visited[nextNode] = true;
				q.push(nextNode);	//다음 너비(현재 for문 돌고있는)에 있는 노드들을 저장
			}
		}
	}

	return false;
}

 

BFS는  단계별로 순회한다.

현재 노드가 가지고 있는 값을 다 방문하고 현재 노드의 다음 단계에 있는 노드에 들어간다.

그 뒤에는 그 들어온 단계에 있는 노드가 가지고 있는 다음 노드들을 다 방문하는 순서이다.

 

1 - 2 - 3

l    l    l

4   5 - 6    으로 연결 되어있다고 가정하에

 

1 -> 2, 1 -> 4

 

2 -> 3, 2 -> 5

 

3 -> 6, 5 -> 6 순서이다. 하지만 5 -> 6은 간 곳이기에 가지않는다.

 

 

큐의 상황은

 

1 -> X -> 2, 4 -> 4 -> 4, 3, 5 -> 3, 5 -> 5 -> 5, 6 -> 6 -> X