목록그래프 (1)

하루살이 개발자

[알고리즘] 그래프 탐색 01_DFS(깊이 우선 탐색)/BFS(너비 우선 탐색)

DFS (깊이 우선 탐색, Depth First Search) 루트 노드(최상위)부터 리프 노드(최하위)까지 탐색한 후, 다시 올라와서 내려가는 방식(깊은 부분을 우선으로 탐색) 재귀(Recursion) 함수를 활용할 수 있음 스택(Stack)을 활용할 수 있음 동작 과정 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 함 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복 1) 재귀 구조로 구현 # DFS_재귀 def dfs_recursive(graph, start, visited=[]): visited.append(start) # 방문한 노드 추가 for node in graph[start]:..
CS/알고리즘 2022. 1. 23. 02:22
이전 Prev 1 Next 다음