[자료구조] 그래프 탐색

기본적인 그래프 탐색 방법인 깊이 우선 탐색과 너비 우선 탐색에 대해 알아보겠다.

그래프의 모양

mygraph = {"A": {"B","C"},
          "B": {"A","D"},
          "C": {"A","D","E"},
          "D": {"B","C","F"},
          "E": {"C","G","H"},
          "F": {"D"},
          "G": {"E","H"},
          "H": {"E","G"}
          }

깊이 우선 탐색

def dfs(graph, start, visited = set()): # 인자로 그래프, 시작 정점, 방문 정점을 받음
    if start not in visited: 
        visited.add(start) # start 정점을 방문
        print(start, end=" ")
        nbr = graph[start] - visited # start의 인접정점에서 방문 정점을 제외
        for v in nbr: # 방문정점을 제외한 start의 인접정점을 방문
            dfs(graph, v, visited)

• 스택을 사용하지 않고 순환 개념을 사용하여 깊이우선탐색을 진행
• 방문 정점을 제외한 인접정점을 방문할 때, 바로 v를 기준으로 순환함수를 실행하면서 깊은 부분을 우선적으로 탐색하는 깊이우선탐색 방식을 따름

너비 우선 탐색

def bfs(graph, start): # 인자로 그래프, 시작 정점을 받음
    visited = set([start]) # start 정점을 방문 정점 집합에 저장 및 집합 객체 생성
    queue = collections.deque([start]) # 큐처럼 사용할 덱 객체 생성 및 start 정점 삽입
    while queue: # 큐에 요소가 남아 있으면 계속 실행
        vertex = queue.popleft() # dequeue 실시
        print(vertex, end=" ") 
        nbr = graph[vertex] - visited # 인접정점에서 방문 정점 제외
        for v in nbr: # 남은 인접 정점들을 v를 큐에 삽입
            visited.add(v)
            queue.append(v)

• 큐를 사용하여 너비우선탐색을 진행
• 인접 정점들이 큐에 순서대로 삽입되고, 선입선출에 형태로 인접 정점들을 방문
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회하는 너비우선방식을 따름