찰떡개발자 코딩

BFS 정의

BFS는 현재 위치에 인접한 모든 위치의 노드를 방문하고, 그 이웃 노드들의 또 다른 이웃 노드들을 방문하는 것은 그 다음에 진행하는 것을 의미. 큐를 이용해서 순환적 형태로 구현하는 것으로 공부해보려고 한다.

BFS 넓이 우선 탐색 (Breadth Fisrt Search)

"근처부터 확인하자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고

멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.

시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다.

2..3..4... 이런식으로 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료

* 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

* 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

구현 방법

1). Queue(큐)를 이용하여 구현

그래프 표현하기

정점의 개수, 간선의 개수, 탐색을 시작할 정점을 번호를 입력받으면서 시작한다.

정점의 개수 : 우리가 방문해야 할 노드의 개수

간선의 개수 : 노드와 연결되어있는 간선의 개수

정점의 번호 : 첫번째 시작 노드의 번호

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); // 정점의 개수
		int m = sc.nextInt(); // 간선의 개수
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호

		boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열

		LinkedList<Integer>[] adjList = new LinkedList[n + 1];//정점에 붙어있는 간선 LinkedList

		for (int i = 0; i <= n; i++) {
			adjList[i] = new LinkedList<Integer>();
		}

		// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
		// 입력으로 주어지는 간선은 양방향이다.
		// 두 정점을 서로 이어주어 간선을 만든다고 생각하자.
		for (int i = 0; i < m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			adjList[v1].add(v2);
			adjList[v2].add(v1);
		}

		for (int i = 1; i <= n; i++) {
			Collections.sort(adjList[i]); // 방문 순서를 위해 오름차순 정렬
		}

		System.out.println("BFS - 인접리스트");
		bfs_list(v, adjList, visited);
	}

	// BFS - 인접리스트
	public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
		//Queue를 통해 선입선출 방식을 채택.
		Queue<Integer> queue = new LinkedList<Integer>();
		//탐색 시작 노드 위치에 방문표시.
		visited[v] = true;
		//탐색 시작 노드를 Queue에 입력
		queue.add(v);

		while(queue.size() != 0) {
			//Queue에 쌓인 방문한 정점 삭제.
			v = queue.poll();
			System.out.println(v + "번 방문");
			
			//해당 정점에 연결된 간선을 통해 방문해야되는 정점들
			Iterator<Integer> iter = adjList[v].listIterator();
			while(iter.hasNext()) {
				int w = iter.next();
				if(!visited[w]) {
					visited[w] = true;
					queue.add(w);
				}
			}
		}
	}

Queue에서 Poll() 메서드를 이용하여 방문한 정점을 삭제하며, 반복되는 방식으로 구현.

중요 포인트

1). Queue를 사용하여 queue.size() !=0으로 방문한 정점을 삭제하고 다시 큐에 방문해야될 정점을 넣어주는부분

2). 두 정점을 이어주어 간선을 만드는 부분.

3). 방문했다는 visisted Array를 사용한 부분.

BFS 시간복잡도

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우

• 그래프가 인접 리스트로 표현된 경우 O(n+e)
• 인접 행렬로 표현된 경우 O(n^2)이다.