개요
알고리즘 문제 유형에 BFS, DFS는 빠질 수 없는 단골이기 때문에 글로 남기며 정리하고 기억하기 위해 작성합니다. 그래프의 개념, 용어, 자료구조로 표현한 그래프에 대해서 알아봅니다.
개념
그래프란?
두 개의 집합에 의해서 정의되는 구조이다.
그래프는 세 가지 종류가 있다.
- 무방향 그래프
- 방향 그래프
- 가중치 그래프
무방향 그래프, G = (V, E)
- V : 노드(node) 혹은 정점(Edge)
- E : 노드쌍을 연결하는 에지(edge) 혹은 링크(Link)
- 개체(object)들 간의 이진관계를 표현
- n = |V|, m = |E|
- edge의 방향이 없음 ( (1,2) == (2,1) )
- 일반적으로 두 정점을 연결하는 edge는 하나라고 가정함
- 스스로를 연결하는 self-edge 도 없다고 가정
** V, E 란?
V : 정점들의 집합
E : 정점과 정점을 연결하는 edge들의 집합
방향 그래프, 가중치 그래프
그래프의 표현
그래프의 표현이라함은 프로그램 내부에서 그래프를 어떠한 자료구조로 표현하느냐를 의미하는 것임. 두 가지가 있는데 인접행렬과 인접리스트 가 있음.
- 인접행렬 (adjacency matrix)
- 인접리스트 (adjacency list)
인접행렬
- 일반적으로 0 ~ 1 까지 넘버링하여 값 표현
- n * n 이차원 배열로 표현하는 방법
- 3 -> 4 edge는 없으므로 0인 것을 확인할 수 있다.
- 대칭행렬이다, 즉 (6행 7열의 값)과 (7행 6열)의 값은 같다.
인접행렬에서 `어떤 노드 v에 인접한 노드 찾기`에 소요되는 시간은 O(n) 시간이다.
=> 해당 행의 모든 열을 뒤지면서 1인 값을 찾아야 하기 때문.
인접행렬에서 `어떤 에지 (u, v)에 존재하는지 검사`하는데 소요되는 시간은 O(1) 시간이다.
=> 그 행렬 값만 보면 되기 때문
인접리스트
노드개수는 2m 개이다 => 정점 2와 5를 봤을 때 2 -> 5, 5 ->2 둘다 성립하기 때문에 edge 개수 * 2 가 성립된다.
이 때 저장공간은 정점 갯수(n) + 엣지 개수(2m) 이며 공간복잡도를 Big O로 표기할 때 상수는 생략한다.
최악의 경우는 O(n^2) 이다.
인접리스트에서 `어떤 노드 v에 인접한 노드 찾기`에 소요되는 시간은 O(degree(v)) 시간이다.
=> 해당 정점에 연결된 모든 노드의 개수를 degree(v) 라고 하는데 이때, 시간복잡도는 해당 연결리스트를 모두 읽는 시간이 된다.
=> 최악의 경우 O(n^2) 이다. (모든 정점이 서로 연결된 경우)
인접리스트에서 `어떤 에지 (u, v)에 존재하는지 검사`하는데 소요되는 시간은 O(degree(u)) 시간이다.
=> 위와 마찬가지로 해당 리스트에 연결된 모든 노드들을 읽는데 소유되는 시간이다.
방향그래프 에서의 표현
- 인접행렬은 비대칭 => 3->5 로 가는 엣지 존재 (1), 그 반대는 존재 X (0)
- 인접 리스트는 m개의 노드를 가짐
가중치 그래프의 인접행렬 표현
- 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장 => 1은 값을 나타내는 절대적인 값이 아님 => 그저 노드의 존재유무를 나타내는 값일 뿐.
- 에지가 없을 때 혹은 대각선 :
- 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서
- 예: 가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 무한대, 대각선은 0.
- 예: 만약 가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 무한대
경로와 연결성
- 무항뱡 그래프 G= (V, E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할 때 v와 u는 서로 연결되어 있다고 말함
- 경로란 어떤 정점에서 에지들을 따라서 다른 정점까지 가는 길을 의미함.
- 모든 노드 쌍들이 서로 연결된 그래프를 연결된(connected) 그래프라고 한다.
- 연결 요소 (connected component)
- 아래 그림에선 3개의 연결 요소로 구성되어 있다.
- 다른 컴포넌트들과 독립적인 상태.
출처
권오흠 교수님의 알고리즘 강의 (www.youtube.com/watch?time_continue=480&v=hiW1KAyN1sc&feature=emb_title)
댓글