알고리즘/DFS BFS2 [알고리즘] BFS 알고리즘 정의 루트 노드에서 시작해서 가장 가까운 노드부터 찾는 알고리즘 BFS (Breadth First Search) 약자로 한국어 표기로는 "넓이 우선 탐색" 또는 "너비 우선 탐색" 이라고 한다. 코드 구현 from collection import deque def bfs(index, graph, visited): queue = deque([index]) while queue: v = queue.popleft() visited[v] = True for i in range(len(graph)): if visited[i] == False: queue.append(i) return visited DFS vs BFS 그림으로 보면 차이점이 명확해질 것이다. 2020. 11. 6. [알고리즘] DFS 알고리즘 정의 루트 노드에서 시작해서 다음 분기를 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 DFS (Depth First Search) 약자로 한국어 표기로는 "깊이 우선 탐색" 이라고 한다. 장단점 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다 코드 구현 def dfs(index, graph, visited): stack = [index] while stack: v = stack.pop() visited[v] = True for i in range(len(graph)): if visited[i] == False.. 2020. 10. 17. 이전 1 다음 728x90 반응형
