그래프 - DFS & BFS

개요

 DFS와 BFS는 그래프 자료 구조에서 모든 노드를 순회&탐색하기 위해 사용되는 알고리즘이다.
 이를 이용하면 그래프 내 모든 노드를 대상으로 완전한 탐색을 실시하거나, 노드와 노드 사이 최단 경로를 알아내거나, 미로 같은 곳에서의 최적 경로를 찾아가게 할 수 있다.

DFS

 DFS란 깊이 우선 탐색(Depth First Search)의 준말이다. 가능한 한 가장 깊은 데까지 노드를 탐색한 뒤, 막다른 곳에 다다르면 왔던 순서대로 다시 돌아오며 다른 노드들을 탐색한다.

 위와 같은 무방향 그래프가 있다면, DFS를 실행했을 때...

 이런 순서대로 탐색을 수행하게 된다(A->C->D->G->F->H->J->I->E->B). 설명하자면 다음과 같다.

 1. A->C->D->G까지 탐색, G가 막다른 길이므로 D로 돌아간다.
 2. D->F->H->J까지 탐색, J가 막다른 길이므로 H로 돌아간다.
 3. H->I까지 탐색, I가 막다른 길이고, H의 순회가 끝났으므로 D까지 돌아간다.
 4. D->E까지 탐색, E의 경우 H로 갈 수 있지만, H는 이미 들렀던 장소이므로 H로 가지 않고 D로 돌아간다.
 5. D->B까지 탐색, B의 경우 A로 갈 수 있지만, A는 이미 들렀던 장소이므로 D로 돌아간다.
 6. D를 포함하여 모든 노드를 들렀기에 탐색을 종료한다.

 탐색의 순서도 중요하지만, '막다른 길일 때 뒤로 돌아간다'는 것과, '들렀던 장소'를 알고 있어야 한다는 점도 중요하다. 위의 그래프에서 A->C->D->G까지 탐색했다가 뒤로 돌아가서 A->C->D의 형태가 되는 것은, 스택의 모습과도 일치한다. 그렇다... DFS는 스택을 사용하는 것이다!

구현

 하지만 스택을 어떻게 쓰라는 것일까? 일단 어떻게 구현할지부터 생각해본다.

 1. 스택에 해당 노드를 push한다.
 2. 노드를 대상으로 하고 싶은 일을 한다.(println으로 출력해보거나)
 3. 인접한 다른 노드로 향한다.
 4. 1~3번을 반복하다가, 인접한 노드가 아예 없(거나 전부 방문했)을 경우 스택에서 현재 노드를 pop한다. 그 다음 3번으로 돌아간다.
 5. 스택이 완전히 빌 때까지 반복한다.

 이것을 코드로 구현하면...

 대충 봐도 꽤 어지러운 코드가 나온다.

 스택의 구조는 꼭 컬렉션 프레임워크의 Stack<T>이 아니더라도 사용할 수 있다. 재귀함수도 스택의 구조를 가지고 있기 때문이다. 재귀함수를 알고 있다면, 코드를 더 간결하게 쓰는 것이 가능하다.

 노드를 사용해 하고 싶은 일을 하는 부분만 빼면, 5줄 정도로 구현할 수 있다. (그나마도 스트림을 쓰면 훨씬 줄어든다.)

어떤 때에 쓰이나

 그래프 내에 사이클(노드끼리 순환하는 구조)이 있는지 확인할 수 있다.
 스택의 구조를 띄므로 미로 찾기 등, 어려운 길을 찾는 것에 유용하다.
 

BFS

  BFS란 너비 우선 탐색(Breadth First Search)의 준말이다. DFS와 달리, BFS는 가장 가까운 노드들부터 탐색해 최종적으로 가장 먼 곳의 노드를 탐색하는 알고리즘이다. DFS처럼 돌아오거나 하지 않기 때문에 스택의 구조를 띄지 않는다.

 아까 전과 같은 그래프에서 BFS를 사용한다면...

 대략 위와 같은 식(A->B->C->D->E->F->G->H->I->J)으로 탐색을 수행하게 된다. 설명하자면 다음과 같다.

 1. A를 탐색, 이후 인접한 모든 노드 B, C, D를 탐색, 이후 B로 넘어간다.
 2. B와 인접한 노드 A, D는 모두 방문한 노드다. C의 경우도 마찬가지이므로, B와 C를 스킵하고 D로 넘어간다.
 3. D와 인접한 모든 노드 E, F, G를 탐색, 이후 E로 넘어간다.
 4. E에서 H로, H에서 I, J 순으로 탐색한다.
 5. 모든 노드를 순회했으므로 탐색을 종료한다. (F<->H는 이미 방문한 상태라 스킵된다.)

 여기서도 방문했던 노드를 기억하는 것이 중요하다. BFS는 돌아가는 길을 기억하지 않고 앞으로만 나아간다는 것도 요점이다. 즉, BFS는 큐를 사용한다.

구현

 작동 방식을 대충 어림잡아본다.

 1. 시작 노드를 큐에 넣고, 방문 처리한다.
 2. 큐에서 가장 먼저 들어간 노드를 꺼낸다.
 3. 그 노드로 하고 싶은 일을 한다.
 4. 그 노드와 인접한 다른 노드들을 큐에 넣고, 동시에 방문 처리를 한다. (인접한 노드끼리 서로를 향하지 않게 하기 위해)
 5. 큐가 완전히 빌 때까지 2~4번을 반복한다.

 이것을 코드로 구현하면...

 다음과 같이 된다. 스택의 구조가 아니므로 재귀를 쓰는 것이 유리하지 않아(쓰려면 쓸 수는 있지 않을까...?) 반복문으로 구현했다.

어떤 때에 쓰이나

 두 노드간의 최단 거리를 찾을 때 사용한다. BFS의 특성 상 가장 가까운 노드들부터 죄다 뒤져보기 때문.
 최단 거리를 찾기에 유용하기 때문에 네트워크 라우팅, 지도에 기반한 내비게이션 등에도 사용할 수 있다.

 아래로는 이번 요약에 사용된 코드 전문이다.

 

import java.util.*;

class Node {
	private String name;
	private LinkedList<Node> nodes;
	
	public Node(String name) {
		this.name = name;
		nodes = new LinkedList<>();
	}
	
	public LinkedList<Node> getNodes() {
		return nodes;
	}
	public void addNode(Node node) {
		nodes.addLast(node);
	}
	
	@Override
	public String toString() {
		return "<" + name + ">";
	}
}

public class Test2 {
	public static void main(String[] args) {
		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node j = new Node("J");
		
		a.addNode(b); a.addNode(c);
		b.addNode(a); b.addNode(d);
		c.addNode(a); c.addNode(d);
		d.addNode(b); d.addNode(c); d.addNode(e); d.addNode(f); d.addNode(g);
		e.addNode(d); e.addNode(h);
		f.addNode(d); f.addNode(h);
		g.addNode(d);
		h.addNode(e); h.addNode(f); h.addNode(i); h.addNode(j);
		i.addNode(h);
		j.addNode(h);
		
//		bfs(a);
//		dfs(a);
//		dfs2(a, new HashSet<Node>());
	}
	
	public static void dfs(Node start) {
		Stack<Node> stack = new Stack<>();
		Set<Node> visited = new HashSet<>();
		
		stack.push(start);
		
		while (!stack.isEmpty()) {				// 스택이 빌 때까지 반복한다
			Node node = stack.peek();
			if (visited.contains(node)) {		// 스택을 pop해서 돌아왔을 때의 분기점
				stack.pop();
				continue;
			}
			
			visited.add(node);					// 현재 노드를 방문 기록에 추가
			System.out.print(node + "-");		// 하고 싶은 일을 한다
			
			boolean pushed = false;
			for (Node other : node.getNodes()) {// 인접한 노드들로 향한다
				if (visited.contains(other))	// 인접한 노드가 방문한 노드인 경우-
					continue;					// -스택에 넣지 않는다
				stack.push(other);
				pushed = true;
			}
			if (!pushed)						// 인접한 노드가 없는 경우
				stack.pop();					// 막다른 노드로 판단하여 pop한다
		}
	}
	
	public static void dfs2(Node node, Set<Node> visited) {
		visited.add(node);						// 현재 노드를 방문 기록에 추가
		System.out.print(node + "-");			// 하고 싶은 일을 한다
		
		for (Node other : node.getNodes()) {	// 인접한 노드들로 향한다
			if (visited.contains(other))		// 인접한 노드가 방문한 노드인 경우 스킵
				continue;
			
			dfs2(other, visited);				// 인자값만 다른 자기 자신을 호출
		}
	}
	
	public static void bfs(Node start) {
		Queue<Node> queue = new LinkedList<>();
		Set<Node> visited = new HashSet<>();
		
		// 첫 노드는 먼저 큐에 넣고 방문 처리를 해준다
		queue.offer(start);
		visited.add(start);
		
		while (!queue.isEmpty()) {				// 큐가 빌 때까지 반복한다
			Node node = queue.poll();			// 큐의 최상단에 있는 노드를 가져온다
			System.out.print(node + "-");		// 하고 싶은 일을 한다
			
			for (Node other : node.getNodes()) {// 인접한 노드들로 향한다
				if (visited.contains(other))	// 인접한 노드가 방문한 노드인 경우-
					continue;					// -큐에 넣지 않는다
				
				queue.offer(other);				// 인접한 노드를 큐에 넣고
				visited.add(other);				// 방문 처리를 하여 2중으로 들어가지 않게 한다
			}
		}
	}
}

 

그래프는 길 찾는데만 쓰는 것이 아니다

 일종의 망을 형성하면서, 순환이 가능한 관계라면, 그래프로 표현할 수 있다.

 1. 서울, 인천, 파주, 부천 등, 도시들은 서로 길을 통해 연결되어 있다. 이것은 그래프다!
 2. 나와 친구1, 친구1과 친구2, 친구2와 친구3, 친구3과 나는 서로 친하다. 이것은 그래프다!
 3. 웹사이트에 들어가면 다른 사이트로 가는 링크가 잔뜩 있다. 링크끼리 서로 연결되어 있다? 이것은 그래프다!
 4. 윈도우의 폴더 구조는 서로 연결되어 있다. 이것은 그래프...가 아니다! 폴더 속의 폴더는 순환 관계가 아닌 종속 관계이기 때문이다. 가장 안에 있는 폴더에서 밖에 있는 다른 폴더로 향하는 구조가 아니기에 이것은 그래프가 아니라 트리다!
 5. 사실 더 생각이 안 난다...!!

그래서 언제 어느때에 뭘 사용하는 것이 좋은가

 BFS와 DFS 모두 시간 복잡도는 동일하다. 인접 리스트의 경우 O(정점 + 간선), 인접 행렬의 경우 O(간선^2)의 시간이 들게 된다. 단순히 정리하자면 다음과 같다.

	DFS	BFS
속도	느린 편	빠른 편
주된 장점	완전 탐색	최단 경로 찾기
메모리 소모	적은 편	많음