BFS

BFS

BFS(Breadth-First Search)는 루트 노드 또는 임의 노드에서 시작해서 가까운 거리에 있는 노드부터 먼저 탐색하는 완전 탐색 방법의 하나이다.

 

BFS의 특징

• 선입선출의 자료구조인 큐를 통해 구현된다.
• 그래프에 대한 BFS를 구현할 경우 어떤 정점을 방문했는 지 여부를 반드시 검사해야 무한 루프를 방지할 수 있다.

 

시간 복잡도

그래프의 구현 방법에 따라 시간 복잡도에 차이가 있다. N은 정점의 수, E는 간선의 수이다.

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

 

BFS를 사용하기 좋은 상황

• 그래프의 모든 정점을 방문하는 것이 목적인 경우
• 두 정점간의 최단 거리와 관련된 문제를 해결하는 것이 목적인 경우

 

BFS의 그래프 탐색 과정

• 시작 정점을 방문한 후, 깊이가 작은 정점들에서부터 큰 정점들까지 차례로 방문한다.
• 각 정점을 방문할 때는 방문 여부 체크를 한다.

 

BFS 구현

인접 행렬과 인접 리스트에 대해 BFS를 구현하였다.

 

인접 행렬 BFS

public class AdjMatrix_bfs {

	private int[][] adjMatrix;

	public AdjMatrix_bfs(int size) {
		if (size <= 0) {
			System.out.println("그래프는 정점이 1개 이상이어야 합니다.");
			return;
		}

		adjMatrix = new int[size + 1][size + 1]; // vertex의 인덱스를 1부터 시작하기 위함.
	}

	// 무향 간선 - 가중치 X
	public void insertBiDir(int vertex1, int vertex2) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = 1;
		adjMatrix[vertex2][vertex1] = 1;
	}

	// 무향 간선 - 가중치 O
	public void insertBiDir(int vertex1, int vertex2, int weight) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = weight;
		adjMatrix[vertex2][vertex1] = weight;
	}

	// 방향 간선 - 가중치 X
	public void insertSingleDir(int vertex1, int vertex2) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = 1;
	}

	// 방향 간선 - 가중치 O
	public void insertSingleDir(int vertex1, int vertex2, int weight) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = weight;
	}

	public void bfs(int index) {
		if (valid(index, index)) {
			return;
		}

		// 방문 여부 체크를 위한 배열
		boolean[] visited = new boolean[adjMatrix.length];
		Queue<Integer> queue = new LinkedList<>();

		visited[index] = true;
		queue.add(index);

		while (queue.size() != 0) {
			// 방문한 정점을 큐에서 추출
			index = queue.poll();
			System.out.print(index + " ");

			// 모든 정점 중 방문한 정점과 인접한 정점을 확인한다.
			int[] matrix = adjMatrix[index];
			for (int i = 1; i < matrix.length; i++) {
				// 인접 정점 중 아직 방문하지 않은 정점이면 방문한 것으로 표시하고 큐에 삽입
				if (matrix[i] != 0 && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}

	private boolean valid(int vertex1, int vertex2) {
		if (adjMatrix.length <= 1) {
			return true;
		}

		if (vertex1 < 1 || vertex1 >= adjMatrix.length || vertex2 < 1 || vertex2 >= adjMatrix.length) {
			return true;
		}

		return false;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();

		for (int i = 1; i < adjMatrix.length; i++) {
			for (int j = 1; j < adjMatrix[i].length; j++) {
				sb.append(adjMatrix[i][j]).append(" ");
			}
			sb.append("\n");
		}

		return sb.toString();
	}
}

 

인접 리스트 BFS

public class Edge {
	private int destination;
	private int weight;

	public Edge(int destination, int weight) {
		this.destination = destination;
		this.weight = weight;
	}

	public Edge(int destination) {
		this.destination = destination;
		this.weight = 1;
	}

	public int getDestination() {
		return destination;
	}

	public int getWeight() {
		return weight;
	}
}


public class AdjList_bfs<T> {
	private int size;
	private List<List<Edge>> adjList = new ArrayList<>(); // 정점들의 목록
	private List<T> dataList = new ArrayList<>(); // 정점들의 데이터를 저장한다.

	// 정점 추가
	public void addVertex(T data) {
		// 인덱스를 1부터 시작하기 위해 첫 번쨰 정점 추가 전에 의미없는 정점을 추가.
		if (size == 0) {
			adjList.add(new ArrayList<>());
			dataList.add(null);
			size++;
		}

		adjList.add(new ArrayList<>()); // 정점들의 목록을 추가한다.
		dataList.add(data); // 정점들의 데이터를 저장한다. 동일한 정점에 대한 adjList와 dataList의 인덱스는 동일하다.
		size++; // 정점 개수 증가
	}

	public void bfs(int index) {
		if (valid(index)) {
			return;
		}

		// 방문 여부 체크를 위한 배열
		boolean[] visited = new boolean[size];
		Queue<Integer> queue = new LinkedList<>();

		visited[index] = true;
		queue.add(index);

		while (queue.size() != 0) {
			// 방문한 정점을 큐에서 추출
			index = queue.poll();
			System.out.print(index + " ");

			// 방문한 정점의 인접 정점을 가져오고 순회한다.
			ListIterator<Edge> listIterator = adjList.get(index).listIterator();
			while (listIterator.hasNext()) {
				// 인접한 정점
				int n = listIterator.next().getDestination();

				// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입
				if (!visited[n]) {
					visited[n] = true;
					queue.add(n);
				}
			}
		}
	}

	// 간선을 추가한다 - 가중치 지정 O
	public void addEdge(int source, int destination, int weight) {
		if (valid(source) || valid(destination)) {
			return;
		}

		adjList.get(source).add(new Edge(destination, weight));
	}

	// 간선을 추가한다 - 가중치 지정 X
	public void addEdge(int source, int destination) {
		if (valid(source) || valid(destination)) {
			return;
		}

		adjList.get(source).add(new Edge(destination));
	}

	// 주어진 인덱스에 해당하는 정점에서 출발하는 간선 정보를 반환한다.
	public List<Edge> getAdjVertices(int index) {
		return adjList.get(index);
	}

	// 주어진 인덱스에 해당하는 정점의 데이터를 반환한다.
	public T getData(int index) {
		return dataList.get(index);
	}

	private boolean valid(int index) {
		if (size <= 1) {
			System.out.println("정점이 없습니다.");
			return true;
		}

		if (index < 1 || index >= size) {
			System.out.println("유효한 정점 인덱스가 아닙니다.");
			return true;
		}
		return false;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < adjList.size(); i++) {
			sb.append("adjVertices to " + i + ": ");
			List<Edge> adjVertices = getAdjVertices(i);

			for (Edge adjVertex : adjVertices) {
				sb.append(adjVertex.getDestination() + "(" + adjVertex.getWeight() + ")" + " ");
			}

			sb.append("\n");
		}

		return sb.toString();
	}
}

 

실제 사용

public class Main {

	public static void main(String[] args) {
		///////////////////// 인접 리스트의 BFS /////////////////////
		AdjList_bfs<Integer> adjList_bfs = new AdjList_bfs<>();

		for (int i = 1; i <= 5; i++) {
			adjList_bfs.addVertex(i);
		}

		adjList_bfs.addEdge(1, 2);
		adjList_bfs.addEdge(1, 4);
		adjList_bfs.addEdge(2, 3);
		adjList_bfs.addEdge(2, 4);
		adjList_bfs.addEdge(2, 5);
		adjList_bfs.addEdge(3, 2);
		adjList_bfs.addEdge(4, 5);
		adjList_bfs.addEdge(4, 1);
		adjList_bfs.addEdge(5, 1);

		for (int i = 1; i <= 5; i++) {
			adjList_bfs.bfs(i);
			System.out.println();
		}
		/*1 2 4 3 5
		  2 3 4 5 1
		  3 2 4 5 1
		  4 5 1 2 3
		  5 1 2 4 3 */

		System.out.println("/////////////////////////////////////");

		///////////////////// 인접 행렬의 BFS /////////////////////
		AdjMatrix_bfs adjMatrix_bfs = new AdjMatrix_bfs(5);

		adjMatrix_bfs.insertSingleDir(1, 2);
		adjMatrix_bfs.insertSingleDir(1, 4);
		adjMatrix_bfs.insertSingleDir(2, 3);
		adjMatrix_bfs.insertSingleDir(2, 4);
		adjMatrix_bfs.insertSingleDir(2, 5);
		adjMatrix_bfs.insertSingleDir(3, 2);
		adjMatrix_bfs.insertSingleDir(4, 5);
		adjMatrix_bfs.insertSingleDir(4, 1);
		adjMatrix_bfs.insertSingleDir(5, 1);

		for (int i = 1; i <= 5; i++) {
			adjMatrix_bfs.bfs(i);
			System.out.println();
		}
		/*1 2 4 3 5
		  2 3 4 5 1
		  3 2 4 5 1
		  4 5 1 2 3
		  5 1 2 4 3 */
	}
}