[자료구조] 그래프 (Graph)

그래프란?

정점과 정점들간의 관계가 표현된 자료구조

 

• 정점Vertex : 대상이나 개체를 나타내는 그래프의 구성요소
• 간선Edge : 두 정점을 연결하는 선

 

• 무향 그래프 : 간선의 방향이 없는 무방향 그래프 무향 그래프의 최대 간선 수 V * (V - 1) / 2개
• 유향 그래프 : 방향을 가지는 그래프 유향그래프의 각 정점이 가질 수 있는 최대 간선수는 V - 1개

 

그래프의 표현

인접행렬

V * V크기의 2차원 배열을 이용해서 간선 정보를 저장

행번호와 열번호는 그래프의 정점에 대응

 

무향 그래프

왼쪽의 무향 그래프를 오른쪽과 같은 인접행렬로 나타낼 수 있다.

i번째 행의 합 = i번째 열의 합 = Vi의 차수

 

유향 그래프

방향 그래프라면? 행렬은 위와같이 대칭이 아니게 되는 것이다.

행 i의 합 = Vi의 진출 차수

열 i의 합 = Vi의 진입 차수

위의 경우 1행의 합은 4로 1 노드에서 나가고 있는 간선의 수가 총 4개이다.

반면 1열의 합은 2로 1 노드로 들어오고 있는 간선의 수는 2개임을 알 수 있다.

 

만약 가중치가 있는 그래프라면 1대신에 각 가중치를 값으로 넣어주면 된다.

 

인접 행렬의 장점

• 이해하기 쉽다
• 간선의 존재 여부를 즉각 확인 가능

 

인접 행렬의 단점

• n * n행렬이 필요하기 때문에 n^2에 해당하는 공간이 필요
• 행렬의 준비 과정에서 행렬의 모든 원소를 채우는데에 O(N^2)라는 시간이 소요된다.

 

=> 간선의 밀도가 높은 그래프의 경우에 적합한 표현방법이다.

 

인접 리스트

두 정점을 연결하는 간선의 정보를 리스트로 저장함

각 정점마다 리스트를 하나씩 만든다. 각 정점에 인접한 정점들을 연결리스트로 단다.

인접 행렬과 달리 존재하지 않는 간선은 저장되지 않는다.

각 노드는 정점의 번호, 다음 정점의 포인터 로 구성된다.

 

가중치를 가지는 그래프라면 정점의 번호와 함께 가중치를 저장한다.

 

인접 리스트의 장점

공간의 낭비가 없다. = 간선의 밀도가 낮은 휘귀그래프의 경우 유용한 표현법이다.

 

인접 리스트의 단점

정점 i와 정점 j간의 간선이 존재할 때 리스트를 차례대로 훑어야 하므로 인접 행렬보다는 탐색 시간이 걸린다.

 

인접 배열

각 정점에 연결된 정점들을 연결리스트 대신 배열로 저장하여 연결 리스트의 단점을 해결하는 방법이 있다.

1에 {2, 3, 4, 6}과 같은 배열을 연결 해두고 이 배열을 정렬된 형태로 만들면 이진탐색을 사용할 수 있어

임의의 정점에 인접한 정점 수가 k라면 logK+1번 내로 j의 존재를 확인할 수 있다.

인접 배열의 헤더에 인접 정점이 몇개인지 표시해두면 더 쉽게 탐색을 할 수 있다.

 

간선 리스트

지금까지의 표현법은 정점을 중심으로 한 표현법이라면 간선 리스트는 간선을 중심으로 한 표현법이다.

두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장한 것

시작 정점과 끝나는 정점을 리스트 형식으로 저장한다.