트리와 그래프 내용 정리

트리와 그래프

그래프란?

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

 출처 : 위키백과

그래프의 종류

1. 무방향 그래프

• 간선에 방향이 존재하지 않아 양방향으로 이동이 가능하다.
• (A,B), (B,A)는 동일한 간선이다

2. 방향 그래프

• 간선에 방향이 존재하는 그래프로 지정된 방향으로만 이동이 가능하다.
• A->B로 가는 간선은 <A,B>로 표시하며 <B,A>와는 다른 간선이다.

3. 가중치 그래프

• 간선에 비용이나 가중치가 할당된 그래프이다.

4. 완전 그래프

• 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프

5. 단순 그래프

• 두 정점 사이의 연결선이 최대 한 개인 그래프

6. 부분 그래프

• 원래의 그래프에서 일부 정점이나 간선을 제거해 만든 그래프

그래프 구현 방법

그래프 구현 방법은 인접리스트 방법과 인접 행렬 방법 두 가지로 나뉜다.

인접 리스트 방법

• 일반적인 그래프 표현 방법
• 모든 정점을 인접 리스트에 저장하고, 각각의 정점에 대해 인접한 정점들을 리스트로 표현한 것이다. 구현 방식
• 각각의 연결리스트 헤더에 모든 정점을 하나씩 저장한다.
  이때 헤더 노드들은 하나의 배열로 붙어있다.
• 헤더에 연결되는 연결 리스트에는 해당 헤더가 저장하고 있는 노드에 인접한 노드들을 저장한다.
• 무방향 그래프인 경우 (a,b)는 a의 연결 리스트에 표시되고, b에도 표시해준다.

인접 행렬 방법

• n x n 불린 행렬로써 matrix[i][j]가 참이라면 i->j로의 간선이 존재한다는 의미이다.
• 노드가 n개인 그래프를 인접행렬로 표현하면 간선 수와 무관하게 n^2의 메모리 공간이 필요하다.
• 인접 리스트는 어떤 노드에 대해 인접한 노드에 대해 바로 찾을 수 있지만 인접 행렬을 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회하여야 하므로 효율성이 떨어진다.

트리란?

• 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.
• 트리에는 사이클이 존재할 수 없다.
• 최상위 노드를 루트 노드(root node)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 트리 종류

1. 이진트리

• 각 노드가 최대 두 개의 자식을 갖는 트리

2. 이진 탐색 트리

• 이진트리의 속성을 만족하고 모든 노드에 대해 왼쪽 서브 트리는 해당 노드보다 작은 값이, 오른쪽 서브트리는 해당 노드보다 큰 값을 가져야 한다.

3. 완전 이진트리

• 트리의 모든 높이에서 노드가 꽉 차 있는 이진트리
• 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진트리