1.tree

나무를 거꾸로 뒤집어 놓은 형태이며, 그래프의 여러 구조 중 단방향 그래프의 한 구조이다. 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아서 트리 구조라 한다.

특징으로는

• 데이터가 바로 아래 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 하나의 데이터 하위 여러 개 데이터 존재하는 비선형 구조이다.

구성

• 루트 : 꼭짓점
  • 여러 개의 데이터를 간선(edge)으로 연결
• 노드 : 각 데이터
  • 두 개의 위/아래 연결된 노드는 부모-자식 관계를 갖는다.
• 부모 노드 : 현 노드 기준 상위 노드(상대적으로 루트와 가까움)
• 자식 노드 : 현 노드 기준 하위 노드
• 리프 노드 : 자식이 없는 노드(트리 구조의 끝지점)

측정

• 깊이(depth)
  • 루트부터 하위 특정 노드까지의 깊이
  • 루트부터 하향(루트는 깊이 0)
• 레벨(Level)
  • 같은 깊이 가지는 노드 그룹
  • 같은 레벨에 있는 노드는 형제노드라 한다.
• 높이(Height)
  • 리프 노드를 기준으로 루트까지의 높이 표현
  • 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 갖는다.
• 서브트리
  • root 하위 트리 구조를 갖춘 작은 트리 지칭

2.Graph

여러개의 점들이 서로 복잡하게 연결된 자료구조를 의미한다. 기존 수학의 그래프가 아닌 복잡한 네트워크망 구조로 이해하면 되겠다.

2-1.인접행렬

두 정점을 이어주는 간선이 있다면 두 정점은 인접한다. 인접행렬은 이를 2차원 배열 형태로 나타낸 것으로 A점과 B점이 이어져 있다면 1(true), 그렇지 않다면 0(false)로 표시한 일종의 표현이다.

위 그래프에서

• A의 진출차수는 2개이다. (A->B || A->D)
  • [1][0]==1
  • [1][2]==1

인접행렬은 언제 사용할까?

• 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인에 용이하다.
  • A점에서 B점으로 진출하는 간선 여부 파악을 위해 n*m 행렬에 어떤 값이 저장되었는지 바로 확인 가능하다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.

2-2.인접 리스트

각 정점이 어떤 정점과 인접하는지를 리스트 형태로 표현한다. 정점마다 하나의 리스트를 가지며, 자신과 인접한 정점을 담고 있다. 또한 우선순위를 중요시하지 않으며, 우선순위가 중요할 경우 quequ와 heap을 사용하는 것이 합리적이다.

인접 리스트는 메모리를 효율적으로 사용하고 싶을 경우 사용한다.
인접행렬은 연결 가능한 모든 경우의 수를 저장하므로 상대적으로 많은 메모리를 소모한다.

---

• 그래프 용어 정리

  • 정점(Vertex) : 노드(node), 데이터가 저장되는 그래프의 기본 원소

• 간선(edge) : 정점 간의 관계(정점을 이어주는 선)
• 인접 정접(adjacent vertex) : 하나의 정점에서 간선으로 직접 연결된 정점
• 가중치 그래프(weighted graph) : 연결 강도
• 비가중치 그래프(unweighted graph) : 연결 강도 적혀있지 않는 그래프
• 무(방)향 그래프(undirected graph) : 양방향으로 움직일 수 있는 그래프
• 진입/출차수(in/out-degree) : 정점에 진입/출하는 간선의 갯수
• 자기루프(self loop) : 정점에서 진출한 간선이 곧바로 자신에게 진입하는 경우
• 사이클(cycle) : 한 정점에서 해당 정점으로 돌아갈 수 있는 경우 사이클이 있다고 표현한다.