Graph

# Graph

그래프는 버텍스와 엣지로 구성된 자료구조입니다

버텍스는 우리가 써왔던 노드와 같은 개념이고 엣지는 버텍스간의 연결관계를 나타냅니다. 그리고 두 버텍스가 엣지로 연결되어 있으면 두 버텍스는 인접해 있다고 말할 수 있습니다.

그래프의 예시로 네비게이션 길찾기에도 그래프를 이용한 탐색 알고리즘이 적용되어 있고, 게임 내 캐릭터 이동도 그래프 자료구조를 기반으로 합니다, 그리고 검색에서 사용되는 지식그래프도 그래프 자료구조를 활용하였습니다. 전통적인 검색엔진은 역색인 방법으로 키워드 기반으로 데이터를 저장하는데 이 방법은 키워드에 대한 정보를 빠르게 얻을 수는 있지만 연결관계를 가진 관련 키워드에 대한 정보는 찾기 어렵다는 한계가 있었습니다. 지식 그래프는 각 객체의 연관성을 엣지로 연결시켜서 한계를 극복했습니다. 이렇게 정보들 간에 연관관계가 있을 때 그 연관 정보를 가장 잘 관리할 수 잇는 자료구조가 그래프입니다.

그래프는 버텍스와 엣지로 구성되어 있다면 다양한 형태로 그려질 수 있고, 그 특징들에 따라 그래프들의 종류를 구분할 수 있습니다

[ 방향그래프 ]

방향성이 있는 엣지를 가진 그래프를 방향그래프라고 합니다. 방향이 있는 그래프에서는 무조건 방향이 있는 순서대로만 노드를 이동시킬 수 있습니다

[ 가중치 그래프 ]

엣지에 가중치가 주어진 그래프를 가중치 그래프라고 합니다. 가중치는 양수도 음수도 될 수 있습니다. 위의 그림에서 A→B의 경로를 봤을 때, 가중치가 없는 경우 A→B로 바로 가는 경로가 가장 빠른 방법이겠지만, 가중치가 있는 경우에 A→B의 가중치는 7이고, A→C→B의 가중치는 3이므로 A→C→B경로가 더 효율적인 방법이 되겠습니다.

[ 루프 ]

그래프에서 버텍스는 자기자신을 가리키는 엣지를 가질 수 있는데, 그 엣지를 루프라고 합니다.

[ 순환그래프 ]

그래프의 어느 한 버텍스에서 어떤 경로를 지나서 다시 그 버텍스로 돌아오는 그래프를 순환 그래프라고 합니다.

 

# 그래프 구현 방법

[ 인접행렬 ]

인접행렬은 이차원 배열로 표현할 수 있는데, 연결된 버텍스의 연결관계는 1 아니면 0이나 음수를 넣어서 표현 할 수 있습니다. 인접행렬을 이용한 구현방법은 버텍스간의 연결관계를 직관적으로 볼 수 있다는 장점이 있지만, 노드 갯수가 N개라면N^2에 해당하는 메모리 공간을 사용해야한다는 단점이 있습니다. 엣지를 추가하거나 삭제하는 것은 간단하지만, 새로운 버텍스를 추가했을 때는 연산이 복잡해집니다.

[ 인접리스트 ]

버텍스의 갯수 만큼의 리스트를 사용하는 방법입니다. 자신과 연결된 버텍스의 정보만 저장하게 됩니다. 인접리스트는 인접행렬보다 메모리 공간을 효율적으로 사용할 수 있다는 장점이 있습니다. 또한, 버텍스를 추가하거나 삭제하는 연산이 인접행렬보다 비교적 쉽습니다. 하지만 리스트만 보고 버텍스간의 연결관계를 파악하는데에는 인접행렬보다 시간이 더 소요된다는 단점이 있습니다.