큐(Queue)
자료구조 이용def bfs(graph, start_node):
visit = list()
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visit:
visit.append(node)
queue.extend(graph[node])
return visit
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'G', 'H', 'I'],
'D': ['B', 'E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']
}
print(bfs(graph, 'A'))
<output>
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
pop(0)
은 시간복잡도가 O(N)
이라 매우 비효율적인 코드가 만들어 진다. 따라서 collections
라이브러리의 deque
를 사용한다.
from collections import deque
def bfs(graph, start_node):
visit = list()
queue = list()
queue = deque(start_node) # append
while queue:
node = queue.popleft() # pop(0)
if node not in visit:
visit.append(node)
queue.extend(graph[node])
return visit
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'G', 'H', 'I'],
'D': ['B', 'E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']
}
print(bfs(graph, 'A'))
<output>
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
스택(Stack)
자료구조 이용def dfs(graph, start_node):
visit = list()
stack = [start_node]
while stack:
node = stack.pop()
if node not in visit:
visit.append(node)
stack.extend(graph[node])
return visit
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'G', 'H', 'I'],
'D': ['B', 'E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']
}
print(dfs(graph, 'A'))
<output>
['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']