[Algorithm] 그래프 탐색 알고리즘 - BFS & DFS

"그래프 탐색"이란 그래프에서 하나의 노드를 시작으로 다수의 노드를 방문하는 알고리즘을 말한다. 

이때, 방문하는 노드는 딱 한 번씩만 방문하는 것이 특징이다.

만약, 자료구조 그래프에 대한 내용이 궁금하다면 아래 포스팅을 참고 바란다.

https://seokyoungg.tistory.com/94

[Data Structure] Graph

 

이러한 그래프 탐색 알고리즘에는 2가지가 있다. 

• BFS
• DFS

 

 

BFS

"BFS"는 Breadth-first Search의 약자로 말 그대로 너비 우선 탐색이다.

 

BFS는 하나의 정점을 시작으로 인접한 모든 정점들을 우선 방문하는 방법이다. 

이때, BFS는 자료구조 Queue를 사용하게 된다.

만약, 자료구조 Queue에 대한 설명과 구현방법이 궁금하다면, 해당 포스팅을 참고 바란다. 

https://seokyoungg.tistory.com/90

[Data Structure] Queue

 

구현

그래프를 구현하는 방법에는 크게 2가지가 있다. 

• 인접 행렬 
• 인접 리스트

이 2가지 방식별로 코드와 시간복잡도는 달라지게 된다.

 

인접 행렬

func bfs<T>(graph: AdjacencyMatrixGraph<T>, startNode: Node<T>) {
	var queue = Queue<Node<T>>()
	var isVis = [Node<T>: Bool]()
	
	isVis[startNode] = true
	queue.enqueue(startNode)
	
	while let current = queue.dequeue() {
		// 모든 vertex와 연결되어 있는지 정보를 확인한다.
		let allVertexs = graph.allVertexs()
		for vertex in allVertexs {
			if !graph.isConnect(from: current, to: vertex) { continue }
			if isVis[vertex] != nil { continue }
			
			isVis[vertex] = true
			queue.enqueue(vertex)
		}
	}
}

우선, 앞서 말했듯 Queue자료구조와 방문했는지 여부를 확인하기 위한 isVis 배열도 선언한다.

이후 과정은 다음과 같다. 

• 초기 지점을 Queue에 넣어주고, isVis를 통해 방문 여부를 체크해 준다. 
• 이후, 아래 과정을 Queue가 비어 있을 때까지 반복한다. 
• graph내의 모든 정점들에 대해, 현재 정점과 연결되어 있는지 확인한다. 
• 만약 연결되어 있고, 방문 이력이 없다면 방문한다. 
• 방문할 땐, 큐에 넣어주고 isVis를 true로 체크해준다.

 

인접 리스트 

func bfs<T>(graph: AdjacencyListGraph<T>, startNode: Node<T>) {
	var queue = Queue<Node<T>>()
	var isVis = [Node<T>: Bool]()
	
	isVis[startNode] = true
	queue.enqueue(startNode)
	
	while let current = queue.dequeue() {
		// 현재 노드를 기준으로 인접 노드만 확인한다.
		for vertex in graph.adjacentVertex(for: current) {
			if isVis[vertex] != nil { continue }
			
			isVis[vertex] = true
			queue.enqueue(vertex)
		}
	}
}

 

전체적인 과정은 인접행렬과 유사하다. 

하지만, 모든 노드에 대해 연결된 노드를 직접 찾아야 했다면, 

인접 리스트는 연결된 노드에 바로 접근할 수 있다. 

 

시간복잡도 

정점의 개수가 $V$, 간선의 갯수가 $E$라고 가정해 보자.

인접 행렬 

인접행렬의 경우, 현재 노드에 대해 모든 노드와 연결되어 있는지 확인 후 방문을 진행했다. 

따라서, $O(V^2)$의 시간복잡도가 소요된다.

 

인접 리스트

인접 리스트의 경우, 현재 노드에 대해 연결된 노드의 개수만큼 확인 후 방문하게 된다. 

즉, 모든 노드를 돌게 되며 ($V$번), 이때 그래프 내의 모든 간선의 개수만큼 확인하게 된다. $E$

따라서 시간복잡도는 $O(V + E)$가 된다.

 

인접 행렬 vs. 인접 리스트 

간선의 수가 적은 Sparse Graph의 경우에는 메모리적인 측면에서도 시간복잡도 측면에서도 인접리스트가 유리하다.

반면, 간선이 많은 그래프(Dense Graph)에선 인접행렬을 사용하는 것이 유리하다.

 

 

활용 사례 

최단 거리 문제

가장 대표적으로 최단 경로 문제를 해결할 수 있다. 

다만, 간선의 가중치가 모두 동일해야 한다. 

가중치가 다른 경우의 최단 거리는 "다익스트라", "벨만 포드"등등 다른 알고리즘을 통해 해결해야 한다.

 

BFS는 너비 우선 탐색이다. 따라서, 목적지까지 가장 먼저 도착한 경로가 최단 거리가 된다.

 

따라서, 다음과 같이 isVis를 통해 거리를 확인해 주면 된다.

(백준 문제의 경우, 대부분 BFS문제에서 2차원 배열을 graph로 활용하기 때문에, graph를 2차원 배열로 변경했다.)

func bfs<T>(graph: [[T]], startPoint: Point, endPoint: Point) -> Int {
	var queue = Queue<Point>()
	var isVis = Array(
		repeating: Array(repeating: 0, count: graph[0].count),
		count: graph.count
	)
	
	isVis[startPoint.x][startPoint.y] = 0
	queue.enqueue(startPoint)
	
	while let current = queue.dequeue() {
		let currentDistance = isVis[current.x][current.y]
		
		if current == endPoint {
			return currentDistance
		}
		
		for direction in (0..<4) {
			let nextX = current.x + disX[direction]
			let nextY = current.y + disY[direction]
			
			if nextX < 0 || nextX >= graph.count || nextY < 0 || nextY >= graph[0].count { continue }
			if isVis[nextX][nextY] != 0 { continue }
			
			isVis[nextX][nextY] = currentDistance + 1
			queue.enqueue(.init(x: nextX, y: nextY))
		}
	}
	
	return -1
}

 

 

이외에도 웹 크롤링, 그래프 연결성 검사 등등 다양한 분야에서 활용된다.

 

 

DFS

"DFS"는 Depth-First Search의 약자로 깊이 우선 탐색이다.

 

 

"DFS"는 하나의 노드를 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다.

 

BFS와의 탐색 과정 차이를 보게 되면 다음과 같다. 

 

 

이러한 DFS에서는 스택 자료구조를 사용하게 되는데, 스택에 대한 자세한 설명은 아래 링크를 참고 바란다.

https://seokyoungg.tistory.com/89

[Data Structure] Stack

 

 

이러한 DFS는 재귀로도 해결할 수 있다. 

사실, 재귀함수의 호출 형태가 내부적으로는 Stack자료구조에 해당 함수의 Stack Frame을 쌓는 구조이기 때문에, 유사하다.

 

 

구현 

BFS와 마찬가지로 인접 행렬, 인접리스트 둘 다 활용이 가능하다. 

또한, 앞서 말했듯 재귀 스택 둘다 활용이 가능하다. 

 

인접 행렬 

우선, Stack의 방식이다. 

func dfsStack<T>(graph: AdjacencyMatrixGraph<T>, startNode: Node<T>) {
	var stack = Stack<Node<T>>()
	var isVis = [Node<T>: Bool]()
	
	while let current = stack.pop() {
		let allVertexs = graph.allVertexs()
		for vertex in allVertexs {
			if !graph.isConnect(from: current, to: vertex) { continue }
			if isVis[vertex] != nil { continue }
			
			isVis[vertex] = true
			stack.push(vertex)
		}
	}
}

코드를 보게 되면, BFS와 유사하다. 다만, 차이점은 Stack과 Queue의 자료구조의 차이점에 있다.

 

 

다음으로는 재귀호출의 방식이다. 

func dfsReculsive<T>(
	graph: AdjacencyMatrixGraph<T>,
	currentNode: Node<T>,
	isVis: [Node<T>: Bool]
) {
	guard isVis[currentNode] == nil else { return }
	var isVis = isVis
	isVis[currentNode] = true
	
	for vertex in graph.allVertexs() {
		if !graph.isConnect(from: currentNode, to: vertex) { continue }

		dfsReculsive(graph: graph, currentNode: vertex, isVis: isVis )
	}
	isVis[currentNode] = false
}

재귀 호출 방식도 상당히 유사하다. 다만 Stack 내부에서 구현했던 코드를 붙여 넣은 게 전부이다.

 

 

인접 리스트

우선, stack의 구현방식이다.

func dfsStack<T>(graph: AdjacencyListGraph<T>, startNode: Node<T>) {
	var stack = Stack<Node<T>>()
	var isVis = [Node<T>: Bool]()
	
	while let current = stack.pop() {
		for vertex in graph.adjacentVertex(for: current) {
			if isVis[vertex] != nil { continue }
			
			isVis[vertex] = true
			stack.push(vertex)
		}
	}
}

 

마찬가지로 BFS의 방식가 유사하나 사용한 자료구조가 Queue가 아닌 Stack이라는 차이점이 있다. 

 

다음으로 재귀방식이다.

func dfsReculsive<T>(
	graph: AdjacencyListGraph<T>,
	currentNode: Node<T>,
	isVis: [Node<T>: Bool]
) {
	guard isVis[currentNode] == nil else { return }
	var isVis = isVis
	
	isVis[currentNode] = true
	
	for vertex in graph.adjacentVertex(for: currentNode) {
		dfsReculsive(graph: graph, currentNode: vertex, isVis: isVis )

	}
	
	isVis[currentNode] = false
}

 

 

시간복잡도 

DFS 역시 마찬가지로 시간복잡도가 동일하다. 

• 인접 행렬: $O(V^2)$
• 인접 리스트: $O(V + E)$

하지만, DFS를 재귀로 구현하는 경우, Address Space의 Stack 메모리가 다 차게 되는 Stack OverFlow가 발생할 수 있다.

 

활용 사례

BFS와 마찬가지로 최단거리 탐색에 사용될 수 있지만, BFS와 다른 점은 다음과 같다. 

BFS에선 최초로 목적지에 도달한 지점이 최단거리임을 보장했지만, DFS에선 보장하지 않는다. 

이는 깊이 우선 탐색이기 때문이며, 이를 위해 별도의 길이를 저장하는 전역변수 혹은 파라미터 필요하게 된다. 

따라서, 최단 거리 문제에선 BFS가 대부분 유리하다. 

 

이 외에, 백트레킹, 그래프의 사이클 찾기 등등 여러 분야에서 사용된다.

 

 

References

위키백과

• Breadth-first search

• Depth-first search