Soyulia's Blog

[자료구조]그래프 순회

Soyulia's photo
Soyulia
·

2 min read

목표 : 깊이 우선 탐색(DFS) , 너비 우선 탐색(BFS)개념과 기본 구현 코드를 알아보자.

그래프 순회

  • 순회 : 모든 정점과 간선을 검사해서 그래프를 탐색하는 과정.

  • DFS, BFS : 그래프를 순회하는 알고리즘

✏️깊이 우선 탐색 (DFS)

  • Push -> 비었는지 확인 -> Pop(노드 방문)

  • 먼저 시작할 노드 0을 선택한다.

  • 0번을 push해주고 비었는지 확인 후 pop을 해주면서 인접한 요소들을 stack에 넣어준다.

  • 3번을 pop해주면서 인접 노드를 push해주는데 이미 push해준 노드는 이 단계를 생략한다. 즉, 5번만 push한다.

  • 5번을 pop해주면서 4,6을 push 해준다.

  • 이를 반복하면, 0,3,5,6,8,9,7,4,2,1 순서로 나온다.

  • 결과 값은 유일하지 않다.

  • 구현 코드

graph = [
    [],      # 0
    [2, 3],  # 1 
    [4, 5],  # 2
    [6],     # 3
    [2, 5],  # 4
    [2, 4],  # 5
    [3, 7],  # 6
    [6]      # 7
]

# 방문 정보를 기록하기 위한 리스트
visited = [False] * 8

def dfs(v):
    # 방문 표시
    visited[v] = True
    print(v, end=' ')
    # 그래프를 순환하면서 인접 노드들을 방문
    for i in graph[v]:
        # 만약 방문하지 않은 노드가 있다면
        if not visited[i]:
            # 탐색 시작
            dfs(i)

# 탐색 시작 노드 1을 넣어주며 dfs() 실행
dfs(1)

✏️너비 우선 탐색 (BFS)

  1. A가 큐에 들어가고 pop하면서 인점한 노드 BCD가 큐에 들어간다.

  2. B가 pop하면서 인접한 E가 큐에 들어간다.

  3. 이를 반복하면 A,B,C,D,E,F,G순서로 나오게 된다.

from collections import deque

graph = [
    [],      # 0
    [2, 3],  # 1 
    [4, 5],  # 2
    [6],     # 3
    [2, 5],  # 4
    [2, 4],  # 5
    [3, 7],  # 6
    [6]      # 7
]

visited = [False] * 8

def bfs(v):
    # 큐 생성 및 큐에 시작 노드 삽입
    q = deque()
    q.append(v)
    # 아직 방문해야 하는 노드가 있다면
    while q:
        # 큐에서 노드를 꺼내서 x에 저장
        x = q.popleft()
        print(x, end=' ')
        # 그래프를 탐색하다가 방문하지 않은 노드가 있다면
        for i in graph[x]:
            if not visited[i]:
                # 큐에 방문하라고 삽입하고 방문 처리
                q.append(i)
                visited[i] = True

bfs(1)

DFS

  • 재귀적인 특징, 백트래킹을 이용하여 모든 경우 하나씩 전부 탐색하는 경우

  • Graph 크기가 클 경우

  • Optimal한 답을 찾는 것이 아닌 경우

  • 경로의 특징을 저장해야 하는 경우(ex, 경로 가중치, 이동과정 제약)

BFS

  • 최단 거리 or 최단 횟수

  • Optimal 한 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최단 거리

  • 탐색의 횟수를 구해야하는 경우