[Python] DFS(Depth-First Search) 정점의 Depth 구하기?!

[Python] DFS(Depth-First Search) 정점의 Depth 구하기?!

반응형

DFS 란?!

[Python] Graph Traversals(Search) 그래프 순회(탐색) 정리

DFS는 깊이 우선 탐색이다.. 위의 글을 보면 쉽게 이해할 수 있을 것이다.

예제 그래프

위 그래프 정점들의 깊이를 구할 것이다.

[Python/파이썬]

depth_list = [0] graph = { 1 : [2, 3], 2 : [1, 4, 5], 3 : [1], 4 : [2, 6], 5 : [2], 6 : [4], } def dfs(v, depth, discovered=[]): discovered.append(v) # discovered는 탐색한 노드들을 저장한다. for w in graph[v]: if not w in discovered: # w가 탐색한 노드가 아니라면 탐색한다. depth_list.append(depth) discovered=dfs(w,depth+1,discovered) return discovered result = dict(zip(dfs(1,1),depth_list)) print(result[1]) print(result[2]) print(result[3]) print(result[4]) print(result[5]) print(result[6])

0 1 1 2 2 3

DFS를 이용하여 Depth를 구하는 코드들이 많이 없는 거 같아서 한번 짜보았다..

반응형

from http://security-nanglam.tistory.com/531 by ccl(A) rewrite - 2021-08-07 16:00:19