[Algorithm] 그래프 (Graph)
여러 노드(또는 정점, vertex) 들이 간선(edge, 또는 arc)으로 연걸된 추상 네트워크
이를 수식으로 표현하면,
G는 그래프, V는 노드의 집합이고 E는 간선의 집합이다.
이와 같은 그래프에서
V는 {a, b, c, d} , E는 {{a, b}, {b, c}, {c, d}, {d, a}} 이다.
그래프의 종류
무방향 그래프
- 방향이 없는 그래프
- 간선을 통해 노드는 양방향으로 갈 수 있다.
- 보통 노드 A, B가 연결되어 있을 경우 (A, B) 또는 (B, A)로 표기
방향 그래프
- 간선에 방향이 있는 그래프
- 보통 노드 A, B가 A -> B 방향일 경우, <A, B> 로 표기
가중치 그래프 (네트워크)
- 간선에 비용 또는 가중치가 할당된 그래프
연결 그래프
- 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우
비연결 그래프
- 무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 경우
사이클 (Cycle)
- 단순 경로의 시작 노드와 종료 노드가 동일한 경우
비순환 그래프 (Acyclic Graph)
- 사이클이 없는 그래프
완전 그래프
- 그래프의 모든 노드가 서로 연결되어 있는 그래프
평면 그래프
- 간선을 서로 횡단하지 않고 평면에 그릴 수 있는 그래프. 즉, 간선이 교차하지 않는다는 것을 뜻한다.
- 연결된 평면 그래프의 오일러 공식에 따르면, V - E + F = 2 (V: 노드 수 E: 간선 수 F: 면 수)
- 평면 그래프 예
이 그래프가 평면 그래프일까?
이렇게 표현 가능하다!
그래프 vs 트리
| 그래프 | 트리 | |
| 정의 | 노드와 노드를 연결하는 간선으로 표현되는 자료 구조 | 그래프의 한 종류. 방향성이 있는 비순환 그래프 |
| 방향성 | 방향 그래프, 무방향 그래프 모두 존재 | 방향 그래프만 존재 |
| 사이클 | 사이클 가능함. 순환 및 비순환 그래프 모두 존재 | 비순환 그래프로 사이클 존재 X |
| 루트 노드 | 존재 X | 존재 O |
| 부모 / 자식 관계 | 개념 존재 X | 개념 존재 O |
이웃 함수
모든 이웃 V의 컨테이너 또는 반복 가능한 객체이다.그래프를 표현하는 방법으로 크게 인접 행렬, 인접 리스트, 인접 다중 리스트가 있다.
인접 행렬
그래프 G = (V, E)를 n >= 1의 정점을 가진 그래프라고 하였을 때 그래프 G에 대한 인접 행렬의 크기는 n*n이며, a[n, n] 크기의 2차원 배열로 표현된다.a[n, n] 에서 a[i j]가 그래프에 표현된다면 1을 아니면 0의 값을 가진다.
예시
인접 리스트
n개의 정점을 각각에 대해 인접한 정점들의 리스트로 만드는 것이다.
리스트의 노드 구조를 정점(vertex) 필드와 주소(link) 필드로 구성해여야 정점 i에 대한 인접 리스트에 정점 i와 인접한 정점들을 나타내는 노드들을 포함시키게 할 수 있다.
각 정점의 리스트는 헤더 노드를 가지고 있고, 리스트 헤더들은 배열을 이용해 노드 번호를 오름차순으로 정렬하였다.
그러나 리스트 내의 노드 순서는 그 이외에 다른 특별한 의미를 갖지 않는다.
예시
인접 다중 리스트
무방향 인접 리스트의 표현에서 각 간선 (i, j)는 실제로 정점 i와 정점 j 두 개의 인접 리스트를 포함하게 된다. 즉, 하나의 간선은 두 개의 노드의 인접 리스트를 표현할 수 있다. 이러한 점을 사용해서 만든 것이 다중 리스트
노드를 여러 리스트들이 공유하는 리스트를 말한다.
예시
- 정점0 : E0 → E1
- 정점1 : E0 → E2 → E3
- 정점2 : E2 → E4
- 정점3 : E1 → E3 → E4
이웃 함수 구현 코드 참고
https://lgphone.tistory.com/75