250213 TIL - 자료구조 (그래프, 트리)

그래프 Graph

"정점들과 그 정점들을 연결하는 간선들로 이뤄진 자료 구조"

정점 Node, Vertex

연결된 개체 하나하나

간선 Edge

정점들을 이어주는 선 (정점 간의 관계를 표현해줌)

차수 Degree

하나의 정점에 연결된 간선 개수

경로 Path

하나의 정점에서 다른 정점으로 갈 때 거치게 되는 간선과 정점들의 집합

방향성 Directed, Undirected

간선의 연결이 단방향인지, 양방향인지

순환성 Cyclic, Acyclic

모든 간선을 한번씩만 지나며 모든 정점을 순회할 수 있는지, 순회할 수 없는지

곁들이는 용어
이외에도 모든 정점을 순회하는 경로인 Cycle, 노드가 본인에게 간선을 연결하는 Self-Loop 등이 있슴다!!

---

트리 Tree

"부모-자식 관계로 계층화된 노드들과 그 노드들을 연결하는 간선들로 이뤄진 자료 구조"
"그래프의 일종"

최상위 노드 Root

부모 중에 제일 부모인 노드, 유일한 존재

최하위 노드 Leaf

자식 중에 제일 자식인 노드

간선 Edge, Branch

노드들을 이어주는 선, 트리에선 무조건 단방향 Directed

형제자매 관계 Sibling

같은 부모 노드에서 갈라져 나온 노드들

노드 크기 Size

하나의 노드의 자식 노드 개수와 본인을 포함해 센 값

노드 깊이 Depth

특정 노드가 최상위 노드로부터 거쳐온 계층의 수

노드 단계 Level

노드들의 세대를 일컫는 말

트리 높이 Height

최상위 노드로부터 최하위 노드까지 거치는 계층의 수

곁들이는 정보 두 가지
1) 트리에서 어느 한 노드를 제거하고 남는 노드와 간선들의 형태도 그대로 트리라는!!
2) 개별 트리들의 집합 형태의 자료구조를 포레스트라고 함!!