[TIL] 그래프 종류와 표현 방식
그래프
연결되어 있는 객체 간의 관계를 표현하는 비선형 자료 구조
그래프의 정의
그래프 G 는 (V, E) 로 표시한다 << 이 표기법을 언제 사용하는건지 질문 받았었는데
추가로 알아보니, 코드에서는 E (간선의 집합)을 직접적으로 사용하지 않고, 코드에서는
주로 V (정점의 집합)과 그래프의 인접 리스트나 인접 행렬을 통해 간선을 간접적으로 표현한다고 한다
다시 정리하면, (V, E) 는 그래프에서 V 라는 이름의 정점들이 있고,
그 정점을 사이를 연결하는 E 라는 이름의 간선들이 있다는 것을 의미한다
따라서 (V, E) 표기는 그래프의 구조를 간단하고 명확하게 나타낼 수 있기 때문에
알고리즘을 설계하거나 설명할 때 주로 사용한다고 한다
V - Vertex 정점, 여러 가지 특성을 가질 수 있는 객체, Node
E - Edge 간선, 정점들 간의 관계, Link
무방향 그래프에서 두 노드가 연결되어 있으면 두 노드는 인접하다고 표현 가능하다
무방향 그래프와 가중치 그래프에서는 A 와 B 가, A 와 C 가 인접하다, B 와 C 는 인접하지 않다
하지만 방향 그래프에서는 간선이 A 에서 B 쪽으로 방향을 갖고 있어서 A 가 B 로는 인접하고 B 에서 A 로는 인접하지 않다
A, C 도 마찬가지로 C 에서 A 로 방향을 갖고 있으므로 C 에서 A 로 인접하고 A 에서 C 로는 인접하지 않다
그래프 구현
1. 인접 행렬
인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현한 것으로,
2차원 리스트를 사용하여 인접 행렬을 구현할 수 있다
연결된 노드는 1, 연결되지 않은 노드는 0 으로 표시한다
무방향 그래프와 가중치 그래프의 경우 대각선을 기준으로 대칭이지만 방향 그래프는 그렇지 않다
또한 가중치 그래프의 경우 연결되어 있지 않은 경우 무한으로 표현한다
| 무방향 그래프 | 방향 그래프 | 가중치 그래프 | |||||||
| 연결 관계 | A | B | C | A | B | C | A | B | C |
| A | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 5 | 2 |
| B | 1 | 0 | 0 | 0 | 0 | 0 | 5 | 0 | INF |
| C | 1 | 0 | 0 | 1 | 0 | 0 | 2 | INF | 0 |
(그래프를 깔끔하게 나누고 싶었는데 티스토리 그래프는 어떻게 편집하는지 잘 모르겠다)
+ 그래프를 행렬로 구현했을 때 어디가 기준이고 어디가 방향인지 헷갈렸는데, 관례적으로 | 가 기준, ㅡ 가 방향 (대상) 이라고 한다
++ 연결되지 않은 노드들에 대해서 방향/ 무방향 그래프는 0 으로 표기하고, 가중치 그래프는 INF 로 표기하는 이유를 찾아봤다
가중치 그래프의 경우는 실제로 거리가 중요하기 때문에 연결되지 않은 상태를 무한대로 표시하지만
방향/ 무방향 그래프에서는 경로 존재 여부만 중요하기 때문에 0 으로 표기해도 충분하다고 한다
인접 행렬 코드 구현
무방향 그래프
graph = [
[0, 1, 1],
[1, 0, 0],
[1, 0, 0]
]
print(graph[0][1]) # 1 출력
print(graph[2][1]) # 0 출력방향 그래프
graph = [
[0, 1, 0],
[0, 0, 0],
[1, 0, 0]
]
print(graph[0][2]) # 0 출력
print(graph[2][0]) # 1 출력가중치 그래프
INF = 21470000000
graph = [
[0, 5, 2],
[5, 0, INF],
[2, INF, 0]
]
print(graph[0][1]) # 5 출력
print(graph[1][2]) # 21470000000 출력
2. 인접 리스트
그래프에서 각 노드에 연결된 다른 노드들을 리스트로 표현하는 방식
각 노드마다 해당 노드와 연결된 노드들의 정보를 리스트나 배열로 저장해서
노드 간의 연결 관계를 효율적으로 표현하는 방법
무방향 그래프
방향 그래프
가중치 그래프
인접 리스트 코드 구현
무방향 그래프
# 인접 리스트 초기화
graph = [[] for _ in range(3)]
# A에서 B, C로의 연결
graph[0].append(1) # A -> B
graph[0].append(2) # A -> C
# B에서 A로의 연결
graph[1].append(0) # B -> A
# C에서 A로의 연결
graph[2].append(0) # C -> A
# graph[0] (A)에 연결된 모든 노드 출력
print("노드 A의 연결:")
for node in graph[0]:
print("노드", node)
# 출력 결과
# [[1, 2], [0], [0]]
가중치 그래프
# 인덱스 A, B, C 를 각각 0, 1, 2 로 표기
graph = [[] for _ in range(3)]
# A 에서의 연결을 가중치를 포함하여 튜플로 저장
graph[0].append((1, 5))
graph[0].append((2, 2))
# B 에서 A 연결을 가중치 포함하여 튜플로 저장
graph[1]. append((0, 5))
# C 에서 A 연결을 가중치 포함하여 튜플로 저장
graph[2].append((0, 2))
# graph[0] (A) 에 연결된 모든 노드와 그 가중치를 출력
# 노드 A 가 연결된 노드 B 와 C 의 정보를 출력
for i in range(len(graph[0])):
print("노드", graph[0][i][0], ", 가중치", graph[0][i][1])
# 출력 결과
# 노드 1 , 가중치 5
# 노드 2 , 가중치 2
인접 행렬과 인접 리스트의 차이
| 인접 행렬 | 인접 리스트 | |
| 특징 | 모든 관계를 저장한다 | 연결된 노드에 대한 정보만 저장한다 |
| 장점 | 두 노드의 연결 정보를 빠르게 탐색할 수 있다 | 간선 개수에 비례하는 메모리만 차지한다 |
| 단점 | 그래프에 대한 정보가 커질수록 메모리 낭비가 심하다 | 두 노드에 대한 연결 정보를 얻는 속도가 느리다 |
+ 그래프 탐색 알고리즘은 DFS, BFS 가 있고 내일 공부할 예정