Python으로 구현한 DFS와 BFS

DFS와 BFS는 그래프의 정점을 순회할 때 가장 많이 쓰이는 알고리즘이다. 두 알고리즘 모두 한 정점에서 시작하여 엣지를 따고 한 노드씩 차례로 방문해간다. 하지만 DFS는 '깊이우선탐색'이기 때문에 엣지를 타고 최대한 깊게 들어갈 수 있을 때까지 들어간 뒤 다음 노드를 타는 반면, BFS는 '넓이우선탐색'이기 때문에 그 노드의 주변 노드부터 모두 방문한 다음 엣지를 타고 간다.

 

DFS는 스택이나 재귀함수를 사용하여 구현하고 BFS는 큐를 사용하여 구현한다. 아래 코드는 DFS를 구현할 때 재귀함수를 사용하였고 BFS를 구현할 때는 파이썬 기본 라이브러리인 Queue를 import하였다.

from queue import Queue

# Class which represents unweighted, undirected graph
class Graph():
	def __init__(self, num_node):
		self.num_node = num_node # the number of nodes
		self.adjacent_list = [[] for _ in range(num_node)]

	# add an edge for both nodes
	def add_edge(self, start, end):
		self.adjacent_list[start].append(end)
		self.adjacent_list[end].append(start)


# visit nodes by DFS using recursion
def DFS(graph, current_node, visited):
	visited[current_node] = True
	print(current_node, end=" ")
	for neighbor in graph.adjacent_list[current_node]:
		if not visited[neighbor]:
			DFS(graph, neighbor, visited)


# visit nodes by BFS using queue
def BFS(graph, start_node):
	queue = Queue()
	visited = [False for _ in range(graph.num_node)]
	visited[start_node] = True
	queue.put(start_node)

	while not queue.empty():
		current_node = queue.get()
		print(current_node, end=' ')
		for neighbor in graph.adjacent_list[current_node]:
			if not visited[neighbor]:
				queue.put(neighbor)
				visited[neighbor] = True


if __name__ == '__main__':
	# input three integers: the number of nodes, the number of edges,
	# the node from which we start a traversal.
	# Note that we number nodes from 0 to (num_node - 1).
	num_node, num_edge, start_node = map(int, input().split())

	graph = Graph(num_node)
	# input an edge with two numbers of nodes in each line
	for _ in range(num_edge):
		edge_start, edge_end = map(int, input().split())
		graph.add_edge(edge_start, edge_end)

	# print results
	print("DFS: ", end="")
	DFS(graph, start_node, visited=[False for _ in range(graph.num_node)])
	print("\nBFS: ", end="")
	BFS(graph, start_node)
	print()