DFS 및 BFS의 코드들은 아래 주소에서 볼 수 있다.
https://github.com/HiiWee/algorithm-Java/blob/master/src/structure/Graph.java
종강을 하고 드디어 DFS에 이어 BFS에 대해 작성을 시작하겠습니다.
BFS
BFS는 DFS와 동일하게 그래프를 순회하는 방법 중 하나이다.
Breadth First Search의 약자로 너비를 우선적으로 탐색한다는 의미이다.
BFS의 동작방식은 아래와 같이 나뉜다.
시작 정점을 결정하고 방문한다.- 방문한 정점에 인접한 정점을
큐에 모두 담는다. - 큐에서
POLL을해 정점을 꺼내고2번 작업을 반복한다. - 이 작업을
큐에 아무 원소도 없을때까지 반복
DFS와 원리는 동일하지만 DFS는 Stack을 이용하고 BFS는 Queue를 이용한다는 것에 차이점이 있다.
Stack은 LIFO(Last In First Out)구조를 가지지만 Queue는 FIFO(First In First Out)의 구조를 가진다.
실제 그림을 통한 설명을 통해 어떻게 Queue가 BFS를 구현할 수 있는지 알아보자
위와 같은 그래프는 정점 1, 2, 3, 4, 5를 가지며 각각의 간선들은 방향성이 없는 무방향 그래프다. 이를 Queue를 이용한 BFS는 아래와 같이 진행된다.
먼저 시작 정점은 1번 노드로 결정했다면 큐에 시작 정점을 담고 순회를 시작한다.
1. 순회를 시작하면 Queue에서 원소를 하나 꺼내고 해당 정점과 인접한 정점을 모두 큐에 담는다.
2. 방문 정점 인접한 모든 정점을 큐에 담았다면 다시 큐에서 정점을 꺼내서 다시 해당 정점의 인접 정점을 큐에 담는 작업을 반복한다.
3. 정점 2와 인접한 정점 5를 스택에 담았으므로 다시 큐에서 정점을 꺼낸다.
4. 정점 3과 인접한 정점들은 모두 큐에 담겨있거나 방문한 정점들이므로 다시 큐에서 정점을 꺼낸다.
5. 정점 4와 인접한 정점들은 모두 큐에 담겨있거나 방문한 정점들이므로 다시 큐에서 정점을 꺼낸다.
6. 정점 5가 꺼내지고 주변에 인접한 정점들은 모두 방문한 정점들이다. 따라서 다음 작업을 진행하려 했지만, 큐에 아무 원소도 없으므로 순회를 종료한다.
괄호안에 숫자는 탐색한 순서를 나타낸다.
최종적인 순회의 결과는 위와 같다.
여기서 5번 정점이 2번과 연결되어 있는 이유는, 2번 정점을 방문했을때 큐에 담긴 정점이 5번 정점이므로 연결선이 존재하게 된다.
그러면 실제 코드를 이용해 BFS를 구현해보자
BFS 구현(Java)
인접 행렬, 인접 리스트를 통한 구현 방법이 존재하고, 여기서는 인접 리스트를 이용한 BFS를 구현해보자
Graph, Node 클래스
인접 리스트를 이용한 그래프의 표현
Graph 클래스: 그래프를 구성하는 노드들을 저장하는 클래스
Node 클래스: 각 노드들의 데이터와, 인접리스트, 해당 노드의 방문여부를를 저장하는 클래스
data: 간단하게 int 타입을 이용adjacent(인접리스트): java.util.LinkedListvisited: boolean
public class Graph {
static class Node {
int data;
LinkedList<Node> adjacent;
boolean visited;
public Node(int data) {
this.data = data;
this.visited = false;
adjacent = new LinkedList<>();
}
}
Node[] nodes;
public Graph(int size) {
nodes = new Node[size];
for (int i = 0; i < size; i++) {
nodes[i] = new Node(i);
}
}
}Node 클래스
각 노드들을 관리하는 클래스이며
각 노드들이 생성될 때 생성자를 통한 모든 필드의 초기화 작업이 이루어진다.
Graph 클래스
Node클래스의 집합으로 이루어지며 생성자의 인수로 노드의 개수를 입력받는다.
이후 Node의 생성자를 이용해 모든 노드를 초기값으로 변경해준다.
편의를 위해 각 노드의 번호와 데이터 값은 동일하다.
Graph 클래스의 메소드
addEdge(int l1, int l2)
public void addEdge(int l1, int l2) {
Node n1 = nodes[l1];
Node n2 = nodes[l2];
if (!n1.adjacent.contains(n2)) {
n1.adjacent.add(n2);
}
if (!n2.adjacent.contains(n1)) {
n2.adjacent.add(n1);
}
}
// 콘솔에 현재 노드의 데이터를 출력
public void print(Node node) {
System.out.print(node.data + " ");
}노드 생성이후 각 노드들을 이어주는 간선을 추가해 각 노드들의 인접한 관계를 표시해준다.
List<T>.contains(Object T) 메소드는 리스트내에 동일한 요소가 있으면 참 값을 반환한다. !를 이용해 현재 리스트에 없는 노드만 추가해 중복을 방지한다.
현재 무방향 그래프를 만들고 있으므로 E(1, 2)와 E(2, 1)은 동일한 간선으로 취급된다.
BFS(int rootIndex)
public void BFS(int index) {
Node root = nodes[index];
Queue<Node> que = new LinkedList<>();
que.add(root);
root.visited = true;
while (!que.isEmpty()) {
Node node = que.poll();
for (Node n : node.adjacent) {
if (!n.visited) {
n.visited = true;
que.add(n);
}
}
print(node);
}
}매개변수로 받은 정점의 인덱스를 시작 정점으로 두고 Queue에 시작 정점을 담고 방문처리 후 순회를 시작한다.
while문을 돌며 Queue에서 정점을 하나 꺼내고 해당 정점과 인접한 정점 중 아직 방문하지 않았다면 Queue에 삽입하고 방문처리를 한다.
방문 정점에 대한 모든 인접 정점이 Queue에 삽입됐다면 방문 정점을 콘솔에 출력하고 다음 정점을 Queue에서 꺼내 반복한다.
언제까지?! Queue에 아무 원소도 없을때까지 반복한다.
main 함수 및 실행결과
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.BFS(0);
}
실제로도 결과가 1 -> 2 -> 3 -> 4 -> 5 순서로 출력되는걸 볼 수 있다.
결론
DFS와 BFS는 거의 비슷한 특징을 가지지만 Stack과 Queue를 사용하는 점이 매우 큰 차이점이라고 할 수 있다.
이 부분을 잘 알고 알고리즘 문제를 풀때 이용하면 좀 더 수월하게 할 수 있을것이다.
아직도 어려운 난이도의 DFS, BFS 문제를 만나면 한참 시간을 쏟지만, 글로 하나씩 정리하면서 개념적인 부분은 확실하게 정립될 수 있었다.
조금 늦었지만 깊이, 너비 우선 탐색의 글을 마쳤다. 종강도 했고, 이제 온전히 집중할 수 있는 시간으로 방학을 보내야겠다!
References
