그래프에서 "인접 (adjacent)하다" 라는 것은 두 vertex를 잇는 edge가 존재한다는 것을 의미한다. 즉, 두 vertex가 연결되어 있다는 뜻이다. 그래프에서 이렇듯 vertex간의 인접함을 나타내는 방식은 크게 2가지가 존재한다. 첫 째로는 인접 행렬 (Adjacency Matrix) 이 있고, 둘 째로는 인접 리스트 (Adjacency List) 가 존재한다. 이 중 인접 행렬에 대해서 다룬다.
인접 행렬이란 2차원 배열에 각 node가 연결된 형태를 저장하는 방법이다. 즉, 인접 행렬에서 [ i ][ j ] 는 vertex i 와 vertex j 간의 연결성을 나타내는 것이다. 이 때 2차원 배열의 [ i ][ j ] 에는 다음과 같은 값들을 저장한다.
- 1 : (edge에 가중치가 없는 경우) 노드 간 연결되었을 때
- 가중치 (cost) : (edge에 가중치가 존재하는 경우) 노드 간 연결되었을 때
- 0 : 해당 행, 열이 자기 자신을 가리키는 경우 ( = i와 j가 같은 경우 )
- ∞ : 노드 간 연결되지 않았을 때
그래프를 인접 행렬로 나타낸 예시는 다음과 같다.
위의 예시에서 만약 edge에 비용이 존재한다면 1 대신 비용을 인접 행렬에 저장하면 된다.
만약 방향이 없는 undirected graph라면 인접 행렬은 대각선을 기준으로 대칭이다. 반대로 방향이 있는 directed graph라면 대각선을 기준으로 대칭이지는 않을 것이다.
파이썬에서 인접 행렬은 2차원 리스트로 간단하게 구현할 수 있다.
위의 그래프에 해당하는 인접 행렬을 파이썬으로 구현한 소스코드는 아래와 같다.
'Algorithm' 카테고리의 다른 글
| DFS (1) - DFS (Depth-First Search) 란? (0) | 2023.07.30 |
|---|---|
| 자료구조 (Data Structure) (6) - 그래프 표현 방식 : 인접 리스트 (Adjacency List) (0) | 2023.07.30 |
| 자료구조 (Data Structure) (4) - 그래프 (Graph) 란? (0) | 2023.07.30 |
| 재귀 함수 (3) - 재귀 함수의 대표적인 예 : 팩토리얼 (Factorial) (0) | 2023.07.30 |
| 재귀 함수 (2) - 재귀 함수의 종료 조건 (0) | 2023.07.30 |
