[자료구조] Graph

그래프란? 

개체 (object)들 간의 이진관계를 표현한 것이다.

 

그래프 요소 

G = (V,E) 

V : 노드 정점라고 부른다. 

E : 노드 쌍을 연결하는 에지(edge) 혹은 링크(link)

 

앞으로 밑의 설명에서 n = |V| , m = |E| 라고 하자

 

그래프 종류

 

1. 무방향 그래프 (Undirected Graph)

에지간의 방향이 존재하지 않는 그래프 이다. 

 

** 보편적으로 두개 노드 간의 에지는 1개만 있다고 보고, 자기 자신으로 가는 셀프 에지도 없다라고 본다. 

 

2. 방향 그래프 (Directed Graph)

에지 (u,v)  는 u로 부터 v로의 방향을 가진다. 

방향이 다르면 서로 다른 그래프가 된다. 

 

** self edge가 존재할 수 있다. 

 

3. 가중치 그래프 ( Weighted )

에지 마다 가중치가 지정되어 있다. 

 

 

그래프의 표현

 

<무방향 그래프>

1. 인접 행렬(adgacency matrix)

인접행렬은 2차원 행렬로 나타낸다. 0~n-1까지 존재한다. 

 

- 인접행렬은 대칭행렬이다.

- 저장공간은 O(n^2)이다. 

- 어떤 노드 v에 인접한 모든 노드 찾기는 O(n) 시간이 걸린다. 

- 어떤 에지에 (u,v)가 존재하는지 검사는 O(1) 시간이 걸린다. (찾으려는 n,m이 1인지만 확인하면 되니까) 

 

 

2. 인접 리스트 (adjacency list)

정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트이다.

 

- 저장공간은 O(n+m)이다.

- 어떤 노드 v에 인접한 모든 노드 찾기는 O(degree(v)) 시간이 걸린다. 

- 어떤 에지에 (u,v)가 존재하는지 검사는 O(degree(u)) 시간이 걸린다. (어떤 한 행이나 열에 1인지만 확인하면 되니까)   - 총 노드의 개수는 2m 개가 된다. (1노드와 2 노드가 연결 되었다고 할때, 1-2 , 2-1 이렇게 두개의 엣지가 존재하기 때문)                                   

 

<방향 그래프>

 

1. 인접행렬은 비대칭

2. 인접 리스트는 m개의 노드를 가진다. (방향이 존재하기 때문)

 

   

<가중치 그래프>

에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장한다.

에지가 없을 경우 대각선:

- 특별한 규칙은 없으며 그래프와 가중치가 의미하는 바에 따라서 0 또는 무한으로 표현한다. 

 

 

 

 

이 글은 권오흠 교수님 수업을 듣고 정리한 내용입니다!

출처 : JAVA로 배우는 알고리즘