상세 컨텐츠

본문 제목

알고리즘 공부 <8> - 그래프

알고리즘

by oimb 2018. 11. 4. 16:42

본문

 

오늘은 그래프에 대해서 한번 알아봅시다.

 

1. Graph

 

 

그래프는 꼭지점들의 집합과 과 간선들의 집합으로 이루어진 집합입니다

그래프의 종류로는 무방향 그래프, 방향 그래프 ,가중치가 있는 그래프, sparse 그래프, dense그래프 있습니다.

참고로 sparse 그래프는 간선의 개수 보다 노드의 개수가 더 큰 그래프이며 dens.e 그래프는 그것의 반대입니다.

그리고 간선의 개수의 빅오는 V * V 임을 알 수 있습니다. ( 셀프루프 포함 , 배열로 표현시 꽉찬 배열)

 

 

인접 관계에서 그래프가 무방향그래프인 경우에는 인접관계가 대칭되지만 방향 그래프인 경우에는 반드시 대칭되지지는 않는다.

또 그래프에서 임의의 두 노드를 골랐을 때 이 두노드가 연결 되어있다면 그래프가 연결되어 있다고 한다.

그리고 방향 그래프에서 strongly connected란 그래프에서 임의의 두 꼭지점에 v,w에 대해서 v에서 w로 가는 경로가 존재한다면 이를 strongly connected라고 한다.

 

 

2. Adjacency

 

먼저 왼쪽 그림에 경우를 보면 

임의의 두 꼭지점 v,w가 간선 (v,w)을 구성한다면 두 꼭지점은 인접해 있다고 한다.

그리고 오른쪽 그림은 임의의 두 간선 e , f가 서로 공통의 꼭지점을 가진다면 두 간선은 인접해 있다고 한다.

 

 

3. Representation of Graphs

 

 

참고로 두 표현방식은 단순그래프를 기반으로 한다. ( 다중 연결과 셀프루프를 포함하지 않음)

인접의 관계를 행렬과 리스트로 표현한 것이다.

 

인접리스트는 꼭지점들의 배열로 구성되며 하나의 꼭지점당 하나의 리스트를 구성하는데 이 리스트는 꼭지점 집합 V에 속하는 어떤 u에 대해  u와 인접한 모든 꼭지점들로 구성된다.

인접 행렬은 행과 열이 꼭지점에 대응되고 꼭지점들 중한 인접하는 관계 끼리는 1로 아닌 관계는 0으로 매핑 시킨다.

 

 

4. Degree

꼭지점 v에 대한 차수(degree)는 v에 부속되어있는 간선의 개수이다. 또 이를 deg(v)라고 쓴다. 따라서 deg(v) = 8  (self loop 포함)

Handshaking Lemma

쉽게 생각하면 악수를 생각하면 된다. 서로 악수할 때 손이2개 인것을 묘사하며 짝수개인것을 말한다.

즉 어떤 그래프에서 모든 꼭지점의 차수의 합은 짝수라는것을 의미한다. ( 2 * n )

이를 추론하면 어떤 그래프에서 홀수차수의 꼭지점의 개수는 짝수개인것을 알 수 있다.

 

5. Storage Requirement

Adj: list

필요 저장량을 보면방향 그래프에 대해서 보면

모든 인접리스트의 길이의 합은 간선의 개수가 된다.

그리고 총 storage는 O(V+E)가 된다 이 이유는 무방향 그래프를 보고 설멍하겠습니다.

무방향 그래프에서는 모든 인접리스트의 길이 합은 간선의 개수 *2가 된다.

그리고 총 스토리지는 역시 O(V+E)가 된다.

O(V+E)인 이유를 설명하기에 앞서 +는 or을 의미한다는것에 명심하자

인접 행렬의 경우 행과 열이 노드의 개수만큼 이루어지기 때문에 총 stroage 는 노드의개수 제곱이 된다

하지만 인접 리스트의 경우에는 빅오가 노드의 개수와 간선의 개수중 더 큰쪽에 영향을 받게 된다.

노드의 개수가 간선의 개수보다 더 큰경우 노드의 개수가 빅오가 된다.

하지만 간선의 개수가 노드의 개수보다 더 큰 경우에는 노드의개수 * (노드의 개수 -1)이 된다.

하나의 노드가 자신을 제외한 n-1개의 노드와 인접할 수 있고 이러한 경우가 n개 있기 때문이다. 

즉 이 경우 빅오는 n * (n-1)이 된다. 또 중복을 제외한 경우는 n(n-1)/2가 된다 어찌됬건 빅오는 O(V+E)가 된다.

 

Adj : Matrix

 

인접행렬의 행과열은 노드의 개수로 이루어져 있으며 특정 두 노드가 간선을 이룬다면 즉 (i,j) 가 간선의 집합에 속한다

행렬(i,j) 값은 1이며 아닌경우에는 0이 들어간다.

 

6. Pros and Cons

: Adj List

 

인접리스트는 그래프가 노드의 개수가 간선의 개수보다 많은 경우에는 storage requirement가 좋다

하지만 어떠한 두 노드 u ,v에 대해서 간선(u,v)를 이루는지 확인하려면 해당 노드의 리스트를 찾을때까지 전부 바야하

단점이 존재한다. ( 행렬은 두 노드의 값이 1인지 확인하면 된다.)

: Adj Matrix 

행렬은 노드의 개수가 행과 열을 이루므로 공간은 빅오 O(v^2)이 된다. 즉 공간에서는 비효율적이다.

하지만 두노드가 간선을 이루는지를 알아내는 방법은 1인지 아닌지만 찾음 되므로 굉장히 쉽다.

그래프에대해서 간단히 알아보았다 다음에는 그래프 탐색에 대해 공부해보자

관련글 더보기