프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.
1. 인접 행렬
2. 인접 리스트
# 인접 행렬 방식 예제
INF = 99999999 # 무한의 비용 선언
# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
# ---------------------------------
# 인접 리스트 방식 예제
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)
인접 행렬
- 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비
인접 리스트
- 연결된 정보만을 저장해서 메모리를 효율적으로 사용
- 두 노드가 연결되어 있는지 확인하는게 인접 행렬보다 느림
DFS는 스택 자료 구조를 이용하여 동작 한다.
DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단.
O(N)
재귀 함수를 이용하면 매우 간결함.
# 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)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
큐 자료구조 이용함.
큐 사용해서 간단하다.
deque라이브러리를 사용하는 것이 좋으며 O(N)시간 소요.
일반적인 경우 실제 수행시간은 DFS보다 좋은 편.
from collections import deque
# BFS 메서드 정의
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
bfs(graph, 1, visited)