[Algorithm]그래프 - 1. 그래프의 개념

그래프란?

• 그래프는 노드(vertex)와 간선(edge)을 이용한 비선형 자료 구조이다.
• 데이터는 노드(vertex)로 노드 간의 관계를 간선(edge)으로 표현한다.
• 노드 간의 관계에서 정도를 표현할 필요가 있을 때 가중치를 추가할 수 있다.
• 트리 자료 구조도 그래프의 한 종류에 속한다.(트리는 사이클이 없고 방향(부모 > 자식)이 있는 방향 그래프 이다.)

< 가중치가 존재하는 그래프 >

그래프의 종류

• 데이터와 관계만 표현하는 무방향 그래프(undirected graph)와 관계와 흐름의 방향까지 표현하는 방향 그래프(directed graph)가 있다.
• 방향 그래프는 한쪽 방향만 가르킬 수도 있지만 두 노드가 서로를 가르킬 수도 있다.

• 흐름의 방향 뿐만 아니라 흐름의 양도 그래프에 나타낼 수 있는데 흐름의 양을 가중치라고 한다. 이러한 그래프를 가중치 그래프(weight graph)라고 한다.

• 어떤 노드에서 출발해 간선을 따라 이동하다 보면 다시 출발한 노드로 돌아오는 경로를 사이클 이라고 하고, 사이클이 존재하는 그래프를 순환 그래프(cycle graph)라고 한다. 순환 경로가 존재하지 않는 그래프를 비순환 그래프(acycle graph)라고 한다.

 

다음글

[Algorithm]그래프 - 2. 그래프의 구현