[Data Structure] 그래프(Graph)와 트리(Tree)

Graph란?

• Node와 Node를 연결하는 Edge를 하나로 모아 놓은 비선형 자료구조
• 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델
• 방향성에 따라 Undirected Graph와 Directed Graph로 나누어짐
  • Undirected Graph
    • 간선을 통해 양방향으로 진행
    • 노드A와 노드B를 연결하는 간선이 존재하면 (A, B)로 표현
  • Directed Graph
    • Edge에 방향성이 존재
    • A -> B이면 <A, B>로 표현
    • <A, B>와 <B, A>는 다름
• 가중치 그래프(Weighted Graph)
  • Edge에 비용이나 가중치가 할당된 그래프로 네트워크라고도함

Graph의 특징

• 그래프는 네트워크 모델
• 2개 이상의 경로가 존재 할 수 있음
• root node가 존재하지 않음
• 부모-자식 관계가 존재하지 않음
• 순회는 DFS 또는 BFS로 이루어짐
• 순환 또는 비순환함
• 간선의 유무는 그래프에 따라 다름
• 인접 리스트와 인접 행렬로 구현할 수 있음

Tree란?

• Node와 Edge로 이루어진 비선형 자료구조로 계층적 모델
• 그래프의 한 종류로 Cycle이 없는 하나의 연결 그래프

Tree의 특징

• 트리는 하나의 Root Node를 가짐
  • Root Node는 0개 이상의 자식 노드를 가짐
  • 자식 노드도 0개 이상의 자식 노드를 가짐
• 트리는 순환하지 않음
• Node가 N개인 트리는 항상 N-1개의 Edge를 가짐
• 임의의 두 Node간의 경로는 유일함