Graph

• 노드 : 데이터를 표현하는 단위 (열매)
• 엣지 : 데이터를 연결해주는 단위 (나뭇 가지)
• 루트 노드 : 최상위 데이터 (가장 높은 곳에 있는 열매)
• 리프 노드 : 최 하위 데이터 (가장 낮은 곳에 있는 열매)
• 디그리(degree) : 각 노드가 가진 가지의 수

그래프의 종류

• 방향성이 없는 그래프
• 방향성이 있는 그래프
• 가중치가 있는 그래프
• 순환 그래프
• 비 순환 그래프

Tree

• 방향성이 없는 그래프
• 한 노드에서 다른 노드로 이르는 길이 단 하나뿐인 그래프
• 비순환 그래프
• N개의 노드로 이루어져 있다면 N-1개의 엣지를 갖는다.

그래프 구현하기

보통 다음 두 가지 방법으로 구현한다.

1. 인접행렬(Adjacent Matrix)

인접행렬은 V개의 노드로 이루어진 그래프를 VxV 행렬로 구현하는 방법이다. 행과 열을 사용해서 노드의 연결관계를 표시할 수 있다. 예를 들어 노드 i와 노드 j가 연결되어 있다면 행렬의 A[i][j]의 값은 1, A[j][i]의 값도 1이 된다. 노드가 연결되어있지 않는 행렬 원소는 값이 0이다.

특별한 그래프

• 가중치 그래프 : 행렬의 원소값이 1이 아닌 가중치 값이 된다. 연결되어 있다면 각 가중치 값, 연결되어 있지 않다면 0
• 방향성이 있는 그래프: 노드i에서 노드 j로 연결되어 있는 단방향 그래프라면 A[i][j] 값은 1이지만 A[j][i]의 값은 1이 아닐 수 도 있다.

인접행렬 방식의 특징

메모리를 많이 사용하면서 시간 복잡도를 낮춘 구현 방법이다.

• n개의 노드 연결관계를 표현하기 위해 n^2개의 데이터를 사용한다. 메모리 복잡도는 O(n^2)이다.
• 접근 시간은 O(1)이다. 행렬이기 때문에 접근 시간은 매우 빠르다.

2. 인접 리스트(Adjacent List)

인접 행렬방식은 사실 많은 데이터를 낭비하고 있다. n x n개라는 큰 공간에서 띄엄띄엄 연결되는 그래프는 값이 1인 데이터보다 0인 데이터가 훨씬 더 많이 차지하고 있기 때문이다. 따라서 좀 더 효율적인 메모리 이용구조를 생각하게 되었다. 기존에 0이었던 데이터들을 제거하면 어떨까?

리스트를 각 원소로 갖는 배열

• n개의 노드를 표현하기 위해 n개의 배열 A[n]을 사용한다.
• 각 원소는 리스트로 표현된다.
• i번째 노드에 연결된 j노드를 표시하려면, A[i] 리스트에 j를 추가한다.
• 마찬가지로 A[j]리스트에도 i를 추가한다.

특별한 그래프

• 가중치 그래프 : i번째 노드에 가중치 k로 연결된 j노드를 표시하려면 A[i]리스트에 pair(파이썬이라면 튜플)을 사용해서 (j, k)를 추가한다. 마찬가지로 A[j]리스트에도 (i,k)를 추가한다.
• 비순환 그래프 : i번째 노드에 단방향으로 연결된 j 노드를 표시하려면 A[i]리스트에 j를 추가한다. A[j]리스트에는 추가하지 않는다.

인접 행렬 방식의 특징

인접 리스트 방식은 메모리 사용을 낮추는 대신 시간 복잡도를 희생한 방식이다.