Graph

그래프

무방향 그래프 G에 대해서 G = (V,E) 로 표기할 수 있다

여기서

V는 vertex, node로 불리는 정점

E는 edge, link로 불리는 정점을 잇는 간선을 나타낸다

위와 같은 그래프는

V = {1,2,3,4,5,6,7,8}

E = {(1,2), (1,3), (2,3), ..., (7,8)}

n = 8, 정점 개수

m = 11, 간선 개수

으로 나타낼 수 있으며 위와 같이 (1,2) (2,1)이 동일하다고 보는 것이 무뱡항 그래프이다

위와 같은 그래프는 (u,v) 와 (v,u)가 같지 않은, 방향 그래프라고 하고

가중치 그래프는 무방향, 방향 그래프 모두 될 수 있으며 간선에 가중치를 부여한 것을 가중치 그래프라고 한다

그래프의 표현

이러한 그래프들은 프로그래밍에서 어떻게 나타낼 수 있을까?

인접행렬

정점 개수 n의 그래프는 n*n 행렬로 나타낼 수 있다 행렬은 알다시피 2차원 배열로 나타낼 수 있으니

위에서 본 정점의 개수가 8개인 그래프를 2차원 배열로 나타내보면 다음과 같다

인접행렬로 나타낸 그래프의 연산 시간

저장 공간 : O(n^2)

v에 인접한 노드 찾기 : O(n)

edge (u,v) 노드 찾기 : O(1)

인접리스트

각 정점들이 가지고 있는 간선들을 연결리스트로 가지고 배열에 담아두는 형식

말로 표현하기가 살짝 힘든데 그림을 보면 이해가 쉽다

각 정점 1,2,3,4,5를 배열에 담아둔 뒤

1이 가지고 있는 간선 (1,2), (1,5)를 연결리스트로 표현해서 가지고 있는다

이렇게 표현한 인접리스트의 노드 개수는 2m인데 간선 (u,v)는 u집합에서 한 번, v집합에서 한 번 총 두 번 나타나기 때문

인접리스트로 나타낸 그래프의 연산 시간

저장 공간 : O(n+m)

v에 인접한 노드 찾기 : O(degree(v))

edge(u,v) 노드 찾기 : O(degree(n))