개인적으로 어려워 하는 알고리즘,,
알고리즘
BFS는 FIFO를 원칙으로 하는 Queue로 구현한다.
탐색을 시작하는 첫 노드(root)를 queue에 넣고 탐색을 시작한다.
A. queue에서 노드를 꺼낸다.
B. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문하고 queue에 넣는다.
queue에 노드가 없어질 때 까지 AB반복
구현
def bfs(graph, root):
visit = list()
queue = [root]
#AB반복
while queue:
temp = queue.pop(0)
if temp not in visit:
print(temp)
visit.append(temp)
queue.extend(graph[temp])
알고리즘
DFS는 LIFO를 원칙으로 하는 Stack으로 구현한다.
탐색을 시작하는 첫 노드(root)를 stack에 넣고 탐색을 시작한다.
A. stack의 최근 노드를 확인한다.
B. 확인한 노드와 연결된 노드 중 인접한 노드를 방문하고 stack에 넣는다.
C. 인접한 노드 중 방문하지 않은 노드가 없다면 stack에서 노드를 하나 꺼낸다.
stack이 노드가 없어질 때 까지 ABC 반복
구현
def dfs(graph, root):
visit = list()
stack = [root]
#ABC반복
while stack :
temp = stack.pop()
if temp not in visit :
print(temp)
visit.append(temp)
stack.extend(graph[temp])
더보기

graph info

code
graph = {'A': set(['B', 'C', 'E']),
'B': set(['A', 'D', 'F']),
'C': set(['A', 'G']),
'D': set(['B']),
'E': set(['A', 'F']),
'F': set(['B', 'E']),
'G': set(['C'])}
'Algorithm > Tip' 카테고리의 다른 글
[Python] web scraping (0) | 2020.09.25 |
---|---|
[Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS (0) | 2020.08.24 |