1. 무향 그래프, 유향 그래프

그래프는 현상이나 사물의 정점과 간선으로 표현하는 것으로, 정점(Vector)은 대상이나 개체를 나타내고 간선(Edge)은 이들 간의 관계를 나타낸다.

예를 들면 위 그래프를 친구간의 관계로 표현한다고 하면, 각 알파벳은 사람이고, 간선은 친구관계를 의미한다.

즉 A의 친구들은 [B,C,D,E]등이고 F의 친구는 [C,E]이다.

그래프에는 대표적으로 2가지 종류가 있는데 대표적으로 위 그래프와 같은 무향 그래프와 아래와 같은 유향 그래프이다.

그리고 그래프의 간선은 값을 가질 수 있다. 이런거를 가중치라고 한다.

가중치를 가진 유향 그래프

2. 인접 행렬(Adjacency Matrix)

이런 그래프를 인접 행렬로 표현 할 수 있는데, G = (V,E)에서 정점의 총수가 n이라 했을 때 우선 n ** 2의 행렬을 만든 후 둘 간의 간선이 있으면 1을 할당한다.

2-1. 무향 그래프(가중치 X)

무향 그래프

A B C D E F
A 0 1 1 1 1 0
B 1 0 1 0 0 0
C 1 1 0 0 0 1
D 1 0 0 0 1 0
E 1 0 0 1 0 1
F 0 0 1 0 1 0
위의 그래프를 아래에 표로 표현한것이다.

무향 그래프 같은 경우에는 인접 행렬이 대칭을 이룬다.

만약 가중치를 가지면 아래와 같이 표현 할 수 있다.

2-2. 무향 그래프(가중치 O)

가중치를 가진 무향 그래프

A B C D E F
A 0 9 7 5 6 0
B 9 0 9 0 0 0
C 7 9 0 0 0 5
D 5 0 0 0 5 0
E 6 0 0 5 0 1
F 0 0 5 0 1 0
이렇게 가중치를 표현할 수 있다.

이번에는 유향 그래프를 해보자

2-3. 유향 그래프(가중치 O)

A B C D E F
A 0 8 0 5 6 0
B 0 0 6 0 0 0
C 7 0 0 0 0 4
D 0 0 0 0 5 0
E 0 0 0 0 0 2
F 0 0 5 0 1 0
유향 그래프는 무향 그래프와 다르게 인접 행렬이 대칭을 가지지 않는다.

그 밖에 링크드 리스트와 해시 테이블 등이 있다.