그래프의 기본
그래프를 표현하는 방식은 다음과 같습니다.
G = (V, E)
이는 그래프 G는 한쌍의 (V,E) 라고 표현가능하기도 합니다.
여기서 V는 정점(vertex) 집합이고 E는 엣지(edge) 집합입니다.
이때 그래프는
1. 방향이 지정되거나 지정되지 않을 수 있음
방향 있으면 엣지에 화살표 그려지는 A directed graph 없으면 An undriected graph
2. 알고리즘의 실행 시간을 표현할 |V| 그리고 |E| 라고 보통 표현합니다. 각각 V와 E집합의 갯수입니다.
3. 알고리즘을 표현하는 두 가지 일반적인 방법: 인접 목록(Adjacency lists), 인접 행렬(Adjacency matrix)
방향이 있는 그래프 Incident Graph
diagraph, 즉 이중 그래프에서는 self-loof이 가능합니다.
정점에서 정점으로 스스로 간선 방향을 그릴 수 있습니다.
또한 이중그래프에서는 두 개의 정점이 최대 두 개의 간선을 그릴 수 있습니다.
일반적으로 각 정점은 숫자나 이름이 구분됩니다.
(2,1)이라면 2 정점에서 1정점으로 간선이 그려졌다고 보면됩니다.
방향이 없는 그래프 Undirected Graph
방향이 없는 그래프는 방향이 없는 간선들로 이뤄져있습니다.
간선들은 방향이 없으므로 선으로만 표시됩니다.
self loof가 금지되어있습니다.
간선 (u,v)는 간선 (v, u)와 같습니다. 방향이 같기 떄문입니다.
인접 Adjacency
(u,v) 쌍이 간선으로 이뤄져있다면 v 정점이 u 정점의 이웃이 됩니다.
무방향 그래프에서는 인접한게 대칭됩니다.
u가 v랑 인접하다면 v도 u랑 인접합니다.
방향이 있는 그래프에서는 인접이 대칭되지 않습니다.
인접 리스트와 인접 행렬로 그래프를 표현합니다.
Adjecency List, Adjecency Matrix.
인접 리스트 표현
무방향 그래프일경우 리스트들의 방향이 저장됩니다.
시간 복잡도는 O(V + E)입니다.
사진에 |V| 리스트의 배열 Adj이 1~5까지 5개가 있는데요.
각각 Adj 하나당 정점 하나라고 보시면 됩니다.
그럼 |V| 는 5가 됩니다.
(u, v) ∈ E
이 수식이 사진에 해당하는 상황입니다.
(u, v), 즉 u와 v를 연결하는 간선이 모든 간선의 집합인 E에 포함된다는 말입니다.
1번 정점을 예시로 들면 u = 1이 되고 연결되어있는 v들이 2, 5가 있습니다.
(1, 2) ∈ E
(1, 5) ∈ E
이렇게 표현됩니다.
인접 리스트의 성능
공간 Space : (V + E)
Vertex와 Edge의 갯수를 합친만큼 공간을 차지합니다.
참고 : degree(u)는 정점 u의 리스트 길이입니다.
같은 말로는 정점 u의 인접한 간선의 갯수들입니다.
시간 Time ->
to list all vertices adjacent to u
정점 u에 연결된 인접한 정점들을 나열하는데 걸리는 시간 :
Θ(degree(u))
시간 Time ->
to determine if (u, v) ∈ E
두 정점 u와 v가 연결되어있는지 확인하는데 걸리는 시간:
O(degree(u))
u의 리스트를 처음부터 끝까지 다 살펴봐야하기 때문
예) 1번 2번 연결되있는지 확인하려면 1번 리스트의 [2, 5] 요소를 다 확인
인접 행렬 (Matrix) 표현
|V| x |V| 행렬 : O(V²) 시간 복잡도
(i, j) 항목은 간선이 있으면 1이고 없으면 0입니다.
즉, i 정점과 j 정점이 연결되어있으면 1 아니면 0입니다.
인접 행렬의 성능
공간 Space : Θ(V²)
V x V 크기의 행렬이 필요하기 때문입니다.
대체로 이전의 인접 리스트보단 많은 공간이 필요합니다.
시간 Time ->
to list all vertices adjacent to u
정점 u에 연결된 인접한 정점들을 나열하는데 걸리는 시간 :
Θ(V)
u번째 행을 처음부터 끝까지 봐야하기 때문입니다.
V개의 열을 확인해야하기 때문에 V 시간이 듭니다.
대체로 인접 리스트보다 더 오래 걸립니다.
시간 Time ->
to determine if (u, v) ∈ E
두 정점 u와 v가 연결되어있는지 확인하는데 걸리는 시간:
Θ(1)
A[u][v] 번째에 1인지 0인지만 확인하면 되기 때문에 1입니다.
상수시간이기도하고 당연히 인접 리스트보다 더 빠릅니다.
u의 리스트를 처음부터 끝까지 다 살펴봐야하기 때문
예) 1번 2번 연결되있는지 확인하려면 1번 리스트의 [2, 5] 요소를 다 확인
가중치 그래프 저장 가능
0,1 대신 실제 가중치 값을 저장할 수 있음
예: 도시 간 거리를 저장하는 경우, graph[1][2] = 150 # 1번-2번 도시 간 거리 150km
이렇게 가볍게 기본 그래프 개념을 살펴봤습니다.
더 자세한 그래프 순회에 대한 개념은 아래 글에서 확인 가능합니다.
https://kimyir.tistory.com/130
'그냥 개발글 > 알고리즘' 카테고리의 다른 글
| 그래프 Topological Sort 알고리즘 (0) | 2024.12.03 |
|---|---|
| 그래프 순회 BFS와 DFS (0) | 2024.12.01 |
| Radix Sort 기수 정렬 (0) | 2024.10.20 |
| Counting Sort 계수 정렬 (0) | 2024.10.20 |