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

DFS 란?!

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

[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를 구하는 코드들이 많이 없는 거 같아서 한번 짜보았다..