[알고리즘] 그래프 탐색 기법을 코드로 이해하기

1. 그래프

그래프는 광범위한 분야에서 활용되고 있는 자료구조이다. 그러다보니 코딩테스트 문제 출제 1순위이다.
그래프는 정점과 간선의 집합으로 하나의 간선은 두 개의 정점을 연결한다.
그래프는 G=(V, E)로 표현하는데 간선에 방향이 있는 그래프를 방향그래프, 간선에 방향이 없는 그래프를 무방향그래프라고 한다.

V = 정점의 집합, E = 간선의 집합

2. 그래프 탐색

그래프에서는 너비우선탐색(BFS)과 깊이우선탐색(DFS) 방식으로 모든 정점을 방문할 수 있다.

그래프 탐색 예시

2.0 그래프 코드

G = {
    1: set([3, 5])
    2: set([3, 4, 6]),
    3: set([1, 2, 6]),
    4: set([2]),
    5: set([1]),
    6: set([2, 3])
}

2.1 BFS

BFS는 큐를 사용해 임의의 정점(a)에서 시작해 정점(a)의 이웃하는 모든 정점(b)을 방문하고, 방문한 정점들(b)의 이웃 정점들(c)을 모두 방문하는 방식으로 그래프를 탐색한다.

위키피디아 - BFS 예시

BFS 코드

from collections import deque

def bfs(graphs, start):
    que = deque([start]) # 탐색중인 큐
    visited = [false for _ in range(len(graphs) + 1) # 방문 여부 확인
    visited[start] = True
    print_list = [] # 방문 순서 저장할 리스트

    while que:
        current_node = que.popleft() # 현재 노드
        print_list.append(current_node) # 순서 저장

        for next_node in graphs[current_node]: # 이웃한 노드들 방문
            if not visited[next_node]: # 방문한 적 없는 노드라면
                visited[next_node] = True
                que.append(next_node) # 다음에 탐색하기 위해 큐에 넣기

    print(" ".join(print_list))

2.2 DFS

DFS는 스택으로 임의의 정점(a)에서 시작하여 이웃하는 하나의 정점(b)을 방문하고, 방문한 정점(b)의 이웃 정점(c)을 방문하며, 더 이상 방문할 정점이 없다면 이전 정점으로 돌아오는 식으로 그래프를 탐색한다.

위키피디아 - DFS 예시

DFS 코드

def DFS(graphs, start):
    stack = [start] # 탐색중인 스택
    visited = [false for _ in range(len(graphs) + 1) # 방문 여부 확인
    visited[start] = True
    print_list = [] # 방문 순서 저장할 리스트

    while stack:
        current_node = stack.pop() # 현재 노드
        print_list.append(current_node)

        for next_node in graphs[current_node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.extend(graphs[next_node))

    print(" ".join(print_list))