Graph - 깊이우선탐색(DFS)
2023. 3. 13. 10:54ㆍ알고리즘
반응형
한곳을 먼저 깊이 탐색하다가 더이상 갈 수 없을때 다른쪽을 탐색
#DFS
#전역변수를 사용한 경우
graph = {
'A' : ['B', 'D', 'E'],
'B' : ['A', 'C', 'D'],
'C' : ['B'],
'D' : ['A', 'B'],
'E' : ['A']
}
visited = []
def dfs(current):
visited.append(current)
for k in graph[current]:
if k not in visited:
dfs(k)
return visited
######################################################
#전역변수 사용 안한 경우
def dfs(graph, current, visited=[]):
visited.append(current)
for k in graph[current]:
if k not in visited:
visited = dfs(graph, k, visited)
return visited
print(dfs('A'))# 결과 >>> ['A', 'B', 'C', 'D', 'E']
반응형
'알고리즘' 카테고리의 다른 글
그래프 - 너비우선탐색(BFS) (0) | 2023.03.13 |
---|---|
자료구조 - 그래프(GRAPH) (0) | 2023.03.11 |
트리 Tree (1) | 2023.03.08 |
재귀 (Recursion) (0) | 2023.02.27 |
Hash table (0) | 2023.02.26 |