2022-07-31

그래프와 종류

그래프의 개념과 종류에 대해 알아보자!

그래프(Graph)

그래프는 데이터 간에 관계를 나타내는 자료구조로, 정점(Node 또는 Vertex)과 간선(Edge)로 구성되어있다.

정점은 개체를 의미하고 간선은 개체 간에 관계를 의미한다.

그래프는 정점이 서로 연결되어 있지 않아도 구성할 수 있고 사이클이 가능하다.

사이클이란 특정 노드에서 출발해 다시 돌아오는 경로가 존재한다는 것을 의미한다.

간선에 방향이 있어 해당 방향으로만 순환할 수 있는 그래프를 말한다.

간선에 방향이 정해져 있지 않아 어느 간선으로든 정점을 순환할 수 있는 그래프를 말한다.

간선에 가중치 또는 가중치 값이 할당된 그래프를 말한다.

그래프를 나타내는 방법은 크게 인접 행렬과 인접 리스트가 있다.

정점과 간선의 관계를 2차원 배열로 표현하는 방법이다.

정점의 개수는 행렬에 크기에 따라 결정되고, 주로 정점이 작은 그래프에 사용되는 방법이다.

인접 행렬이 시간 복잡도로 이점을 얻는 상황은 특정 정점 간에 연결된 간선이 있는지

확인할 때 상수 시간으로 동작하기 때문이다.

정점과 간선의 관계를 해시 테이블과 배열로 표현하는 방법이다.

해시와 배열을 사용해 간선 정보를 효율적으로 저장하기 때문에, 정점이 많은 그래프에 사용되는 방법이다.