[알고리즘] 트리, 그래프에 대하여

그래프(Graph)

: 사이클이 존재하는 그래프

 

 

개체는 노드(Node)

관계는 간선(Edge)

 

 

무방향 그래프 (Undirected Graph)

A와 B가 연결되어 있으면 B와 A도 연결되어 있다

 

방향 그래프 (Directed Acyclic Graphs)

간선에 방향이 존재하는 그래프

A → C 일 때, C → A 인 건 아니다

여기서 사이클 이라는 중요 개념이 등장한다

💡 사이클 : 시작 정점과 끝나는 정점이 동일한 경로

 

사이클이 존재하지 않는 방향 그래프는 DAG(Directed Acyclic Graphs)

트리는 사이클이 존재하지 않는 DAG 이다

가중치 그래프

간선에 가중치, 즉 비용이 추가된 그래프이다

A → B로 갈때 10 만큼의 비용이 필요하다, 라는 느낌

 

 

 

트리(Tree)

이진 트리

: 사이클이 존재하지 않는 방향 그래프, DAG

조직도 라고 생각하면 이해가 쉽다

 

그래프는 개체 간의 관계 를 표현한다면

트리는 개체를 계층 으로 표현한다

 

최상위 루트 노드가 존재하고

루트 노드를 시작으로 부모, 자식 관계가 형성된다

 

두 정점은 한 개의 경로를 가지고, 부모 자식으로 현결된 Top to Bottom 방식이다

트리는 사이클을 형성하면 안된다

 

탐색 알고리즘

• 전위 순회
  • 자신 → 왼쪽 → 오른쪽
• 중위 순회
  • 왼쪽 → 자신 → 오른쪽
• 후위 순회
  • 왼쪽 → 오른쪽 → 자신

 

트리 종류

• 이진 트리
  • 각 노드가 최대 두 개의 자식 노드를 가진다
• 이진 탐색 트리
  • 이진 트리의 일종이다
    • 왼쪽 가지에는 노드 값보다 작은 값
    • 오른쪽 가지에는 노드 값보다 큰 값