Graph

오늘 배운 것

Graph, tree, BST(Binary Search Tree)는 graph라는 큰 뿌리에서 나온 갈래들입니다.

 

그중 graph의 자료구조에 대해 알아보겠습니다.

 

Graph 자료구조

그래프는 노드(node, 또는 vertex 정점), 그리고 노드와 노드를 연결하는 간선(edge)로 구성됩니다.

 

특징

• 한 vertex에서 2개 이상의 경로가 가능
• 무방향 / 양방향 모두 가능
• slef loop가능, loop ciruit 가능
• 순환 / 비순환으로 나뉨.

 

위에 파란 점들은 데이터입니다. 이 데이터를 vertex라고 부르고, 점과 점을 이어주는 간선이 edge입니다.

두 버텍스는 방향성을 가지지 않을수도 있고, 방향성을 가질수도 있습니다. 그리고 스스로를 가르킬 수도 있습니다.

 

 

위 그림과 같이 시작과 끝이 서로 순환도 가능합니다. 시작과 끝이 같은 cycle.

 

버텍스에서 직접 이어져있는 버텍스들을 인접 버텍스라고 합니다. 그리고 이어져 있는 선들을 degree라고 합니다.

왼쪽의 그림에서 A의 인접 버텍스는 B, C, D 3개가 되고, B, C, D는 1개입니다.

방향성이 있을때는 버텍스에서 밖으로 나가는 edge를 out degree, 버텍스에서 안으로 들어오는 edge를 in degree라고 합니다.

엣지에 가중치를 할당된 제일 오른쪽의 그래프도 있습니다. 도로망이나 지하철 통신망 사용료 등 어떤 경로를 탐색할 때 걸리는 시간과 비용등을 나타낼 수 있습니다.

 

그래프 이론에서 한붓그리기 또는 오일러 트레일이 있는데, 그래프의 모든 변을 단 한번씩만 통과하는 트레일을 말합니다.

 

 

그래프를 구현하는 방법 2가지

• 인접 행렬 (Adjacency Matrix)
• 인접 리스트 (Adjacency list)

 

 

인접 행렬

인접 행렬

	A	B	C	D
A	X	O	O	O
B	O	X	X	X
C	O	X	X	X
D	O	X	X	X

 

2차원의 배열에 모든 버텍스의 연결 관계를 담는 방식입니다. 0과 1을 이용한 행렬로 표현할 수 있습니다.

N x N 으로 만들어지기 때문에, 간선의 수와 무관하게 n^2의 메모리 공간이 필요합니다.

버텍스를 잇는 엣지의 여부를 O(1)로 찾을 수 있지만, 모두 순회를 해야하기 때문에 그래프의 간선이 많은 밀집 그래프 일때 사용하면 좋습니다.

 

 

인접 리스트

 

인접 리스트

인접 리스트는 버텍스의 번호만 안다면, 이 번호를 이용하여 쉽게 각 버텍스를 찾을 수 있습니다.

인접하는 노드를 쉽게 찾을 수 있으며, 그래프에 존재하는 모든 간선의 수를 O(n+e)안에 알 수 있습니다.

행렬보다 적은 메모리를 차지하여, 그래프 내에 적은 숫자를 가지는 그래프일때 사용하면 좋습니다.