[ 그래프 ] BFS 연습하기 JAVA

문제

그림과 같은 그래프에 대하여 정점의 개수 N, 연결선의 개수 M이 주어지고

그래프에 대한 연결 정보가 주어질 때, 시작 정점 1에서 BFS 방문 경로를 출력하시오.

그래프 정보

 

풀이

BFS를 연습하는 가장 기본적인 문제입니다.

시작 정점 1을 bfs() 함수 실행할 때 입력해준 뒤, Queue를 이용하여

다음 정점과 연결되어 있고 ( map[x][i] == 1 ), 아직 방문하지 않은 정점이 있다면 ( visited[i] == false )

큐에 해당 정점을 넣어주고, 더 이상 방문할 정점이 존재하지 않는다면 종료해주었습니다.

연결되어 있는 모든 정점을 너비 우선 탐색(Breadth First Search)으로 방문하는 문제입니다.

방문한 정점에 대하여 중복 방문하는 경우를 방지하기 위해 visited 배열을 이용하여 방문할 경우 true 값을 이용해

중복처리를 해주었습니다.

 

결과 값을 보면 시작정점 1 에서부터 

거리가 1인 2번 정점과 3번 정점을 먼저 방문한 뒤,

거리가 2인 4번 정점과 5번, 7번 정점을 방문하고

마지막으로 거리가 3인 6번 정점을 방문하는 것을 볼 수 있습니다.

 

코드

실행 결과