그래프(Graph) - 표현법??

안녕하세요~ 무단이탈(????) 했던 테슬라입니다.
늦어서 죄송합니다.
요즘에 정신없는 나날들이여서 포스트 쓰는것도 깜빡했지 뭐겠어요...

저번시간에 그래프에 대해서 했었지요.
그런데!!! 그 그래프를 어떻게 컴퓨터로 표현해야 할까요?
그냥 그림처럼 편하게 넣을 수 있으면 좋겠지만 그게 말처럼 되는건 아니지요.
그래서 오늘은 그래프의 표현방법에 대해서 해볼게요.

자 컴퓨터로 표현하기 위한 방법으로 인접행렬(Adjacency Matrix)와 인접리스트(Adjacency List)가 있습니다.

우선 인접행렬에 대해서 알아볼까요?
만약 n개의 점을 갖는 그래프라면 인접행렬은 n*n행렬로 표현되고,
만약 두개의 점 Vi, Vj사이에 간선이 존재한다면 (i,j)에 값이 1이고 없다면 0으로 저장합니다.
배열을 이용해 표현이 가능하지요.
물론 방향성과 무방향성그래프가 차이가 있다는것은 당연지사 입니다.
예를 들어볼까요?
 

요런 그래프가 있다고 합시다.
저번에 했던 집합으로 표현해봅시다.
왼쪽의 무방향 그래프를 G1, 오른쪽의 방향성 그래프를 G2라고 한다면,

V(G1) = { 1, 2, 3, 4 }
E(G1) = { (1, 2), (1, 3), (1, 4), (2, 3), (3, 4) }

V(G2) = { 1, 2, 3, 4 }
E(G2) = { <1, 2>, <1, 4>, <2, 3>, <3, 1>, <3, 4> }

겠죠?

먼저 방향성 그래프 G2를 보도록 하지요.

자, 요런 모양이 되지요.
그럼 무방향 그래프 G1을 볼까요?

자 이렇게 됩니다. 왜 그럴까요?
정답은 무방향 그래프의 경우 양쪽 모두를 향했다고 생각하면 되기 때문에 ( (1,2) = (2,1) )
모두 채우면 이렇게 되는것이지요.
음... 그런데 눈치 채셨나요?
 

양쪽이 대칭이지요?
무방향 그래프는 방향성 그래프를 대칭으로 해서 0부분에 1이 대칭되고 있으면 1로 바꿔주면 됩니다.
아 물론 무방향 그래프와 방향성 그래프가 같은 형태라면 말이지요.
하아 그런데 이 인접행렬에도 문제가 있습니다.
이럴 경우를 생각해 봅시다.

자 우리에게 필요한 간선은 1로 표시되고 연결되지 않은 나머지 필요하지 않는 부분은 0으로 처리됩니다.
그런데, 이처럼 채워지는 간선이 적다면... 네, 기억장소에 낭비가 생기겠지요?

그래서 연결되는 간선이 적을 경우 기억장소의 낭비를 줄이기 위한 방법으로 인접리스트가 있습니다.
인접리스트는 인접행렬에서 n개의 행을 n개의 연결리스트로 표현한 것입니다.
즉 n개의 점을 n개의 연결리스트로 표현했다고 할 수도 있는 것이지요.

인접리스트는 연결 되어있는 점들만 리스트로 표현하므로 기억장소를 절약할 수 있지요.
하지만 연결 리스트는 연결주소를 가지고 있어야 하므로,
연결된 간선이 많아진다면면 기억장소의 낭비가 심해질 수 있는 문제를 가지고 있어요.
때문에 자신의 그래프에 따라 잘 선택해서 사용하는 것이 좋겠죠?

자 그럼 인접리스트를 예로 들어볼까요?

아까 예제로 사용했던 그림입니다.
왼쪽의 무방향 그래프를 G1, 오른쪽의 방향성 그래프를 G2라고 한다면,

V(G1) = { 1, 2, 3, 4 }
E(G1) = { (1, 2), (1, 3), (1, 4), (2, 3), (3, 4) }

V(G2) = { 1, 2, 3, 4 }
E(G2) = { <1, 2>, <1, 4>, <2, 3>, <3, 1>, <3, 4> }

이건 그대로지요?
자 우선 G2인 방향성 그래프를 인접리스트로 나타내면,

이 됩니다. 자 1에서 시작되는 간선들의 진입하는 2와 4가 연결리스트에 추가되는 것이지요.
다른것도 이와 마찬가지 입니다.
그럼 무방향 그래프 G1을 볼까요?

음 그냥 정점에 연결되어 있는 다른 모든 정점들을 가지는군요.
인접행렬이 가지고 있는 값을 그냥 연결리스트로 표현한 것입니다.

음 오늘은 여기까지 입니다.
틀린 부분이나 오타가 있으면 알려주세요~