Graph에 대해서

그래프는 알고리즘에서 자주 나오고 또 중요한 자료구조입니다.

최단거리를 찾는 다익스트라 알고리즘이나 특정 지점을 탐색하는 DFS, BFS가 대표적입니다.

 

서론은 짧게 하고, 본론으로 들어가겠습니다.

 

 

Graph란 무엇인가?

그래프는 정점과 간선로 이루어진 구조라고 할 수 있습니다.

여기서 정점은 보통 node, vertex라고 부르며 간선은 edge라고 부릅니다.

*주의할 점 : 간선이 존재하지 않으면 그래프가 아닙니다. 

 

그래프를 시각적으로 보자면 이렇습니다.

 

 

A, B, C라는 3개의 노드와 3개의 간선으로 이루어진 간단한 그래프입니다.

후에 설명드릴 내용으로 조금 더 자세히 설명해 드리자면 이 그래프는 무방향 그래프로 방향성이 존재하지 않는 그래프입니다.

 

바로 다음으로 넘어가도 되지만 그래프의 잘못된 예도 잠깐 보여드리겠습니다.

 

 

위의 이미지에는 간선이 없는 노드로만 이루어진 구조로, 그래프가 아닙니다.

그럼 이제 그래프의 종류를 알아보겠습니다.

 

 

Graph의 종류

무방향 그래프

무방향 그래프는 위에서 설명했듯이 간선의 방향성이 존재하지 않는 그래프라고 할 수 있습니다.

예시로 가장 많이 드는 그래프이기도 합니다.

 

방향 그래프

방향 그래프는 무방향 그래프와 완전히 반대되는 개념으로 간선의 방향성이 존재하는 그래프입니다.

여기서 더 구별하자면 단방향/양방향 그래프가 있지만 간단히 설명하자면 SNS에서 팔로우를 할 때 서로 팔로우하는 것과 한쪽만 팔로우하는 그래프라고 생각하면 됩니다.

 

가중치 그래프

가중치 그래프는 간단히 간선에 특정 값이 추가되는 방식이라고 보면 됩니다.

위 그래프에서는 방향 그래프로 표현했지만, 무방향도 가능합니다.

특히, 가중치 그래프는 최단 거리 혹은 값을 기준으로 판단해야하는 상황에서 자주 쓰입니다.

 

다른 그래프로는 연결 그래프, 비연결 그래프가 있지만 간단히 설명하자면, 연결 그래프는 모든 노드에 간선이 연결되어 있는 그래프이고, 비연결 그래프는 하나 이상의 노드가 간선에 연결되어있지 않은 그래프입니다.

 

다양한 그래프가 더 있지만 여기까지 설명하고 넘어가겠습니다.

 

 

그럼 Graph는 왜 쓰는가?

사실 아직 그래프를 많이 써보지 않아서 잘 모릅니다.

그래도 제 경험상 설명해보자면 가장 간단하게 가장 많은 상황을 표현할 수 있어서라고 생각합니다.

이 부분은 댓글이나 제가 후에 수정할 때 다시 써보겠습니다.

 

 

표현 방법은?

그래프의 표현방법은 다양합니다.

그중에서 가장 많이 쓰이는 방법 2가지를 설명드리겠습니다.

 

1. 인접 행렬

위의 그래프를 인접 행렬로 표현해 보자면

 

From \ to	A	B	C	D
A	0	1	1	1
B	1	0	0	1
C	1	0	0	1
D	1	1	1	1

 

이렇게 됩니다.

위 그래프가 무방향 그래프였기 때문에 대칭성을 가진 형태가 나옵니다.

만일 방향 그래프라면 대칭성이 깨질 수 있으며, 가중치 그래프인 경우에는 0과 1이 아닌 해당 간선에 해당된 가중치 값을 대입하면 됩니다.

 

 

2. 인접 리스트

인접 행렬에서의 그래프를 다시 인접 리스트로 표현해 보겠습니다.

 

A : B -> C -> D

B : A -> D

C : A -> D

D : A -> B -> C -> D

 

이를 통해 알 수 있는 사실은, 인접 리스트는 순서에 상관없이 해당 노드에 연결되어 있는 이웃 노드들을 나열하는 것입니다.

 

이렇게 알아봤는데 그럼 어떻게 활용할까?라는 질문이 생길 수 있습니다.

이 질문에 대해서는 다음에 연결 지어서 해보겠습니다.