BFS

 

BFS 알고리즘?

모든 가중치가 1일때 최단거리를 구하는 알고리즘이다.

 

BFS를 이용해 해결할 수 있는 문제는 아래와 같은 조건을 만족해야 한다.

    1. 최소 비용 문제이어야 한다. 

    2. 간선의 가중치가 1이어야 한다.

    3. 정점과 간선의 개수가 적어야 한다. (적다는 것은 문제의 조건에 맞춰서 해결할 수 있다는 것을 의미한다.)

 

간선의 가중치가 문제에서 구하라고하는 최소 비용과 의미가 일치해야 한다.

즉 거리의 최소값을 구하는 문제라면 가중치는 거리를 의미해야 하고, 시간의 최소값을 구하는 문제라면 가중치는 시간을 의미해야 한다.