record logo record

목차

그래프(Graph)란?

그래프(Graph)의 종류와 특징에 대해서 알아보기 전에 그래프의 실생활 예시 를 알아 보겠습니다.

그래프는 트리에 있었던 부모 자식 관계에 관한 제약이 없기 때문에 그래프는 트리보다 훨씬 다양한 구조를 표현할 수 있고, 현실 세계의 수많은 문제들을 푸는 데 유용하게 사용됩니다.

그래프 구성요소(용어)

그래프의 특징

그래프의 종류

datastructure-graph-category

그래프는 여러 가지 변형된 형태를 가질 수 있습니다.

그래프 는 대표적으로 간선에 방향이라는 추가적 속성을 부여하여 크게 유향(=방향, directed) 그래프무향(undirected) 그래프 두가지로 나뉩니다. 또한 가중치라는 속성을 가진 가중치 그래프 가 있습니다.

이외에 다중 그래프, 단순 그래프, 루트 없는 트리 그래프, 이분 그래프, 사이클 없는 방향 그래프(DAG) 등이 있습니다.

다음은 그래프의 형태로 그래프를 분류 한 경우입니다.

그래프(Graph)와 트리(Tree) 비교

 
그래프(Graph)
트리(Tree)
정의 정점(vertex)과 그것을 연결하는 간선(edge)들로 이루어진 자료구조 그래프의 한 종류인 DAG의 한 종류
방향성 방향 그래프, 무방향 그래프 존재 방향 그래프 존재
사이클 사이클, 자체 간선(self-loop), 순환(Cyclic) 비순환(Acyclic) 존재 사이클 절대 불가능
루트 노드 없음 한 개 존재
부모-자식 없음 존재
모델 네트워크 모델 계층 모델
탐색(순회) DFS, BFS Pre, In, Post Order
간선의 수 간선이 있을수도 없을수도 있음 노드가 N개인 트리의 간선의 수는 N-1개
경로 - 임의의 두 노드 간의 경로가 유일

그래프 구현 방법

인접 리스트(Adjacency List)

각 정점마다 하나의 연결 리스트 를 갖는 방식입니다.

int n = 10; // 정점의 개수
vector<int> adjacent[n];

adjacent[1].push_back(2);// 1->2
adjacent[1].push_back(3);// 1->3

인접 리스트O(|V|+|E|) 의 공간을 사용 합니다.

인접 행렬(Adjacency Matrix)

인접 리스트 표현의 큰 단점은 두 정점이 주어질 때 이 정점이 연결되어 있는 지를 알기 위해서 연결리스트를 일일이 뒤져야합니다. 이와 같은 연산의 속도를 높이기 위해 고안된 표현 방식이 인접 행렬(Adjacency Matrix) 로 표현한 방식입니다.

vector<vector<int> > adjacent;
adjacent[1][2] = 1; // 1->2
adjacent[1][3] = 1; // 1->2

인접 행렬 은 간선 개수와 관계없이 항상 O(|V|²) 크기의 공간을 사용 합니다.

그래프 구현 방법 비교

datastructure-graph-impl

※참고※
간선의 수가 |V|²에 비해 훨씬 적은 그래프를 희소(sparse) 그래프
반대로 간선의 수가 거의 |V|²에 비례하는 그래프를 밀집(dense) 그래프 라고 합니다.

따라서, 희소 그래프는 인접 리스트를 밀집 그래프는 인접 행렬을 사용하는 것이 유리 합니다.

References