[자료구조] 그래프(Graph), 인접 행렬, 인접 리스트

그래프(Graph)

정점(vertax)과 간선(edge)로 이루어진 자료구조이다.

 

방향성을 가지고 있느냐에 따라 방향 그래프와 무방향 그래프로 나누어진다.

 

 

위 그림에서 왼쪽이 무방향 그래프, 오른쪽이 방향 그래프를 나타낸다.

 

 

이러한 그래프는 보통 인접행렬, 인접 리스트의 두 가지로 표현한다.

 

 

인접 행렬

각 정점(vertax)에 대해서 간선(edge)가 연결되어 있는 경우에 1을 작성하는 방법이다.

 

위 왼쪽 무방향 그래프의 인접 행렬은 아래와 같다.

 

 

해당 행과 열이 교차되는 곳에 1이 있다는 것은 두 정점이 간선으로 연결되어있다는 뜻이다.

그리고 왼쪽 상단에서 오른쪽 하단으로 가는 축을 기준으로 대칭을 가지는 것을 확인할 수 있다.

무방향 그래프는 방향성이 없기 때문에 1과 0이 관계가 있으면 0과 1도 관계가 있기 때문이다.

 

이렇듯 무방향그래프는 인접 행렬로 주로 나타낸다.

 

 

인접 리스트

각 정점에 대한 연결성을 연결리스트로 나타내는 방법이다.

 

위 그림처럼 List[0]에는 정점 0과 연결된 정점들을 연결리스트로 나타내고, List[1]에는 정점 1과 연결된 정점들을 이어붙여놨다.

인접 리스트는 방향성이 있는 방향그래프에 자주 사용되는데, 위 그림도 방향 그래프에 대한 인접리스트이다.