[자료구조] 13강 그래프, 그래프 표현 방법

1.그래프의 정의

그래프는 정점(vertex), 간선(edge)들의 집합으로 구성되는 비선형 자료구조

V(G)와 E(G)는 그래프 G의 정점들의 집합과 간선들의 집합을 나타내며 G=(V,E)로 표기

그래프 G에서 정점(vertex)는 V(G)로 표기하고 노드라고 부르기도 한다.

간선(edge)는 정점들 간의 관계를 표현하는 방법으로 E(G)로 표기하고 링크(link)라고 부르기도 한다

 

2.그래프의 용어

그래프는 간선들 간의 방향성이 있는지와 간선의 가중치가 있는지 및 간선의 수에 따라 여러 가지 그래프의 종류로 구분

 

(1) 무방향 그래프

무방향 그래프는 정점들 간에 순서가 없는 그래프로서 간선을 의미한다.

(2) 방향 그래프

방향 그래프는 정점들 간의 순서가 의미 있는 그래프로 다른 간선을 의미

(3) 완전 그래프

완전 그래프는 각 정점에서 다른 모든 정점을 연결하여 최대의 간선 수를 가지는 그래프

정점이 n개인 무방향 그래프에서 최대의 간선수는 n(n-1)/2개 이고 정점이 n개인 그래프의 최대 간선 수는 n(n-1)개 이다.

(4) 부분 그래프

부분 그래프는 원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프

(5) 가중 그래프

가중치 그래프는 정점을 연결하는 간선에 가중치가 할당된 그래프를 의미

(6) 정점의 차수

한 정점의 차수는 그 정점에 부속한 간선들의 수를 말한다

(7) 그래프의 경로

그래프 G의 경로는 임의의 정점까지의 연속된 정점들의 순서를 말하며 이들을 구성하는 간선들의 수를 경로의 길이라고 한다.

그래프의 경로들 중에서 모두 다른 정점으로 구성된 경로를 단수 경로라고 하며 단순 경로에서 처음과 마지막 정점은 같을 수 있다.

(8) 사이클

단순 경로 중에서 처음과 마지막 장점이 같은 경로를 사이클이라 한다.

방향 그래프이면서 사이클이 없는 그래프는 DAG(Directed Acyclic Graph)라고 하고 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프, 떨어져 있는 정점이 없는 그래프는 연결 그래프 (Connected Graph)라고 한다.

 

* 그래프 표현 방법

그래프를 표현하는 방법에는 인접 행렬과 인접 리스트로 표현하는 방법이 있다.

인접행렬은 2차원 배열을 사용하고 인접리스트는 연결 리스트를 활용하여 표현

그래프의 표현방법은 그래프의 특성에 따라 메모리의 사용량과 처리 시간 등이 달라지므로 효율적이 표현방법을 선택하여 사용

인접 행렬은 간선이 많은 그래프에 적당한 표현방법이며 인접 리스트는 간선의 수가 많지 않는 희소 그래프를 표현하기에 적당한 방법으로 메모리의 낭비를 줄일 수 있다.

 

1.인접 행렬

인접 행렬은 그래프의 구조를 표현하기 위해서 정점들 사이의 인접 관계를 정점 수만큼의 행과 열을 갖는 행렬을 이용하여 표현하는 방법이다.

인접 행렬 표현은 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비가 발생한다.

 

2.인접 리스트

그래프의 각각의 정점에 대해 인접한 정점들을 연결 리스트로 표현하는 구조로 각 정점의 차수만큼 노드를 연결한다.

그래프에 연결된 정점들만을 이용하여 표현함으로 정점들 간의 간선의 수가 적은 경우에 메모리의 낭비를 줄일 수 있다.

인접 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드를 구성되고 정점의 헤드 노드는 정점에 대한 리스트의 시작을 의미한다.

- 간선의 중복을 피하기 위해 간선을 고유한 노드에 저장하여 여러 리스트에 공유할 수 있도록 하는 인접 다중 리스트를 사용한다.

인접 다중 리스트의 경우에는 중복 사용을 피함으로 기억 장소를 절약하는 장점은 있으나 검색시간이 느려진다는 단점을 가진다.