<aside> 💡
[그래프 방문 순서]
</aside>
2차원 배열(행렬)로 그래프 연결 정보를 표현
$V * V$ 크기의 2차원 배열을 만들어, 정점 i와 j가 연결되어 있으면 matrix[i][j] = 1로 표시하는 방식
노드의 개수가 적거나, 그래프가 조밀(dense)할 때 사용하기 편리
공간 복잡도가 대체로 $O(N^2)$ (N은 노드 수)
인접행렬 만들기
import sys
sys.stdin = open('input.txt')
# --- 그래프 구성 (인접 행렬) ---
# 정점(V)과 간선(E)의 개수를 입력받음
V, E = map(int, input().split())
# 간선 정보를 하나의 리스트로 입력받음
data = list(map(int, input().split()))
# V+1 x V+1 크기의 2차원 리스트를 0으로 초기화
# (노드 번호를 1부터 사용하기 위해 V+1 크기로 생성)
adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]
# 8개의 간선 정보를 2개씩 짝지어 순회 (총 E번 반복)
for i in range(E):
# n1과 n2는 서로 연결된 두 정점을 의미 (인접 행렬의 인덱스 값으로 쓰임)
n1, n2 = data[i * 2], data[i * 2 + 1]
# n1과 n2가 연결되었음을 1로 표시
adj_matrix[n1][n2] = 1
# 무향 그래프이므로, 반대 방향도 연결되었음을 표시
adj_matrix[n2][n1] = 1
# --- 결과 확인 ---
for row in adj_matrix:
print(row)
# 인접 행렬
adj_matrix = [
# 0 1 2 3 4 5 6 7
[0, 0, 0, 0, 0, 0, 0, 0], # 0
[0, 0, 1, 1, 0, 0, 0, 0], # 1
[0, 1, 0, 0, 1, 1, 0, 0], # 2
[0, 1, 0, 0, 0, 0, 0, 1], # 3
[0, 0, 1, 0, 0, 0, 1, 0], # 4
[0, 0, 1, 0, 0, 0, 1, 0], # 5
[0, 0, 0, 0, 1, 1, 0, 1], # 6
[0, 0, 0, 1, 0, 0, 1, 0], # 7
]
<aside> 💡
알고리즘 문제에서는 메모리 효율성이 좋은 인접 리스트 방식이 더 선호되는 경우가 많음
</aside>
리스트를 사용하여 노드별로 연결된 정점들을 저장
각 정점마다 해당 정점과 연결된 다른 정점들의 목록을 리스트로 저장하는 방식
노드의 개수가 많지만 간선이 상대적으로 드문(sparse) 그래프에서 공간 절약 가능
공간 복잡도는 $O(N + E)$ (E는 간선 수)
인접 리스트 만들기
import sys
sys.stdin = open('input.txt')
# --- 그래프 구성 (인접 리스트) ---
# 정점(V)과 간선(E)의 개수를 입력받음
V, E = map(int, input().split())
# 간선 정보를 하나의 리스트로 입력받음
data = list(map(int, input().split()))
# V+1개의 빈 리스트를 가진 1차원 리스트를 생성
# (adj_list[i]는 i번 노드와 연결된 노드들의 목록이 됨)
adj_list = [[] for _ in range(V + 1)]
# 8개의 간선 정보를 2개씩 짝지어 순회
for i in range(E):
# n1과 n2는 서로 연결된 두 정점을 의미
n1, n2 = data[i * 2], data[i * 2 + 1]
# n1번 리스트에 n2를 추가
adj_list[n1].append(n2)
# 무향 그래프이므로, n2번 리스트에도 n1를 추가
adj_list[n2].append(n1)
# --- 결과 확인 ---
print(adj_list)
for i in range(1, V + 1):
print(f'{i}: {adj_list[i]}')
# 인접 리스트
adj_list1 = {
1: [2, 3], # 1번 정점과 연결된 정점들
2: [1, 4, 5], # 2번 정점과 연결된 정점들
3: [1, 7], # 3번 정점과 연결된 정점들
4: [2, 6], # 4번 정점과 연결된 정점들
5: [2, 6], # 5번 정점과 연결된 정점들
6: [4, 5, 7], # 6번 정점과 연결된 정점들
7: [6, 3], # 7번 정점과 연결된 정점들
}
# 또는 (0번 리스트는 안쓰기 위해 빈리스트 추가)
adj_list2 = [
[],
[2, 3],
[1, 4, 5],
[1, 7],
[2, 6],
[2, 6],
[4, 5, 7],
[6, 3],
]
adj_list[1]의 내용이 [2, 3]이라면, 1번 정점은 2번과 3번 정점에 연결되어 있다는 의미<aside> 💡
비선형 구조인 그래프에서는, 정점들을 빠짐없이 방문하기 위해 탐색(순회) 알고리즘이 필요하다
그래프 탐색에는 대표적으로 두 가지 알고리즘 ⇒ DFS, BFS가 있음