그래프란?
연결 관계를 표현하는 자료구조
트리는 그래프에 속하는 하위개념
- 트리 : 계층 관계를 표현하는 자료구조, 사이클 형성 X, 상하 관계(부모-자식 관계) 존재
- 그래프 : 보다 일반적인 연결 관계를 표현하는 자료구조, 사이클 형성 가능, 상하 관계 X
•
정점(데이터)를 간선(링크)로 연결한 형태의 자료구조
◦
정점(Vertex) : 그래프의 노드. 객체 하나 하나를 의미
◦
간선 or 링크(Edge) : 정점 간의 관계나 연결을 의미
그래프의 종류
•
그래프 = 연결관계를 표현하는 자료구조
◦
즉, 간선이 중요한 역할을 담당(간선이 연결관계를 표현하는 것이기 때문)
•
간선이 어떠한 형태로 정점을 연결하느냐에 따라 그래프의 종류가 달라짐(대표적으로 아래 4가지)
◦
무방향/방향 그래프
◦
무가중치/가중치 그래프
◦
연결/비연결 그래프
◦
서브 그래프
1. 무방향/방향 그래프
무방향 그래프
방향 그래프
•
무방향 그래프 : 두 정점을 연결하는 간선에 방향이 없는 그래프
◦
즉, 그냥 연결되어있다를 의미(무조건 양방향)
•
방향 그래프 : 두 정점을 연결하는 간선에 방향이 존재하는 그래프
◦
즉, 간선이 가리키는 방향으로만 이동 가능(단방향 or 양방향)
2. 무가중치/가중치 그래프
무가중치 그래프
가중치 그래프
•
가중치 그래프 : 간선에 가중치가 부여된 그래프
◦
비용 : 간선에 부여된 값인 가중치
◦
즉, 연결되어있다고 해도 비용에 차이가 있음
▪
EX : 통행료의 차이, 거리의 차이 등등
•
무가중치 그래프 : 간선에 가중치가 부여되지 않은 그래프
◦
즉, 그냥 연결되어있음을 의미
3. 비연결/연결 그래프
G1 : 연결 그래프
G2 : 비연결 그래프(0에서 다른 정점으로 가는 경로가 없음)
G3 : 비연결 그래프(0에서 2로 가는 경로가 없음)
•
연결 그래프 : 임의의 두 정점 사이를 잇는 경로가 있는 그래프
◦
아무 두 정점을 골라 경로를 확인했을 때, 경로가 있으면 연결 그래프
•
비연결 그래프 : 임의의 두 정점 사이를 잇는 경로가 없는 그래프
◦
아무 두 정점을 골라 경로를 확인했을 때, 경로가 없으면 연결 그래프
4. 서브 그래프(= 부분 그래프)
•
특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프
결론
•
그래프의 종류는 여러 가지인데, 방향 그래프라고 해서 무가중치이거나 가중치 그래프가 아닌게 아님. 두 가지가 섞인 그래프일 수 있음
그래프 표현 방식
•
그래프 구현 방식에는 크게 2가지가 존재 :
◦
그래프를 인접행렬로 표현하는 방법 → 이차원 배열을 기반으로 그래프 구현
◦
그래프를 인접리스트로 표현하는 방법 → 연결 리스트를 기반으로 그래프 구현
1. 인접행렬(Adjacency Matrix) 기반 표현
•
N x N 크기의 행렬로 그래프를 표현하는 방법
◦
N : 정점의 개수
◦
<행, 렬> : <출발 정점, 도착 정점>
▪
연결된 경우 → 1 / 연결 안 된 경우 → 0
▪
가중치가 있는 경우 → 특정 행렬의 값을 비용으로 설정
2. 인접리스트(Adjacency List) 기반 표현
•
특정 정점과 연결된 정점들을 연결리스트로 표현하는 방법
◦
각 정점마다 연결 리스트를 가짐
▪
연결리스트에 특정 노드가 있다 → 해당 노드가 연결되어있음을 의미
▪
가중치가 있다 → 연결리스트의 한 노드를 (노드 번호, 비용) 형태로 함께 표현
두 방식의 장단점
인접행렬 기반 그래프
장점•
간선 존재 여부 확인이 빠름[O(1)] : 그래프의 행렬 인덱스로 바로 접근하면 되니까
•
구현이 단순, 디버깅이 쉬움
•
직관적
단점•
메모리 낭비 : 정점이 많고 간선이 적은 경우(=희소 그래프)에도 (정점 개수 x 정점 개수) 공간 사용
•
모든 인접 정점을 찾는 데 느림[O(V)] : 연결되지 않은 노드도 매번 확인해야함
인접리스트 기반 그래프
장점•
메모리 효율적 : 실제 존재하는 간선 수만큼만 저장[O(V + E)]
•
인접 노드 순회가 빠름 : O(인접 노드 수)
•
큰 그래프에서 적합(특히 희소 그래프)
단점•
간선 존재 여부 확인이 느림[O(인접 노드 수)]
Q) 인접 노드 순회가 빠른데, 왜 간선 존재 여부 확인이 느리다는걸까요? 동일한 의미 아닌가요?
•
디버깅 시 확인 불편
•
직관적이진 않음
코드로 확인해볼까요?
1. 무방향 + 무가중치 그래프
인접행렬 표현
N = 4
graph = [[0] * N for _ in range(N)]
edges = [(0, 1), (1, 2), (2, 3)] # (출발노드, 도착노드)
for u,v in edges:
graph[u][v] = 1
graph[v][u] = 1
print(graph)
Python
복사
인접리스트 표현
N = 4
graph = [[] for _ in range(N)]
edges = [(0, 1), (1, 2), (2, 3)] # (출발노드, 도착노드)
for u,v in edges:
graph[u].append(v)
graph[v].append(u)
print(graph)
Python
복사
2. 무방향 + 가중치 그래프
인접행렬 표현
N = 4
graph = [[0] * N for _ in range(N)]
edges = [(0, 1, 5), (1, 2, 3), (2, 3, 2)] # (출발노드, 도착노드, 가중치)
for u,v,weight in edges:
graph[u][v] = weight
graph[v][u] = weight
print(graph)
Python
복사
인접리스트 표현
N = 4
graph = [[] for _ in range(N)]
edges = [(0, 1, 5), (1, 2, 3), (2, 3, 2)] # (출발노드, 도착노드, 가중치)
for u,v,weight in edges:
graph[u].append((v,weight))
graph[v].append((u,weight))
print(graph)
Python
복사
3. 방향 + 무가중치 그래프
인접행렬 표현
N = 4
graph = [[0] * N for _ in range(N)]
edges = [(0, 1), (1, 2), (2, 3)] # (출발노드, 도착노드)
for u,v in edges:
graph[u][v] = 1
print(graph)
Python
복사
인접리스트 표현
N = 4
graph = [[] for _ in range(N)]
edges = [(0, 1), (1, 2), (2, 3)] # (출발노드, 도착노드)
for u,v in edges:
graph[u].append(v)
print(graph)
Python
복사
4. 방향 + 가중치 그래프
인접행렬 표현
N = 4
graph = [[0] * N for _ in range(N)]
edges = [(0, 1, 5), (1, 2, 3), (2, 3, 2)] # (출발노드, 도착노드, 가중치)
for u,v,weight in edges:
graph[u][v] = weight
print(graph)
Python
복사
인접리스트 표현
N = 4
graph = [[0] * N for _ in range(N)]
edges = [(0, 1, 5), (1, 2, 3), (2, 3, 2)] # (출발노드, 도착노드, 가중치)
for u,v,weight in edges:
graph[u].append((v,weight))
print(graph)
Python
복사
참고자료