[Data Structure]그래프(Graph)

그래프란, 오일러가 만들어 낸 연결 관계를 단순화하여 표시한 도구이다.

 

정점(Vertex)와 간선(Edge)로 이뤄져 있으며 시각화하면 다음과 같다.

 

오일러 그래프

 

정확하게 정의하면 그래프는 '정점의 모음'과 이를 잇는 '간선의 모음'의 결합이다.

 

위 사진처럼 간선을 통해 서로 이웃된 각 정점은 그래프 안에서 경로를 형성한다. 이 경로는 한 정점에서 다른 정점으로 이동할 수 있는 길을 의미하고, 위처럼 정점 사이의 이동은 간선을 통해서만 가능하다.

 

또한 어느 한 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 그 경로를 일컬어 '사이클'을 형성한다고 말한다.

 

경로는 방향성을 가지기도 한다. 방향성이란, 두 정점 간의 이동 방향을 의미하며 한 쪽으로만 방향이 정해져 있으면 반대로는 이동이 불가능하고 이런 방향성을 가진 그래프를 방향성 그래프, 방향성 없이 왕복이 가능하다면 무방향성 그래프라고 한다.

 

그래프에는 연결성이라는 단어가 있다. 무방향성 그래프 내의 두 정점 사이에 경로가 형성되어 있으면 이 두 정점은 연결되어 있다고 표현하고, 그래프 내의 모든 정점이 연결되어 있으면 이 그래프는 연결되었다고 표현한다.

 

---

 

그래프의 표현 방식은 두 가지가 있다. 하나는 인접행렬로 표현하는 방법이고 다른 하나는 인접리스트로 표현하는 방식이다. 두 방식 모두 장단점이 존재하며 그림으로 표현하면 다음과 같다.

 

 

1. 인접행렬

 

인접행렬의 경우 그래프를 표현하는 경우 내부 정점의 개수가 a개라고 할 때 a x a의 행렬을 이루며, 무방향성 그래프의 경우 대각선을 기준으로 대칭을 이룬다.

 

방향성 그래프의 경우 출발 정점 -> 도착 정점의 경우는 1로 표현하고 반대의 경우는 0으로 표현한다.

 

 

2.인접리스트

 

인접리스트의 경우 정점 내부에 간선으로 이어진 정점의 정보를 담고 있다.  각 정점을 노드로 취급하여 해당 정점에서 이어진 간선의 주소를  갖는 식으로 사용한다.

 

---

인접행렬과 인접리스트 각각 장단점

 

두 가지 방식으로 표현하는 것은 각각 장단점이 명확하기 때문에 사용한다.

 

장점

 

행렬 : 정점간의 관계 파악에 용이

 

리스트 : 메모리 크기가 인접행렬에 비해 상대적으로 적다.

 

 

단점

 

행렬 : 메모리 크기는 정점 크기 x N^2(N은 정점의 개수)인 만큼 차지하는 메모리가 크다.

 

리스트 : 인접 관계 확인시 순차 탐색 발생

 

---

그래프 순회

 

그래프는 정렬이 되어 있지 않기 때문에 내부를 순회하기 위해 특정 정점에서 시작해서 모든 정점을 방문하여 데이터를 탐색한다.

 

이 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

 

 

1. 깊이 우선 탐색

 

정점 순회 중 간선이 발견되면 해당 간선으로 넘어가는 식으로 더 이상 내려갈 간선이 없을 때까지 내려간 다음 분기로 돌아와 다음 간선을 탐색한다.

 

 

2. 너비 우선 탐색

 

정점 순회 중 간선이 발견 되어도 해당 정점과 같은 분기에 있는 다른 정점을 모두 탐색한 다음 간선으로 내려간다.

 

 

위 두 방식 모두 노드에 방문 여부를 확인할 수 있는 변수가 필요하다. 해당 변수가 없다면 이미 방문한 변수를 계속 방문하게 되고 무한 루프에 빠질 수 있다.

 

 

---

 

또한 그래프에는 가중치라는 변수를 두기도 하는데, 이는 해당 간선을 이동하는 데 들어가는 비용(코스트)를 의미한다.

 

이 가중치를 계산하여 특정 정점에서 다른 정점들로 이동하는 최소 비용을 계산할 수 있는데 이를 최소 신장 트리라고 한다.

 

 

1. 프림 알고리즘

 

최소 신장 트리를 구하는 알고리즘 중에 하나다. 내용은 다음과 같다.

 

임의의 정점을 시작 노드로 트리에 삽입 -> 인접 정점의 간선 가중치를 조사 -> 가장 가중치가 낮은 간선의 정점을 트리에 추가(단, 기존 정점과 사이클 형성을 하면 안된다.) -> 모든 노드가 트리에 삽입될 때까지 위를 반복

 

여기서, 간선을 비교할 때, 현재 트리에 들어온 모든 정점에 연결된 간선을 비교한다. 이때 비교과정에서의 비용 발생이 심하기 때문에, 삽입 삭제가 빠르고 삽입 시 정렬을 하는 우선순위 큐가 효율이 좋다.

 

 

2. 크루스칼 알고리즘

 

최소 신장 트리를 구하는 알고리즘 중 하나.

 

그래프 내의 모든 간선을 오름차순 순으로 정렬 -> 정렬한 간선을 순회하며 최소 신장 트리에 추가(단, 이때 사이클을 형성하면 안된다.)

 

사이클 형성을 감시할 때, 분리 집합을 이용하면 사이클 감시에 용이하다.

 

트리에 추가된 간선에 연결된 정점들을 하나의 집합으로 묶고, 추가하려는 간선에 연결된 정점들의 집합이 다를 경우, 사이클을 형성하지 않는 것으로 판단하여 트리에 추가, 만약 같은 집합의 경우 사이클을 형성하는 것이므로 넘기면 된다.

 

---

길찾기 알고리즘

 

그래프 내에서 출발 정점과 도착 정점이 있을 때, 최소의 비용으로 해당 정점으로 이어지는 루트를 짜는 알고리즘.

 

다익스트라 알고리즘과 A*(에이스타) 알고리즘이 대표적이다.

 

 

1. 다익스트라 알고리즘

 

각 정점에 시작점부터 자신에게 이르는 거리를 담을 공간을 준비 후, 무한대로 초기화(출발 정점에서 해당 정점까지의 거리) -> 시작 지점의 경로를 0으로 설정 후, 최단 경로에 추가 -> 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신, 이를 최단 경로에 추가

 

이때, 추가하려는 정점이 이미 있을 경우, 추가하려는 경로가 더 비용이 저렴할 경우의 한해 기존 경로 수정.

 

-> 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 반복.

 

 

2. A* 알고리즘

 

게임에서 주로 사용되는 알고리즘이다.

 

이 알고리즘의 핵심은 다음과 같다.

 

• 최소가 되는 지점을 우선 탐색(우선순위 큐)
• 휴리스틱 추정값 사용 --> f(x) = h(x) + g(x); h는 경로 가중치, 즉 노드를 이동하는 데 들어가는 비용. g는 노드 n으로부터 목표 노드까지의 추정 가중치 -> 맨하탄 길이 사용(|x1 - x2| + |y1 - y2|;)
• OpenList와 ClosedList로 노드 관리.

 

위 개념을 적용하여 알고리즘이 구성된다.

 

시작 노드를 우선순위 큐에 삽입 후 시작 -> 최상위 노드를 dequeue하고 ClosedList에 삽입 -> 최상위 노드와 인접한 노드들을 OpenList에 삽입 -> OpenList 내의 노드들의 추정값(F)을 검사 후, ClosedList에 삽입 -> F가 더 작은 경우 경로 갱신 -> h가 0이 될 때까지(목표 노드 발견)까지 검사