DFS/BFS 탐색 알고리즘

 그래프 

그래프는 노드(정점)와 간선으로 표현됨.

그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것

 

그래프의 표현 방식 

 

1. 인접 행렬

 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식

 - 2차월 배열에 각 노드가 연결된 형태를 기록하는 방식 

 - 파이썬에서는 2차원 리스트로 구현 가능

 - 연결 되어 있지 않은 노드끼리는 무한의 비용이라고 작성

 

인접 행렬 방식 예제

INF = 999999999 #무한의 비용 선언

#2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph) #[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

 

2. 인접 리스트

 - 리스트로 그래프의 연결 관계를 표현하는 방식

 - 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

 - 인접 리스트는 '연결 리스트'라는 자료구조를 이용해 구현함

• C++, 자바에서는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공함
• 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공함

 -  파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 됨

 

인접 리스트 방식 예제

graph = [[] for _ in range(3)] #행이 3개인 2차원 리스트로 인접 리스트 표현

graph[0].append((1, 7)) #노드 0에 연결된 노드 정보 저장
graph[0].append((2, 5))
graph[1].append((0, 7)) #노드 1에 연결된 노드 정보 저장
graph[2].append((0, 5)) #노드 2에 연결된 노드 정보 저장

 

차이점

- 메모리 측면

  · 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨

  · 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용

 

노드 1과 노드 7이 연결되어 있는지 확인할 때 인접 행렬의 경우 grpah[1][7] 과 같이 바로 그 좌표를 통해 확인할 수 있음.

반면에 인접 리스트의 경우 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 함.

 

→ 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 메모리 공간의 낭비가 적음.

---

  DFS  

- DFS는 Depth First Search, 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 특정한 경로로 탐색하다가 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

- 동작 과정

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.

      방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

- 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리함

 

- DFS는 스택 자료구조에 기초함 → 구현이 간단함

- 데이터의 개수가 N개인 경우 시간복잡도는 O(N)

- DFS는 스택을 이용하므로 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 표현 가능

 

DFS 예제

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
	
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [], #대부분 노드 1부터 시작하므로 인덱스 0 비워둠
    [2, 3, 8], #노드 1과 인접한 노드
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]

visited = [False] * 9

dfs(graph, 1, visited) # > [1, 2, 7, 6, 8, 3, 4, 5]

---

  BFS  

- BFS는 Breadth First Search, 너비 우선 탐색이라고 부르며, 가까운 노드부터  탐색하는 알고리즘

- 선입선출 방식인 큐 자료구조 이용

- 동작 과정

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

step 6

 

step 7

BFS 예제

from collections import deque

def bfs(graph, start, visited):
    # Queue 구현을 위해 deque 라이브러리 사용
    queue = deque([start])

    # 현재 노드를 방문 처리
    visited[start] = True

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=" ")

        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 인접 리스트 방식
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 

# 정의된 BFS 함수 호출
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6

 

---

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용