[알고리즘] 깊이 우선 탐색(DFS) - Python

깊이 우선 탐색 Depth-First Search

깊이 우선 탐색(DFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 깊이 방향(Depth)으로 확장하는 방식의 탐색을 말합니다. 깊이 방향이란, 한 노드에서 시작해 여러개의 다음 노드로 펼쳐 나간 방식과 달리 한 노드에서 다음 하나의 노드로 들어가는 방향을 말합니다. 미로찾기의 예시를 떠올리면 DFS의 탐색 방향을 이해하기 쉽습니다.

아래 그림1을 보겠습니다. DFS로 그래프를 탐색하면, 아래 그림의 보라색 경로와 같이 탐색하게 됩니다. S1에서 출발하여 a,b,c,d만 순회하고 끝이 납니다. 하지만 c와 f가 남았으므로 S3에서 다시 탐색을 시작합니다. 그리고 c에서 e와 f중 아직 방문하지 않은 f노드를 탐색함으로써 DFS가 끝이 납니다.

그림1

pseudo code와 함께 DFS를 이해해보겠습니다.

 

Pseudo Code

아래의 DFS_Visit은 Simple DFS라고도 불리며, 그림 1에서 S1(a)에서 출발해 b,c,d까지 탐색한 과정이 DFS_Visit에 해당합니다. 즉, DFS를 시작하고 한 번 탐색이 끝날 때 까지의 과정입니다.

 

• parent를 업데이트 해주기 위한 dictionary를 우선 초기화 한 후,
• 현재 방문하고 있는 노드 u의 인접 노드(v) 중에서 다음으로 탐색할 대상을 선정합니다.
• parent를 u로 업데이트 함으로써 방문하고
• DFS_Visit 재귀를 통해 더 깊은 다음 노드를 탐색합니다.

 

아래의 DFS는 Full DFS라고도 불리며, 그림 1에서 막다른 길에 다다른 탐색을, 탐색하지 않은 S3에서 새롭게 시작할 수 있게 하는 코드입니다. 

 

• 초기 시작점 중, 방문하지 않은(parent가 없는 노드) 노드가 있다면
• parent를 None으로 설정함으로써 parent가 없는 상태로 새로운 root로써 시작할 수 있게 하고,
• DFS_Visit을 호출하여 Simple DFS를 다시 수행할 수 있게 합니다.

 

 

Edge Classification

Edge Classification이란 DFS탐색 중, 실제 탐색 경로를 제외한 나머지 Edge들을 분류해주는 작업입니다. 이 작업에서는 Graph를 Tree로 생각하면 편합니다. 그림 1을 다시 보겠습니다.

그림1'

그림1에서 실제 탐색 경로로 지났던 부분은 파란색 하이라이트 부분 뿐입니다. 그 외의 나머지 3개의 edge에 대해 분류를 해줄 수 있습니다. Edge Classification은 3개의 분류 경우가 있습니다.

1. Forward: node → descendant in tree: 다시 후손으로 내려가는 경우
2. Backward: node → ancestor in tree: 다시 조상으로 돌아가는 경우
3. Cross: all others(sibling or between two non-ancestor related subtrees): 그 외(tree에서 형제노드의 경우 또는 서로 조상이 다른 별개의 노드가 연결된 경우)

*Edge Classification의 Pseudo Code는 글 마지막에 첨부하겠습니다.

 

Visualization

DFS를 시각화 하기 위해 위 Pseudo Code에서 코드를 추가해 보겠습니다.

• ".d"는 discovered를 의미하며 처음 탐색된 시점을 말합니다. ".f"는 finish를 의미하며 해당 노드의 연결된 모든 adjacency의 탐색이 끝난 시점을 말합니다.
• ".color"을 통해 node의 색을 업데이트 합니다.
  • WHITE: ".d"이전: 미방문 노드
  • GRAY: ".d"와 ".f" 사이: 방문 중인 노드
  • BLACK: ".f": 방문이 끝난 노드
• ".파이"는 predecessor, 즉 parent을 의미합니다.

위 코드를 통해 DFS를 시각화 하면 아래와 같습니다.

노드 안의 숫자는 ".d/.f"(도착시간/종료시간)를 나타냅니다.

• (a)~(d): u에서 탐색을 시작하여 x까지 깊이 우선 탐색을 마칩니다.

 

• (e)~(k): 더 이상 진행될 인접 노드가 없으므로, 미로찾기 하듯이 다시 후진합니다. 이때 방문이 완전히 종료되면 검정색으로 칠합니다. Edge Classification 작업도 진행함으로써, 하나의 Sub Graph에 대한 DFS_Visit 탐색을 완료합니다.

 

• (l)~(p): 그 다음 Full_DFS를 통해 새로운 시작 노드 w를 찾고, 이 Sub Graph에서도 동일하게 DFS_Visit 탐색을 완료합니다.

 

Time Complexity

대부분의 Graph 알고리즘과 같이 DFS 또한 O(V+E)의 수행시간을 갖습니다. 모든 edge를 한 번씩 검사하고, 각 Vertex를 모두 방문합니다.

 

 

참고) Edge Classification Pseudo Code

class DFS_Result:
	def __init__(self):
    	self.parent = {}
        self.start_time = {}
        self.finish_time = {}
        self.edges = {}
        self.order = []
        self.t = 0
    
     def DFS(G): #Full DFS
     	results = DFS_Result()
        for v in G.vertices():
        	if v not in results.parent:
            	DFS_Visit(G, v, results)
        return results
        
        
     def DFS_Visit(G, v, results, parent=None):
     	results.parent[v] = parent
        results.t += 1
        results.start_time[v] = results.t
        if parent:
        	results.edges[(parent, v)] = 'tree' #일반 경로
          
        #-----------------Edge Classification-----------------#
        for n in Adj[v]:
        	if n not in results.parent:
        		DFS_Visit(G, n, results v)
                
        	elif n not in results.finish_time:
        		results.edges[(v,n)] = "Backward"
                
        	elif results.start_time[v] < results.start_time[n]:
        		results.edges[(v,n)] = "Forward"
                
        	else:
        		results.edges[(v,n)] = "Cross"
          #-----------------------------------------------------#
          
          results.t += 1
          results.finish_time[v] = results.t
          results.order.append(v)

 

다음은 BFS에 대해 설명한 글입니다.

https://stevenkim1217.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS-Python

[알고리즘] 너비 우선 탐색(BFS) - Python

 

 

참고 자료

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/

Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare