그래프 - DFS 구현

DFS 알고리즘 구현

스택, 큐 자료구조 활용

• need_visit stack
• visited queue

* BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있다.

 

개념

위 그래프에 대해 DFS를 구현한다면 다음과 같은 순서로 진행된다.

 

1. 제일 처음 노드 A를 need_visit stack에 추가한다. (시작)

2. need_visit stack에서 pop한 뒤 temp_node로 가져온다.
    (BFS에서 dequeue하던 것과 대조됨)

3. temp_node가 visited queue에 존재하는지 확인

4-1. 없다면 visited queue에 A를 추가

4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작

5. temp_node였던 A를 graph_dict에서 key로 찾아 나온 value를 need_visit stack에 추가한다.
    (마찬가지로 extend로 추가)

6. need_visit stack이 빌 때 까지 2~5번 과정 반복

7. visited queue 리턴 (끝)

 

코드

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

def dfs(graph, start_node):
  visited = []
  need_visit = []

  need_visit.append(start_node)
  while need_visit:
    temp_node = need_visit.pop()
    if temp_node not in visited:
      visited.append(temp_node)
      need_visit.extend(graph[temp_node])
  return visited

print(dfs(graph, 'A'))

 

시간복잡도

노드 수: V

간선 수: E

라고 칭할 때

while need_visit은 V + E번 만큼 수행함으로 

시간복잡도는 BFS와 마찬가지로 O(V+E)가 된다.

 

+ 추가

만약 위와 같이 왼쪽부터 찾아가는 DFS를 하고 싶을 경우 아래와 같이 할 수 있다.

 

코드

def dfs(graph, start_node):
  visited, need_visit = [], []

  need_visit.append(start_node)
  while need_visit:
    print(need_visit)
    temp_node = need_visit.pop(0)
    if temp_node not in visited:
      visited.append(temp_node)
      need_visit = graph[temp_node] + need_visit
  return visited

print(dfs(graph, 'A'))

need_visit에서 pop()하던게 pop(0)으로 맨 앞을 뽑아가게 바뀌었고

need_visit 뒤에 graph[temp_node]를 붙이는게 아닌 

앞 부분에 붙여버린다.

이 과정에서 extend를 사용할 수 없어 그냥 + 를 통해 붙인 다음 need_visit에 넣어주는 방식을 택했다.