[DFS / BFS ] 깊이 우선 탐색, 너비 우선탐색

그래프의 구조를 이해하고 탐색 알고리즘인 DFS와 BFS를 적용하는 내용입니다.

그래프란?

노드와 노드 사이를 간선으로 연결하는 자료 구조 형태입니다. 예를 들어 노드는 도시 간선은 도로라고 생각하면 이해하기 쉽습니다.

그래프의 종류는 다양하게 있습니다. 방향이 있는 그래프와 방향이 없는 그래프, 가중치를 구하는 그래프, 모든 노드가 서로 연결되어 있는 그래프 등등 이 있지만 이것을 코드로 표현하고 해결하기 위해 어떤 방식으로 표현하는 지 설명하겠습니다.

 

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

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

아래에 그래프를 인접 행렬로 구현했을 때 인접 리스트로 구현했을 때를 설명하겠습니다.

그래프

인접행렬

인접행렬에서 중요한 점은 연결이 되어 있지 않은 노드를 무한대로 초기화해 작성합니다. 파이썬에서 코드를 작성할 경우 Math 에 있는 INF 를 이용하거나 큰 수로 초기화하여 사용합니다.

import math

# 서로 연결되어 있지 않은 노드 초기화 하는법
INF = 999999
INF = math.inf

graph = [[0,5,10],
         [5,0,INF],
         [10,INF,0]]
print(graph)

 

 

인접리스트

노드에 대한 정보를 차례대로 연결하여 저장합니다. 위에 그래프는 아래에 형태로 표현할 수 있습니다.

A노드는 B,C 노드와 연결되어 있으니 B, C와 해당 거리를 저장

B노드는 A 노드와 연결되어 있으니 A와 해당 거리 저장

C노드는 A 노드와 연결되어 있으니 A와 해당 거리 저장

인접리스트

 

graph = [[] for _ in range(3)]

#노드 A에 연결된 노드 정보
graph[0].append(("B",5))
graph[0].append(("C",10))

#노드 B에 연결된 노드 정보
graph[1].append(("A",5))

#노드 C에 연결된 노드 정보
graph[2].append(("A",10))

print(graph)

 

두 방식의 차이

인접 행렬 방식은 모든 관계를 저장해야 하므로 저장 개수가 많아지면 메모리 낭비가 커지게 됩니다. 반면 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 효율적으로 사용되게 됩니다. 하지만 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느립니다. 왜냐하면 특정 노드끼리 연결 상태를 확인하고 싶을 때 인접행렬 방식에서는 해당 위치를 찾기만 하면되지만 인접 리스트 방식은 앞에서부터 차례대로 확인하며 찾아야 하기 때문입니다.

 

이제 그래프를 가지고 탐색하는 알고리즘에 대해 설명하겠습니다.

DFS 란?

깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다.

1. 탐색 시작 노드를 스택에 저장한 후 방문을 처리합니다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 스택 추가 후 방문 처리, 없으면 최상단 노드를 꺼냅니다.

3. 2번 과정을 반복하다가 더 이상 방문할 노드가 없으면 종료합니다.

위 그래프에 대한 DFS 적용 알고리즘

1. 최상위 노드 1을 스택에 저장한 후 방문처리 하고 인접한 노드 2,7,4 중 가장 작은 노드 2를 스택에 넣고 방문 처리합니다.

2. 2에서 방문하지 않은 노드와 인접한 노드는 6,8이 존재하므로 가장 작은 노드 인 6을 스택에 넣고 방문 처리합니다.

3. 6에서 방문하지 않은 노드와 인접한 노드는 7이 존재하므로 7을 스택에 넣고 방문 처리합니다.

4. 7에 방문하지 않은 인접 노드가 없으므로 스택에서 7을 꺼냅니다.

5. 6에 방문하지 않은 인접 노드가 없으므로 스택에서 6을 꺼냅니다.

6. 2에 방문하지 않은 인접 노드 8이 존재하므로 스택에 8을 넣고 방문 처리합니다.

7. 8에 방문하지 않은 인접 노드가 없으므로 스택에서 8을 꺼냅니다.

8. 2에 방문하지 않은 인접 노드가 없으므로 스택에서 2을 꺼냅니다.

9. 1에 방문하지 않은 인접 노드 4이 존재하므로 스택에 4을 넣고 방문 처리합니다.

10. 4에서 방문하지 않은 노드와 인접한 노드는 3,5가 존재하므로 가장 작은 노드 인 3을 스택에 넣고 방문 처리합니다.

11. 3에서 방문하지 않은 노드와 인접한 노드는 5가 존재하므로 가장 작은 노드 인 5을 스택에 넣고 방문 처리합니다.

12. 방문하지 않은 남은 인접노드가 없으므로 모든 노드를 차례대로 꺼내면 다음과 같습니다.

1 -> 2 -> 6 -> 7 -> 8 -> 4 -> 3 -> 5

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

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


visit = [False] * 9

dfs(graph,1,visit)


#출력 내용 12678435

연결된 노드 순으로 그래프를 만들고 visit을 통해 방문했는지 체크할수 있도록 만든 후 dfs 함수에서 방문을 체크하면서 최대 깊이까지 재귀함수를 통해 방문합니다.

 

BFS 란?

너비 우선 탐색이라고 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 입니다.

1. 탐색 시작 노드를 큐에 저장한 후 방문을 처리합니다.

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

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

위 그래프에 대한 BFS 알고리즘

1. 시작 노드 1을 큐에 삽입하고 방문 처리합니다.

2. 인접 노드 2,4,7을 순서대로 큐에 삽입하고 방문 처리합니다.

3. 큐에서 2를 꺼낸 후 방문하지 않은 인접 노드 6, 8을 큐에 삽입 후 방문 처리 합니다.

4. 큐에서 4를 꺼낸 후 방문하지 않은 인접 노드 3,5를 큐에 삽입 후 방문 처리 합니다.

5. 방문하지 않은 남은 인접노드가 없으므로 모든 노드를 차례대로 꺼내면 다음과 같습니다.

1 -> 2 -> 4 -> 7 -> 6 -> 8 -> 3 -> 5

여기서 방문하지 않은 인접 노드가 없을 경우에는 무시합니다.

from collections import deque

def bfs(graph,start,visit):
    queue = deque([start])
    visit[start] = True
    while queue:
        v= queue.popleft()
        print(v,end=' ')
        for i in graph[v]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True




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


visit = [False] * 9

bfs(graph,1,visit)


# 출력 내용 1 2 4 7 6 8 3 5

 

deque를 이용해 BFS 를 구현하였습니다.  DFS와 차이점은 재귀함수로 구현하지 않았고 방문하는 노드를 모두 큐에 저장하고 하나씩 뽑으면서 다음 깊이의 노드를 체크하는 방식입니다.

 

DFS BFS 차이점

DFS 같은 경우 스택과 재귀함수를 이용해서 구현했고 BFS 는 큐와 반복문을 통해 구현하였습니다.

재귀함수로 구현하였기 때문에 깊이가 깊어지거나 복잡한 그래프에서는 속도가 느려지는 현상이 발생할 수 있습니다.