[자료구조] 그래프, 트리

1. 그래프

각 점을 Vertex 또는 node라고 부르고 점들을 연결하는 간선을 edge라고 부르는 구조이다.

방향성으로 분류하면 무방향(양방향) 그래프와 방향 그래프로 분류 할 수 있다.

한 곳이라도 순환하는 지점이 있으면 순환 그래프, 없으면 비순환 그래프이다.

DAG(Directed Acyclic Graph)라는 것도 있는데 순환하지 않으면서 방향성이 정해져있는 그래프이다.

 

2. 트리 

(순환성이 없는 무방향 그래프

어떤 노드도 루트 노드가 될 수 있다. (어디서 시작을 하든 다른 모든 노드로 갈 수 있음.)

가장 바깥쪽 노드는 리프 노드.

A 노드에서 B 노드로 가는 경로가 반드시 존재하며 유일하다.

노드 개수 = 간선 개수 + 1)

위의 설명은 수학적인 개념이고 코딩쪽에서는 보통 부모 자식 관계가 있는 방향 그래프이다.

방향성이 있기 때문에 루트 노트는 하나다.

 

코드로 그래프를 나타내는 방법.

 

1. 인접행렬

	0	1	2	3
0	0	1	1	1
1	0	0	1	0
2	0	0	0	0
3	0	0	1	0

연결되어 있는 부분을 방향에 맞게 1로 나타내는 방법이 있다.

 

양방향 그래프라고 하면 대각선으로 대칭해서 값을 복사해주면 된다.

	0	1	2	3
0	0	1	1	1
1	1	0	1	0
2	1	1	0	1
3	1	0	1	0

 

2. 인접리스트

연결리스트를 활용하여 나타내는 방법이다.

 

*인접행렬은 N개의 노드에 대해 N^2만큼의 공간을 쓰기 떄문에 시간을 아낄 수 있다.

*인접리스트는 공간을 아끼지만 어떤 노드로 가기위해서는 앞의 노드를 모두 거쳐야 하기 때문(순차탐색)에 시간복잡도아 O(N)이다.