Graph
정점와 간선의 집합
특징
2개 이상의 경로가 가능하다.
방향성이 있는 그래프와방향성이 없는 그래프로 나뉜다.
방향성이 있는 그래프
정점 A에서 정점 B로 가는 간선은<A, B>와 같이 표현한다.
A에서 B만 갈 수 있다는 뜻이다.
따라서<A,B>와<B, A>는 다른 의미이다.
방향성이 없는 그래프
정점 A와 정점 B를 연결한 간선은(A,B)와 같이 표현한다.
(A,B)와(B,A)는 같은 의미이다.
엣지에 가중치를 부여할 수 있다.
이를가중치 그래프라고 한다. 네트워크라고도 한다.
사이클이 존재할 수도 있고 존재하지 않을 수도 있다.
그래프에 속해 해 있는 모든 점점이 서로 연결되어 있는 그래프를
완전 그래프라고 한다.무방향 완전 그래프의 경우 정점과 간선 수는 다음과 같다.
정점 수: n이면 간선의 수: n * (n-1) / 2
구현 방법
인접리스트(Adjacency List)
그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프인 경우 사용
인접 리스트로 그래프를 표현하는 것이 가장 일반적인 방법이다.
- 각각의 정점에 인접한 정점들을 리스트로 표시한다.
- 배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 동적 가변 리스트를 이용
0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5무방향 그래프이리 경우 (a,b) 간선은 두 번 저장된다.
- 한번은 a 정점에 인접한 간선을 저장하고 다른 한 번은 b에 인접한 간선을 저장한다.
장점
- 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.
- 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다.
단점
간선의 존재 여부를 알려면 해당 정점의 차수, 즉 정점에 연결된 간선의 수 만큼 시간이 필요하다.
인접 행렬(Adjacency Matrix)
그래프에 간선이 많이 존재하는 밀집 그래프인 경우 사용
인접 행렬은 NxN boolean 행렬로써 matrix[i][j] 가
true면 i -> j 의 간선이 있다는 뜻만약 정점의 수가 N 이라면 항상 NxN 개의 메모리 공간이 필요하다.
인접한 노드를 찾기 위해서 모든 노드를 순회해야해서 효율성이 인접리스트에 비해서 떨어진다.
장점
- 간선 존재의 여부를 O(1) 만에 알 수 있다.
- 정점의 차수는 O(n) 만에 알 수 있다.
단점
- 특정 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 순회해야 한다.
- 그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다. : 인접 행렬 전체 순회
그래프를 순회하는 방법
DFS
임의의 정점으로부터 연결되어있는 한 정점으로 우선 탐색하는 알고리즘
모든 노드를 방문하고자 하는 경우에 사용한다.(완전탐색)
BFS
임의의 정점으로부터 연결되어있는 모든 정점을 우선 탐색하는 알고리즘
두 노드 사이의 최단 경로를 알고 싶을 때 사용한다.
