C++ 자료구조 - 그래프

그래프의 표현

위의 그래프는 정점(vertex)이 6개, 간선(edge)이 8개 있다. (정점들을 연결한 게 간선이다.)

간선에 방향이 없기 때문에, 방향이 없는 그래프이다.

정점은 단순하게 그냥 숫자를 저장하면 된다. (숫자가 아닌 다른 게 vertex여도 숫자로 바꿔서 저장하면 된다.)

vertex : {1, 2 ,3, 4, 5, 6}

edge : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)}

 

간선(edge)을 저장하는 방법은 여러 가지가 있다.

 

1. 인접 행렬 (Adjacency - matrix)

정점의 개수를 V라고 했을 때, VxV 크기의 이차원 배열을 이용한다.

A[i][j] = 1 (i -> j 간선이 있을 때), 0 (없을 때)

 

그래서 위의 그래프의 간선을 인접 행렬을 이용하면

	1 2 3 4 5 6

1	0 1 0 0 1 0
2	1 0 1 1 1 0
3	0 1 0 1 0 0
4	0 1 1 0 1 1
5	1 1 0 1 0 0
6	0 0 0 1 0 0

이렇게 나타낼 수 있다. ( 1 - 2 가 연결돼있으니까 (1, 2), (2,1)에 1)

이 그래프는 방향이 없는 그래프이기 때문에 i - j 연결된 게 있으면 i -> j , j -> i로 생각하여 둘 다에 1을 넣어준다!!

만약에 가중치가 있다면 행렬에 1 대신 그 가중치 만큼을 저장해준다.

 

2. 인접 리스트 (Adjacency - list)

리스트를 이용해서 구현한다.

A[i] = i와 연결된 정점 을 리스트로 포함하고 있다.

 

위의 그래프의 간선을 인접 리스트를 이용하면

A[1] 2 5
A[2] 1 3 4 5
A[3] 2 4
A[4] 3 5 2 6
A[5] 1 2 4
A[6] 4

이렇게 나타낼 수 있다. (정점 1은 2와 5랑 연결돼있어서 A[1]은 2, 5)

리스트는 크기를 동적으로 변경할 수 이써야 하므로 링크드 리스트나 길이를 동적으로 변경할 수 있는 배열을 사용한다.(C++에서는 벡터를 사용하자)

만약에 가중치가 있다면 가중치도 같이 저장해주자

 

3. 간선 리스트 (Edge List)

배열을 이용해서 구현하고 간선을 모두 저장한다.

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

 

위의 그래프의 간선을 간선 리스트를 이용하면

E[0] = 1 2
E[1] = 1 5
E[2] = 2 3
E[3] = 2 4
E[4] = 2 5
E[5] = 5 4
E[6] = 4 3
E[7] = 4 6
E[8] = 2 1
E[9] = 5 1
E[10] = 3 2
E[11] = 4 2
E[12] = 5 2
E[13] = 4 5
E[14] = 3 4
E[15] = 6 4

이렇게 간선들을 저장할 수 있다.

그런데 간선 리스트는 각 간선의 앞 정점을 기준으로 개수를 세기 때문에 다시 저장해 보면

E[0] = 1 2
E[1] = 1 5
1 끝났으니까 이제 2 세기
E[2] = 2 1
E[3] = 2 3
E[4] = 2 4
E[5] = 2 5
2 끝났으니까 3 세기
E[6] = 3 2
E[7] = 3 4
3 끝났으니까 4 세기
E[8] = 4 2
E[9] = 4 3
E[10] = 4 5
E[11] = 4 6
4 끝났으니까 5 세기
E[12] = 5 1
E[13] = 5 2
E[14] = 5 4
5 끝났으니까 6 세기
E[15] = 6 4

각 정점의 간선의 개수를 세보자.

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

간선의 누적 값을 보자.

for (int i = 1; i <= n; i++) {
	cnt[i] = cnt[i - 1] + cnt[i];
}

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

4번 정점과 연결된 간선은 E배열에서 8번부터 11번 까지인데 이거는 cnt[3]부터(==8) cnt[4]-1(==11) 까지인 것을 알 수 있다!!이 표에서 보면 i번 정점과 연결된 간선은 E배열에서 cnt[i-1]부터 cnt[i]-1까지이다.