python#2 그래프의 DFS 순회, 재귀함수에 대한 고찰

그래프

• 객체의 일부 쌍들이 연관되어 있는 객체 집합구조로 순회와 최단 경로를 찾는 알고리즘에 주로 사용되는 자료구조이다.

정점과 간선의 순회

• 오일러 경로 : 모든 간선을 한번씩 방문(한 붓 그리기)
  해밀턴 경로 : 모든 정점을 한번씩 방문(다익스트라, 크루스칼, 프림)
• DFS : 깊이 우선 탐색(Depth First Search)으로 스택이나 재귀로 구현, 백트래킹을 통해 뛰어난 효용을 보인다.
  BFS : 너비 우선 탐색(Breadth First Search)으로 큐로 구현한다. 재귀로는 구현이 불가능하다.
• 백트래킹 : 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 그 이전의 후보로 되돌아가 불필요한 계산과정을 줄이는 알고리즘

DFS로 구현 하는 그래프

아래의 그래프를

딕셔너리로 구현하면 다음과 같다.

graph = {
    1 : [2, 3, 4],
    2 : [5],
    3 : [5],
    4 : [],
    5 : [6, 7],
    6 : [],
    7 : []
    }

1.스택과 while pop구문으로 구현하는 DFS

return -> [1, 4, 3, 5, 7, 6, 2]

def DFS(graph, start_node):
    # 1개의 dict와 2개의 list
    need_visit, visited = list(), list()
    # 초기화
    need_visit.append(start_node)
    # while pop에서는 need_visit리스트의 원소들을 삭제하는 구조를 취한다. 
    #스택을 활용해서 쉽게 DFS를 구현할 수 있지만 
    #이 방식은 순회의 방향이 오른쪽 노드를 우선으로 탐색하게 된다.
    while need_visit:
        node = need_visit.pop()
        #그래프의 그림을 보며 따라가보면 쉽게 이해할 수 있다.
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])     
    return visited

2-1. 재귀함수의 특징과 그 특징을 이용한 알고리즘의 구상

• 재귀함수를 작성할 때는 다음 재귀함수를 어떤 조건하에서 불러올 것인지를 잘 고려해야한다. 그리고 그 조건은 알고리즘의 최종 결과값으로부터 함수에 들어갈 인자를 고려하면 자연스럽게 드러나는 것 같다.
• 재귀함수가 필요한 경우를 따져볼 때 우선적으로 고려해야 하는 것은 문제가 동적계획법이나 Divide and conquer로 해결이 되는가이다. 또한 문제가 하나의 루트를 파고드는 형태 즉, DFS적인 순회를 요구한다면 list를 update하는 형식의 재귀함수를 사용할 수 있다.
• DFS의 방식을 따라 노드들을 순회하는 재귀함수를 구상하려고한다. 큰 틀에서 DFS/BFS 순회 알고리즘의 특징인 '1 graph와 2 list(visited, need_visit)'를 염두에 두고 코드를 작성해 보려고 한다.
• 우선적으로 따져볼 것은 결과값이 방문한 노드들을 저장한 list(visited)라는 것이다. 따라서 함수에는 visted.append(node)가 필수적으로 들어가게 될 것이다. 그렇다면 함수의 인자로 node와 graph를 받고, 재귀함수를 불러올 조건을 if node not in visted으로 생각해 볼 수 있겠다.
• 다음으로 함수의 실행 순서를 생각해보면 visited를 업데이트하고 for 구문을 활용해서 graph[node] 즉, value 값들을 순회한다면 재귀함수는 스택의 형태로 연산이 이루어지므로 정확히 DFS의 형태로 실행이 될 것이다.
• 끝으로 list(visited)는 함수의 인자로 넣어주어서 매 함수가 최신의 list를 가지고 진행을 할 수 있도록 해주어야 할 것이다.

2-2. 재귀함수로 구현한 DFS

return -> [1, 2, 5, 6, 7, 3, 4]

def recursive_dfs(node, visited = []):
    visited.append(node)
    for visiting_node in graph[node]:
    	if visiting_node not in visited:
        	recursive_dfs(visiting_node, visited)
    return visited