[자료구조] 그래프

그래프란 연결 관계를 가지는 자료구조이다. (연결구조의 예 : 지하철역들 사이의 연결여부, 거리수치)

링크드 리스트와 같이 노드를 성분으로 가진다.

---

그래프 기본

 

노드들 끼리 직접 연결되어 있을 경우 이 연결관계선을 '엣지'라고 한다. 예를 들어 A와 B사이에 연결관계가 존재하면 이는 'A와 B사이의 엣지'이며, (A,B) 혹은 (B,A)로 표기한다.

직접 연결된 두 노드는 '인접'했다고 한다.

한 노드에 연결된 노드의 개수를 '차수'라고 한다.

어떤 노드에서 어떤 노드까지 가는데에 필요한 엣지들을 '경로'라고 한다. 경로는 충분히 여러개일수 있는데, 그 중 제일 짧은 경로를 '최단 경로'라고 한다. (cf. 경로는 아예 존재하지 않을 수도 있다.)

---

방향 그래프

 

앞서 설명한 그래프에서 '엣지'는 방향이 존재하지 않았지만, 사회에 존재하는 관계중에는 방향이 존재하는 관계도 있다. 예를 들면 인스타그램의 팔로우같은 것이다. 이럴 경우엔 방향이 존재하는 그래프를 사용해야 한다.

 

이 때 A가 B를 가리키면 'A로부터 B로 향한 엣지'이며 이는 (A,B)로 표기한다. (나온 노드가 앞서 표기되어야 한다.)

만약 서로를 가리키면 엣지를 두 개 가진다.

이 경우 '경로'가 조금 달라질 수 있다. 단순히 연결되어 있으면 경로로 사용할 수 있던 무방향 그래프와는 달리 방향그래프에서는 방향이 통해야 이동할 수 있다.

'차수' 또한 '출력차수'와 '입력차수'를 나누어 따로 생각해주어야 한다.

---

가중치 그래프

 

도시간 거리와 같은 연결관계의 경우 똑같이 연결이 되어있더라도, 거리가 다를 수 있다. 이런 경우 엣지에 숫자를 표기하여 적어주는데, 이를 가중치 그래프라고 한다.

 

가중치 그래프에서는 경로의 길이를 계산할 때 엣지 당 단순히 1로 계산하는 것이 아니라, 엣지에 해당하는 숫자를 모두 더해 경로의 길이로 본다.

---

인접정보를 담는 방법

 

인접정보를 표기하기 위해선 두가지 방법을 사용할 수 있다.

 

먼저 인접행렬을 사용하는 방법이다. 말그대로 그래프의 모든 노드의 관계를 행렬로서 표현한다. 노드끼리 엣지가 존재할 경우 1로, 아닐 경우 0으로 표기한다.

 

다음으로 인접 리스트를 사용하는 방법이다. 각 노드가 인접 노드의 정보를 리스트로서 담고 있다.

---

그래프에 대한 분석

 

지금까지 트리나 링크드 리스트같은 자료구조에서 해당 자료의 시간복잡도를 분석할때는 해당 자료의 노드개수(n)을 사용했다. 그래프에서는 조금 다르게 표현할 수 있다.

 

노드를 V(Vertex, 꼭짓점)라고 표현하고, 엣지를 E로 표현해서 나타낸다.

E의 갯수는 방향 그래프의 경우엔 최대 V^2개, 무방향 그래프의 경우엔 최대 V^2/2개 존재할 수 있다.

(즉 최악의 경우 E는 V^2에 비례한다.)

 

따라서 편의에 따라 그래프는 시간복잡도를 표기할 때도 O(V), O(lg(E))와 같이 표기한다.

---

그래프의 시간복잡도(공간복잡도)

 

인접정보를 담을 때 인접 행렬을 사용한 방법은 O(V^2)의 공간 복잡도를 가지고, 인접 리스트를 사용한다면 O(V+E)의 공간 복잡도를 가진다. (인접 리스트는 엣지 만큼 정보를 담고 있다고 볼 수 있기 때문이다. 다만 이 역시 각 노드가 모두 서로 연결된 최악의 경우에는 V^2의 시간복잡도를 가진다.)

 

두 노드가 연결됐는지 확인하려면, 각 노드에 담긴 인접리스트를 전부 확인해야 한다. 따라서 시간복잡도는 최악의 경우 O(V)이다. (각 노드는 최대 V개의 노드와 인접할 수 있으므로) 인접 행렬의 경우로 각 행 혹은 열을 전부 확인해야 하니 시간복잡도는 같다. 다만 행렬은 연결이 되어 있지 않아도 0이라는 정보가 담겨있는 반면, 리스트의 경우 연결이 되어있지 않으면 정보가 아예 없어 탐색 시간이 더 적게 걸린다. 따라서 보통 인접 리스트를 사용한다.