[Algorithm] 그래프

그래프

그래프는 현상이나 사물을 정점과 간선으로 표현한 것으로, 정점은 대상이나 개체를 나타내고 간선은 이들간의 관계를 나타낸다.

 

그래프는 크게 4가지 그래프로 나눌 수 있다.

1) 간선으로 이어진 그래프

2) 간선에 가중치를 더한 그래프

3) 간선에 방향을 가진 그래프(유향 그래프)

4) 간선에 가중치를 더하고 방향을 가진 그래프

 

그래프의 표현

그래프를 컴퓨터에서 표현할 때는 크게 행렬을 이용하는 방법과 리스트를 이용하는 방법이 있다.

 

인접형렬을 이용한 방법

그래프 G에서 정점의 총 개수가 n이라고 하면, n X n 행렬을 준비한다. 정점 i와 정점 j 사이에 간선이 있으면

행렬의 (i, j)원소와 (j, i) 원소의 값을 1로 할당하고 나머지는 0으로 할당한다.

인접행렬로 표현한 일반 간선 그래프

가중치가 있는 그래프를 표현할 경우 각 원소에 1이 아니라 가중치를 저장한다.

인접행렬로 표현한 가중치 그래프

유향 그래프를 표현할 경우, (i, j)의 원소와 (j, i)의 원소가 다르다. (i에서 j로 연결된 경우에만 원소가 1)

유향 그래프를 가중치로 표현할 경우 (i, j)의 원소에 가중치로 표현한다.

인접행렬로 표현한 가중치 있는 유향 그래프

인접 리스트를 이용한 방법

각 정점에 대해 인접한 정점을 리스트로 표현한다.

인접 리스트로 표현한 일반 간선 그래프

가중치를 가진 경우, 리스트에 인접 정점과 그에 대한 가중치를 함께 저장한다.

인접 리스트로 표현한 가중치 있는 그래프