사담 공간
정말 오랜만에 블로그 포스팅을 한다... 학기 중엔 사실 시간이 너무 없기도 했고 ㅠㅠ
알고리즘 파트까지는 이번 방학 중에 끝내보자!!
알고리즘 파트부터는 다음 서적을 참고했다
https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844
Introduction to Algorithms, 3rd Edition (The MIT Press): Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Cli
""Introduction to Algorithms, " the 'bible' of the field, is a comprehensive textbook covering the full spectrum of modern algorithms: from the fastest algorithms and data structures to polynomial-time algorithms for seemingly intractable problems, from cl
www.amazon.com
키워드
#그래프 #간선 #엣지 #정점
1. 그래프의 개념
사실 이전 포스팅 트리에서 그래프의 개념에 대해서 간략히 다뤘었다.
(트리의 개념에도 그래프의 정의가 들어가기 때문에..)
지난 번에 다뤘던 내용을 바탕으로 다시 한번 살펴보자.
출처 : https://news.seoul.go.kr/traffic/archives/1551
그래프는 정점 (Vertex) 과 간선 (Edge) 로 이루어진 자료구조이다.
(정점을 Node로 지칭하는 경우도 있는 듯 하나 본 포스팅에서는 혼동을 막기 위해 정점, Vertex로 용어를 통일하도록 하겠다)
트리 또한 정점과 간선으로 이루어져 있으므로 그래프의 일종이라고 말했었다!
그래프의 정의에 대해서 좀 더 자세히 알아보도록 하자.
그래프의 정의
$$Graph G = (V, E)$$
- V : 공집합이 아닌 정점의 집합
- |V| : 그래프를 구성하는 정점의 개수
- E : 간선의 집합
- |E| : 그래프를 구성하는 간선의 개수
각 간선은 하나, 혹은 두 개의 정점을 연결한다.
- 이 때 연결된 정점은 간선의 엔드포인트(=endpoint)라고 한다
- 정점을 연결하는 간선은 엔드포인트를 연결(=connect)한다고 지칭하며 두 정점의 관계를 나타낸다
- 또한, 간선으로 연결되어 있는 두 정점은 인접하다(=adjacent)고 표현한다.
- N(v) : 정점 v의 이웃 정점의 집합
- 만약 정점 A가 V (정점의 집합) 의 부분집합이라면, N(A) 는 부분집합 A에 속하는 적어도 하나의 정점에 인접한 그래프의 모든 정점의 집합을 나타낸다.
$$N(A) = \cup_{v \in A} N(v) $$
- deg(v) : 무향 그래프에서 정점 v의 차수(=degree)는 정점 v에 수반되는 간선의 개수이다.
- 단, 루프는 2개의 간선으로 취급된다
정점의 차수, 이웃에 대한 이해
예제 문제를 통해 정점의 차수와 이웃을 이해해보자.
다음 그래프 G, H에서 각 정점의 차수, 이웃을 구하라.
<풀이>
- 그래프 G
- 각 정점의 차수
- deg(a) = 2
- deg(b) = deg(c) = 4
- deg(d) = 1
- deg(e) = 3
- deg(g) = 0
- 각 정점의 이웃
- N(a) = {b,f}
- N(b) = {a,c,e,f}
- N(c) = {b,d,e,f}
- N(d) = {c}
- N(e) = {b,c,f}
- N(f) = {a,b,c,e}
- N(g) = null
- 각 정점의 차수
- 그래프 H
- 각 정점의 차수
- deg(a) = 4
- deg(b) = 6
- deg(c) = 1
- deg(d) = 5
- deg(e) = 6
- 각 정점의 이웃
- N(a) = {b, d, e}
- N(b) = {a, c, d, e}
- N(c) = {b}
- N(d) = {a, b, e}
- N(e) = {a, b, d}
- 각 정점의 차수
의사코드에서 그래프의 표현
- 알고리즘이 |VE| 시간 내에 실행된다는 것은 O(|V||E|) 를 나타낸다
- G.V : 정점 집합
- G.E : 간선 집합
그래프 관련 기타 용어
책에서 언급된 내용. 간략하게 짚고 넘어가자!
- simple graph : 각 간선이 두 개의 다른 정점을 연결하며, 두 개 이상의 간선이 같은 정점 쌍을 연결하지 않는다
- Multigraphs : 위의 simple graph 정의와는 다르게, 두 개 이상의 간선이 같은 정점 쌍을 연결할 수 있다
- 예를 들어 m개의 다른 간선이 정점 u, v를 연결할 경우, {u, v} 는 다중성 m을 가진 간선 (=edge of multiplicity m) 이라고 지칭한다.
- 다중 간선 : https://mathworld.wolfram.com/MultipleEdge.html
- loop : 스스로를 가리키는 간선을 순환간선, 루프 (=loop) 라고 지칭한다.
- pseudograph : 루프와 다중 간선을 모두 포함할 수 있는 non-simple graph이다
| 용어 | 간선 유형 | 다중 간선 허용 | 루프 허용 |
| Simple Graph | 무향 | X | X |
| Multigraph | 무향 | O | X |
| Psuedograph | 무향 | O | O |
| Simple directed Graph | 유향 | X | X |
| Directed multigraph | 유향 | O | O |
| Mixed Graph | 유향 & 무향 | O | O |
Courtesy: Discrete Mathematics and Applications by Rosen
유향 (Directed) 그래프 VS 무향 (Undirected) 그래프
그래프가 방향성을 가지고 있는지에 다른 그래프 분류 방법
방향이 있는 유향그래프의 경우 정해진 특정 방향으로만 노드 순회가 가능하다
순환 (Cyclic) 그래프 VS 비순환 (Acyclic) 그래프
순환 그래프는 첫 번째 정점이 마지막 정점에 해당하도록 경로를 형성할 수 있는 그래프를 의미하고, 비순환 그래프는 그렇지 않은 경우의 그래프를 의미한다.
그러면 일부 정점만 순환 가능한 경우는? 경로에서 꼭짓점이 겹치는 경우는?
헷갈리니까 좀 더 깊게 파보자.
보다 세밀한 정의로 들어가보면, 순환의 정의가 "첫 번째 정점이 마지막 정점에 해당하도록 경로를 형성할 수 있는 그래프" 이외에도 "꼭짓점이 중복될 수 없다" 는 조건이 존재한다는 것을 알 수 있다.
(꼭짓점이 중복될 수 없으므로, 변 또한 중복될 수 없다)
아래는 기본적으로 무향 그래프에서의 정의이고, 유향 그래프의 경우 방향에 따른 경로가 이를 준수하여야 한다.
- walk : 정점과 간선이 교대로 나타나는 시퀀스. 시퀀스의 처음과 끝은 서로 다른 정점이다
- path : 정점이 중복되지 않는 walk
- trail : 간선이 중복되지 않는 walk
- closed walk : 시작 정점과 끝 정점이 같은 walk
- closed trail = Tour
- closed path = Cycle
| 용어 | 시작 정점 = 마지막 정점 | 변이 겹칠 수 없음 | 꼭짓점이 겹칠 수 없음 |
| walk | X | X | X |
| trail | X | O | X |
| path | X | O | O |
| closed walk | O | X | X |
| closed trail | O | O | X |
| cycle | O | O | O |
[표 1] 1
출처 : https://ko.wikipedia.org/wiki/%EC%88%9C%ED%99%98_(%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0)
- BDEFDCB : closed walk이지만 정점 D가 중복되므로 순환이 아니다
- HAB : 시작 정점과 끝 정점이 다르므로 순환이 아니다
- HDGH : 순환
가중치 그래프 (Weighted Graph)
그래프 간선에 가중치가 존재하는 그래프를 의미한다.
이제 각각의 정의를 알아봤으니, 한번에 다음 용어를 이해할 수 있을 것이다.
- 유향 순환 그래프
- 유향 비순환 그래프 (DAG)
- 무향 순환 그래프
- 무향 비순환 그래프
말 그대로 "방향이 있고/없고" "순환이 존재하고/존재하지 않는" 그래프이다.
여기까지 읽었다면 몇 가지 의문점이 남을 것이다.
- 그래프에 순환이 있는지 없는지 어떻게 판단하는가?
- 왜 이런 식으로 그래프를 구분하는가?
- 그래프의 모든 정점을 순회한다면, 어떠한 방법으로 순회할 것인가?
이에 대해서는 구현 과정에서 차차 알아가보도록 하자.
2. 그래프의 표현 방법
그래프를 나타내기 위해서는 다음 두 가지 구현 방법을 이용할 수 있다.
각각의 표현 방법과 어떨 때 어떤 방법을 쓰는 것이 더 적절한지 알아보도록 하자.
인접 행렬 (Adjacency Matrix)
밀집 그래프를 표현할 때 이 방식을 사용한다.
밀집그래프 (dense graph) : 간선의 개수가 정점의 개수에 비해 많은 그래프
$$ |E| ~ |v|^2 $$
- |v| x |v| 행렬로 표현
- 원소 (i, j) = 1 : 정점 i와 정점 j 사이에 간선이 있음
- 원소 (i, j) = 0 : 정점 i와 정점 j 사이에 간선이 없음
$$ (i,j) \in E, a_{ij} = 1$$
$$ otherwise, a_{ij} = 0$$
- 유향 그래프
- 원소 (i, j) 는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄
- 가중치 있는 그래프
- 원소 (i, j) 는 1 대신 가중치를 가짐
표현 예시
- 무향 그래프
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 0 | 1 | 1 | 0 |
- 가중치 있는 무향 그래프
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 9 | 7 | 5 | 0 | 6 |
| 2 | 9 | 0 | 9 | 0 | 0 | 0 |
| 3 | 7 | 9 | 0 | 0 | 5 | 0 |
| 4 | 5 | 0 | 0 | 0 | 0 | 5 |
| 5 | 0 | 0 | 5 | 0 | 0 | 1 |
| 6 | 6 | 0 | 0 | 5 | 1 | 0 |
- 유향 그래프
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 0 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 |
| 6 | 1 | 0 | 0 | 0 | 1 | 0 |
- 가중치 있는 유향 그래프
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 8 | 7 | 5 | 0 | 6 |
| 2 | 9 | 0 | 6 | 0 | 0 | 0 |
| 3 | 0 | 9 | 0 | 0 | 5 | 0 |
| 4 | 8 | 0 | 0 | 0 | 0 | 5 |
| 5 | 0 | 0 | 0 | 0 | 0 | 2 |
| 6 | 6 | 0 | 0 | 0 | 1 | 0 |
- 만약 그래프 간선이 없는 경우라면?
| 1 | 2 | 3 | 4 | |
| 1 | inf | 8 | inf | 6 |
| 2 | 8 | inf | 9 | inf |
| 3 | inf | 9 | inf | inf |
| 4 | 6 | inf | inf | inf |
간선이 없는 경우 무한대 거리 (inf) 로 표현한다.
파이썬에서의 구현
바로 위의 그래프를 인접 행렬로 구현해보자
INF = 9999999
graph = [[INF,8,INF,6],
[8,INF,9,INF],
[INF,9,INF,INF],
[6,INF,INF,INF]]
인접 리스트 (Adjacency lists)
희소 그래프를 표현할 때 이 방식을 사용한다.
희소그래프 (sparse graph) : 간선의 개수가 정점의 개수에 비해 적은 그래프
$$ |E| << |v|^2 $$
- N개의 연결리스트로 표현
- i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해놓음
- 가중치 있는 그래프의 경우 가중치까지 보관
- 그래프 G = (V, E)의 인접 목록 표현은 V 안의 각 정점에 대해 |V| 에 대한 인접리스트로 구성되어 있다.
- Adj[u] : V에 속하는 임의 요소 u에 대한 인접리스트
- Adj[u]는 E에 속하고 (u, v) 를 연결하는 모든 간선을 포함한다
- 따라서 Adj[u] 는 그래프 내에 u와 인접한 모든 간선을 포함한다고 볼 수 있다
- 수도코드에서 임의요소 u에 대한 인접리스트는 G.Adj[u]로 표현한다
표현 예시
- 무향 그래프
- 가중치 있는 무향 그래프
파이썬에서의 구현
바로 위의 그래프를 인접 리스트로 구현해보자
graph = [[] for _ in range(6)]
# 각 노드에 연결된 노드 정보 저장
graph[0].append((2,9))
graph[0].append((3,7))
graph[0].append((4,5))
graph[0].append((6,6))
graph[1].append((1,9))
graph[1].append((3,9))
graph[2].append((1,7))
graph[2].append((2,9))
graph[2].append((5,5))
graph[3].append((1,5))
graph[3].append((6,5))
graph[4].append((3,5))
graph[4].append((6,1))
graph[5].append((1,6))
graph[5].append((4,5))
graph[5].append((5,1))
그래프의 모든 정점을 순회하기 위해서는 BFS(너비 우선 탐색), DFS (깊이 우선 탐색) 이 활용된다.
BFS, DFS의 개념과 구현에 대해서는 다음 포스팅에서 다뤄보도록 하겠다.
- https://www.wikiwand.com/ko/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0_%EC%9A%A9%EC%96%B4
https://aerocode.net/272
[본문으로]
'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글
| [알고리즘] 01. DFS & BFS (0) | 2023.09.11 |
|---|---|
| [알고리즘] 00. 자료구조 리마인드 (0) | 2023.09.11 |
| [자료구조] 08. 트리 (0) | 2022.08.29 |
| [자료구조] 07. 큐 (Queue) & 덱 (Dequeue) (0) | 2022.08.29 |
| [자료구조] 06. 스택 (Stack) (0) | 2022.08.25 |
