[자료구조&알고리즘] 그래프?

 

 

그래프란?

: 자료구조의 일종

: 정점(Node, Vertex), 간선(Edge)로 구성 -> 간선이란? 정점과의 관계를 의미한다.

: G=(V,E)로 나타낸다.

 

 

 

<그래프와 관련된 용어 정리>

1. 그래프의 경로란?

: 시작점->도착점으로 가는 간선의 연속

ex) 위의 그림으로 표현해보면 정점 2에서 1로 가는 경로는 아래 두 가지 이다.

     2 -> 1

     2 -> 3 -> 1

 

2. 사이클이란?

: 시작점과 도착점이 모두 같은 경우. 즉, 출발한 정점으로 다시 되돌아오는 경우

 

2-1. 단순 경로와 단순 사이클?

단순하다는 건, 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클을 의미한다.

즉, 특별한 말이 없으면 일반적으로 단순 경로/사이클을 의미한다는 것을 알아두자.

 

3. 방향이 있는 그래프?

: 위 그림과 같이 A -> B 로 간선 방향이 있다면 B -> A로 가는 간선은 존재하지 않는다는 것을 의미한다.

 

4. 방향이 없는 그래프?

: 위 그림과 같이 A -> B 가 방향없이 간선으로 연결되어 있는 경우, B -> A로도 갈 수 있다는 것을 의미한다.

주의할 점) 이렇게, 방향이 없는 그래프는 A -> B의 경우와 B ->A 경우의 간선 2개를 모두 저장해줘야 한다.

 

5. 가중치?

: 간선에 가중치가 있는 경우

  => A에서 B로 이동하는 거리, 이동하는데 필요한 시간, 이동하는데 필요한 비용 등

 

6. 차수(Degree)?

: 정점과 연결되어 있는 간선의 개수

: 방향 그래프의 경우 In-degree(정점으로 들어오는 간선), Out-degree(정점에서 나가는 간선)로 나누어서 차수를 계산해야 한다.

 

 

<그래프를 코드로는 어떻게 표현해야 할까?>

1. 어떤 정점x와 연결된 간선을 효율적으로 찾기 위해서는 어떻게 그래프를 저장해야 할까?

 

1) 인접 행렬로 저장하기(2차원행렬/2차원 배열 사용)

A[i][j] = 1 // i에서 j로 가는 간선이 있는 경우

A[i][j] = 0 // i에서 j로 가는 간선이 없는 경우

가중치가 있을 땐, A[i][j] = w(가중치) 형태로 저장

 

2) 인접 리스트로 저장하기(링크드 리스트 사용)

A[i] = j와 같이 정점 i와 연결된 모든 정점(j)을 리스트에 포함하는 방식으로 저장하자

A[1] = 2 5 // 정점1과 연결된 정점은 2, 5 이다.

A[2] = 1 3 4 5 // 정점 2와 연결된 정점은 1, 3, 4, 5 이다.

A[3] = 2 4

A[4] = 3 5 2 6

A[5] = 1 2 4

A[6] = 4

 

이 경우는 각 리스트마다 길이가 다르므로 동적 배열이 필요하다. vector(C++) 나 arrayList(JAVA) 사용

 

가중치가 있을 땐, 아래처럼 A[i] = (j, w) 형태로 가중치(w)도 함께 저장하자

A[1] = (2,2) (5,7) // 1에서 2로 가는데 가중치가 2다. 1에서 5로 가는데 가중치가 7이다.

A[2] = (1,2) (3,2) (4,3) (5,1)

A[3] = (2,2) (4,1)

A[4] = (3,1) (5,7) (2,3) (6,7)

A[5] = (1,7) (2,1) (4,7)

A[6] = (4,7)

 

2. 그래프의 공간 복잡도를 알아보자~!

1) 인접 행렬 O(V^2) // 2차원 배열/행렬이므로 정점의 제곱만큼

2) 인접 리스트 O(E) // 간선을 저장하니까 간선의 개수만큼

 

즉, E << V^2 이므로 인접 리스트가 더 좋은 자료구조이다.

하지만, 다음 2가지 경우에는 인접 행렬을 사용하는 방법이 더 좋을 수 있다.

 

① u, v가 주어진 경우, u -> v로 가는 간선이 존재하는지를 찾을 때

인접 행렬의 경우 A[u][v] = 1인지만 찾으면 되므로 인접행렬의 경우 O(1)의 시간 복잡도를 가진다.

인접 리스트의 경우, A[u] 를 모두 탐색해야 하므로 u의 차수만큼의 시간이 걸릴 것이다.

 

② 두 정점 u, v가 주어진 경우, v,u의 정점이 존재하는지를 찾을 때

인접 행렬의 경우 A[v][u] = 1인지만 찾으면 되므로 O(1)의 시간이 걸린다.

인접 리스트의 경우에는 A[v] 를 모두 탐색해서 u를 찾아야 하므로 v의 차수만큼 시간이 걸린다.

 

③ 완전 그래프가 주어진 경우

인접리스트와 공간복잡도가 같으므로 인접행렬로 구현하는게 더 간단하고 공간복잡도도 동일할 것이다.

참고) 완전 그래프의 간선의 개수는E = V(V-1)/2 이다.

 

 

그래도 인접 리스트를 쓰는 경우가 훨씬 많으니 인접 리스트를 많이 연습하자ㅎㅎ

 

예를 들어, 정점 X와 연결된 모든 간선을 찾는 경우,

인접행렬의 경우,  A[x][1] 부터 끝까지 탐색해야 하므로 O(v)의 시간이 걸린다.

인접 리스트의 경우, 실제로 연결된 간선만 저장하므로 O(차수)의 시간이 걸린다. 

그래서 인접 리스트의 경우가 시간이 더 빠르다! 공간도 적게 든다! 라고 말할 수 있다.

 

<기타 꿀팁>

인접 리스트는 구현하기가 까다로운데, 링크드 리스트보다 구현하기 쉬운 방법은 없을까?

간선 리스트 방법으로 동적할당 없이 인접 리스트와 비슷한 효과를 내보자!

 

간선 리스트?

: 링크드 리스트를 1차원 배열을 이용해서 구현할 수 있는 방법

 

그래서 간선 리스트로 어떻게 그래프를 구현해?

1) E라는 배열에 간선을 모두 저장한다.

2) 저장된 배열을 오름차순으로 정렬한다.

 

3) 각 간선의 앞 정점을 기준으로 개수를 센다.

i	0	1	2	3	4	5	6
cnt[i]	0	2	4	2	4	3	1

4) cnt[i] 배열을 앞에서부터 누적해 나가며 저장한다.

i	0	1	2	3	4	5	6
cnt[i]	0	2	6	8	12	15	16

이렇게 하면,

 

3으로 시작하는 정점은 6번째부터 8번째 전까지 (E[6] ~ E[7])

4로 시작하는 정점은 8번째~12번째 전까지 (E[8] ~ E[11])

5로 시작하는 정점은 12번째~15번째 전까지 (E[12] ~ E[14]) 임을 알 수 있다.

 

그럼 연결된 정보들을 편하게 사용할 수 있겟징~?

 

 

<관련문제>

13023번: ABCDE