[Data Structure] 그래프의 구성, 종류, 표현 (Graph)

기본 자료 구조 그래프에 대한 공부 기록이다.

구성

그래프는 정점과 간선으로 구성된다.

 

정점 : 대상(개념, 값 등)

간선 : 대상들 간의 관계를 나타냄

간선으로 연결된 두 정점은 인접의 관계를 가진다.

 

종류

무향 그래프

간선에 정점의 관계없이 그냥 이어져있다.

방향이 없다는 뜻의 무향이다.

 

가중 그래프

간선에 인접한 두 정점의 관계값이 있다.

하지만, 방향은 없다.

 

방향 그래프(유향 그래프)

인접한 두 정점 사이의 방향이 결정된다.

수치로 볼 수 있는 값은 없다.

 

가중 방향 그래프

인접한 두 정점 사이의 관계 값이 방향 각각에 결정된다.

 

그래프의 표현

그래프는 다양하게 구현될 수 있다.

인접 행렬

그래프가 n*n 행렬 A[][]로 표현된다.

정점 i와 j 사이의 간선 존재 여부를 A[i][j]에 기록한다.

무향 그래프의 인접 행렬로의 표현이다.

위처럼 배열로 표현된다.

가중 그래프일 경우 가리키는 방향으로 관계값을 넣어주면 된다.

방향 그래프일 경우 행 번호에서 열 번호가 가리키는 방향이므로, 이 방향으로 값을 넣어주면 된다.

 

인접 리스트

인접 리스트는 배열의 값으로 연결 리스트를 가리키게 하여

해당 배열 인덱스값의 정점이 가리키는 정점들을 표시한다.

가중치가 있을 경우, 가중치 값을 하나 더 만들어서 값을 삽입한다.

 

인접 배열

인접 배열은 인접 리스트와 비슷한 방법이지만,

리스트가 아닌 배열을 사용한다.

인접 해시 테이블

이 방법 또한 인접 리스트에서 리스트 대신 해시 테이블을 이용해 구현한 방법이다.