[보기 쉬운 Algorithm] 깊이 우선 탐색(DFS) - Python
깊이 우선 탐색(Depth First Search)은 연결된 노드를 연속적으로 쫓아서 차례대로 탐색하는 알고리즘이다. 예를 들어 위와 같은 경우 'A'에서 탐색을 시작하면 'A'와 연결된 'B', 'D', 'F'를 먼저 찾고, 다음 'B'와 연결된 'C', 'C'와 연결된 'E'를 차례대로 탐색 후, 'D'와 연결된 'G', 다음 'F'를 찾는 것이다. 따라서 순서는 ['A', 'B', 'C', 'E', 'D', 'G', 'F']가 된다. def dfs(graph, start_node): visit = [] stack = [] stack.append(start_node) while stack: node = stack.pop(0) if node not in visit: visit.append(node) s..
[보기 쉬운 Algorithm] 너비 우선 탐색(BFS) - Python
너비 우선 탐색(Breadth First Search)은 연결된 노드를 연속적으로 쫓아서 찾는 것이 아닌 연결된 노드들을 모두 탐색한 후 그다음 연결 노드를 탐색한다. 예를 들어 위와 같은 경우 'A'에서 탐색을 시작하면 'A'와 연결된 'B', 'D', 'F'를 먼저 찾고, 다음 'B'와 연결된 'C', D와 연결된 'G', 'C'와 연결된 'E'를 찾는 것이다. 따라서 순서는 ['A', 'B', 'D', 'F', 'C', 'G', 'E']가 된다. def bfs(graph, start_node): visit = [] queue = [] queue.append(start_node) while queue: node = queue.pop(0) if node not in visit: visit.append(..
