[알고리즘] 그래프의 개념과 표현

그래프의 개념과 표현

이번 시간에는 그래프의 개념과 그래프를 표현 하는 방법에 대해 알아보자

그래프는 G = (V,E) 로 표현되며

V : Vertex, 노드 혹은 정점

E : Edge, 노드쌍을 연결하는 엣지 혹은 링크

위와 같이 V와 E 들의 집합으로 나타내어진다.

그래프는 개체들 간의 이진 관계를 나타낼 수 있다.

위의 그림은 8개의 vertex와 11개의 Edge를 가지고 있다.

특별한 언급이 없는 이상 노드의 개수를 n, 엣지의 개수를 m으로 표현한다.

그래프의 종류는 여러가지가 있는데

첫째로, 방향을 고려하지 않는 무 방향 그래프가 있다.

둘째로, 방향을 고려한 방향 그래프가 있다.

위의 그림은 방향 그래프이다.

마지막으로, 그래프의 모든 엣지가 가중치(weight)를 가지고 있는 가중치 그래프가 존재한다.

보통 엣지에 가중치를 부여해야 사용률이 높아지므로 노드가 아닌 엣지에 가중치를 부여하게 된다.

다음으로 그래프를 표현하는 방법에 대해서 알아보자

먼저, 인접행렬(adjacency matrix) 방법이 있다.

인접 행렬은 그래프를 nxn의 행렬로 표현하는 방법이다.

인접 행렬 방법에서, i 번째행 j 번째 열을 Aij 라고 할 때

정점 i와 j 사이에 엣지가 있으면 1, 없으면 0으로 표시한다.

예를 들어, 1과 2사이에 엣지가 있므로 1행 2열의 값은 1이 된다.

마찬가지로 3과 4 사이에는 엣지가 없으므로 3행 4열의 값은 0이 된다.

결과적으로 모든 행렬을 완성 했을 때 대칭 행렬의 구조를 가지는데, 

여기서 대칭 행렬이라는 뜻은 대각선을 기준으로 접었을때 대칭 이라는 뜻이다

그래프에서 가장 기본적인 연산은, 해당 노드에서 인접한 노드를 찾는 연산이다.

대부분의 그래프 알고리즘에서 필수적인 연산이다.

그러한 인접 노드를 찾기위해서, 인접 행렬의 한 행 전체를 끝까지 읽는 방법이 있다.

해당 행에서 1의 값을 가지고 있는 열이 인접한 노드이므로

인접하는 노드를 찾으려면 O(n)의 시간 복잡도를 가지게 된다.

두번째로 중요한 연산은, 두 노드 u와 v를 연결하는 엣지가 있는지 확인하는 것으므로,

u행 v열의 값만 보면 되므로 O(1)의 시간 복잡도를 가진다.

다음 그래프를 표현하는 방법은, 인접 리스트(adjacency list)이다.

인접 리스트에서는 배열 하나가 각각의 노드를 표시한다.

그리고 나서 해당 노드에 인접한 노드들을 리스트로써 표현한다.

예를 들어 노드 5개가 있으므로 길이가 5개인 배열을 만든다.

 1번에 인접한 노드는 2와 5 이므로 이를 리스트로 표현한다.

이 때, 리스트에 들어가는 순서는 중요하지 않다!

노드 개수는 2m개가 되는데, 이는 엣지 하나당 2개의 노드가 존재하기 때문이다.

또한, 필요한 저장공간은 O(n+m)이 된다.

왜냐하면 배열의 크기는 n이고, 노드들의 총 개수는 2m이므로 

n+2m에서 O안에 들어가면 상수가 사라져서 O(n+m)이 된다.

그 다음 인접 행렬에서도 살펴본 2개의 기본 연산에 대해서 살펴보자면,

인접한 노드를 찾기위해 인접 리스트에서는 해당 노드에 연결 리스트의 길이 만큼의 시간이 필요하다.

이 때, 어떤 노드 v에 실제로 인접한 노드의 개수는 degree(v)라고 부른다.

따라서 O(degree(v))의 시간 복잡도를 가진다.

둘째로, 어떤 에지 (u, v)가 존재하는지 검사하기 위해 모든 리스트를 찾아봐야하므로

O(degree(u))의 시간 복잡도를 가진다.

만약 방향 그래프로 이를 나타낸다면 어떻게 될까

방향 그래프는 무 방향 그래프와는 다르게 자기 자신을 가리킬수 있다.

따라서 위와 같이 같은 행, 같은 열에 1의 값을 가질 수 있고,

리스트에서도 인덱스와 동일한 값을 가질 수 있다.

그렇다면 가중치 그래프는 어떤식으로 인접 노드를 표현할까.

가중치 그래프에서는 엣지의 존재를 나타내기 위해 1 대신에 가중치로 표현한다.

엣지가 없을 때 또는 대각선을 나타낼 때는

특별히 정해진 규칙은 없으므로 그래프와 가중치가 의미하는 바에 따라서 표현한다.

예를 들어, 가중치가 거리 혹은 비용을 나타낸다면 엣지가 없으면 무한대, 대각선은 0으로 나타내거나

먄약 가중치가 용량을 나타낸다면 엣지가 없을 때는 0, 대각선은 무한대로 나타낼 수 있다.

마지막으로 그래프에서 사용하는 몇가지 기본용어를 살펴보자

먼저 경로라는 것은 시작 노드를 따라 끝 노드까지 도달하는 길을 뜻한다.

두 노드를 잇는 경로가 존재한다면 이를 연결(connect)되어있다고 표현한다.

이 때, 엣지 하나로 연결되어있을때 인접하다 라고 한다.

마지막으로 모든 노드 들이 엣지로 연결 되어 있을 때 연결된 그래프라고 한다.

(무방향 그래프로 가정)

위의 그림을 예로 들면, 각각의 그래프들은 연결 그래프 이지만 

3개 그래프 전체를 고려했을때는 연결되어있지 않은 그래프라고 할 수 있다.