[알고리즘] 그래프 탐색을 위한 DFS와 BFS - 파이썬(Python)

그래프 표현

  그래프는 노드(Node)와 간선(Edge)로 표현되며 이때 노드를 정점(Vertex)라고도 한다.

프로그래밍에서 그래프는 '인접 행렬'과 '인접 리스트' 2가지 방식으로 표현할 수 있다. 

그래프 표현

• 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현하는 방식
  - 각 노드가 연결된 형태를 기록하여 저장

인접 행렬

INF = 999999999  # 무한의 비용 선언

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

print(graph)

 

• 인접 리스트 : 리스트로 그래프의 연결관계를 표현하는 방식 
  - 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

인접 리스트

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

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

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

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

print(graph)

 

인접 행렬 VS 인접 리스트

• 인접 행렬은 모든 연결 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비 but 노드1과 노드2의 연결을 graph[노드1][노드2]로 빠르게 확인 가능
• 인접 리스트는 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용 but 연결된 데이터를 하나씩 확인해야 하기 때문에 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림
• 특정 노드와 연결된 모든 인접 노드를 순회해야 하는 경우(DFS, BFS)는 인접 리스트 방식이 더 유리

 

DFS ( Depth-First Search )

  DFS (Depth-First Search)는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색한다.

DFS는 스택 자료구조를 사용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (pop)
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

# DFS 메서드 정의
def dfs(graph, v, visited):
    visited[v] = True # 현재 노드(v) 방문 처리
    print(v, end=" ")
    
    # 현재 노드와 연결된 다른 노드를 재귀적(스택 기반)으로 방문
    for i in graph[v]:
    	if not visited[i]:
    		dfs(graph, i, visited)
            
# 각 노드가 연결된 정보를 2차원 리스트로 표현
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드의 방문 처리를 위한 리스트
visited = [False] * 9

# DFS 함수 호출 (시작 노드: 1)
dfs(graph, 1, visited)

 

 

BFS ( Breadth-First Search )

  BFS ( Breadth-First Search )는 너비 우선 탐색이라고도 부르며, 그래프의 시작 노드와 가까운 노드부터 탐색하는 알고리즘이다.

BFS는 큐 자료구조를 사용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 하나 꺼내 해당 노드와 인접한 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고 방문 처리를 한다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    queue = deque([start]) # 큐 구현을 위해 deque 라이브러리 사용
    visited[start] = True # 시작 노드를 방문 처리
    
    # 큐가 empty될 때까지 반복
    while queue:
    	v = queue.popleft() # 큐에서 노드 하나 꺼냄
        print(v, end=' ')
        # 꺼낸 노드와 연결되고 아직 방문하지 않은 노드들을 큐에 모두 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
                
# 각 노드가 연결된 정보를 2차원 리스트로 표현
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드의 방문 처리를 위한 리스트
visited = [False] * 9

# DFS 함수 호출 (시작 노드: 1)
bfs(graph, 1, visited)

 

DFS / BFS 문제 유형

• 그래프의 모든 정점을 방문해야 하는 문제
  • DFS/BFS 두 방법 중 어느 것을 사용해도 무방하지만 한 정점과 연결된 모든 정점을 다 확인해야 한다면 DFS를 사용하는 것이 일반적
• 경로의 특징을 저장해야 하는 문제
  • 예를 들어, 숫자가 적혀있는 1에서 10까지 가는 경로를 구할 때 같은 숫자를 지나오면 안된다는 조건이 있는 문제와 같이 경로의 특징을 저장해야할 경우에는 DFS를 사용한다.
• 최단거리 문제
  • a정점부터 b정점까지 가는 최단거리를 구해야하는 경우에는 BFS가 유리하다. DFS를 사용할 경우, 처음 발견한 경로가 최단거리라는 보장이 없지만 BFS는 가장 먼저 찾아낸 경로가 곧 최단거리이기 때문이다.