그래프 (자료 구조)

3개의 꼭짓점과 3개의 변으로 이루어진 그래프.

그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

컴퓨터 시스템에 그래프를 저장하는 방법은 여러가지가 있다. 자료 구조는 그래프 구조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다. 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하다. 하지만 실제 적용에 있어서 최적의 자료 구조는 이 두 구조의 조합된 형태를 띤다. 리스트 구조는 종종 sparse graphs에 적합하며 적은 메모리 공간을 요구한다. 행렬 구조는 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공한다.

리스트 자료 구조

발생 리스트(Incidence list) - 변들은 변으로 연결된 두 꼭짓점(방향이 있다면 순서가 존재함)와 가중치(weight), 다른 특정 데이터들을 포함하는 배열로 표현된다. 변으로 연결된 두 꼭짓점은 서로 인접(adjacent)한 관계라고 일컫는다.

인접 리스트(Adjacency list) - 발생 리스트와 비슷하게도, 각 꼭짓점이 인접한 꼭짓점들의 리스트를 가진다. 따라서 방향성을 가지지 않은 그래프에서는 불필요한 정보가 생기게 한다. 예를 들어 만약 A와 B가 인접하다면 A의 인접 리스트는 B를 포함하게 되며 동시에 B의 리스트에도 A가 포함된다. 추가적인 저장 공간에 대한 비용이 있다면 인접 정보를 얻는 것은 빨라진다.

행렬 자료 구조

발생 행렬(Incidence matrix) - 그래프는 변을 열로 하고 꼭짓점을 행으로하는 행렬로 표현되며, 행렬[꼭짓점,변]은 변의 끝점에 대한 데이터를 가진다(가장 간단한 경우: 1은 연결됨을 의미, 0은 연결되지 않음을 의미). 행렬의 크기는 $|V|\cdot |E|$ (꼭짓점의 수 $\times$ 변의 수)로 나타낸다.

인접 행렬(Adjacency matrix) - 인접 행렬의 크기는 $|V|\cdot |V|$ (꼭짓점의 수)로 나타낸다. 만약 꼭짓점 x에서 꼭짓점 y로 변이 존재하면 행렬 성분 x행 y열의 값은 1이고 그렇지 않으면 0이다. 이것은 부분그래프(subgraph), 역(reverse)그래프를 쉽게 찾게 해준다.

같이 보기

• 그래프 순회
• 그래프 데이터베이스
• 그래프 그리기

외부 링크

• Boost Graph Library: a powerful C++ graph library s.a. Boost (C++ libraries)
• Networkx: a Python graph library
• GraphMatcher Archived 2020년 2월 5일 - 웨이백 머신 a java program to align directed/undirected graphs.
• GraphBLAS A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.