그래프(Graph) vs 트리(Tree)

목차

Graph는 Tree를 포함하는 개념입니다. 즉, 모든 트리는 그래프이지만, 모든 그래프는 트리가 아닙니다.

그래프(Graph)

• 정의
  • 그래프는 노드(Node) 또는 정점(Vertex)들을 연결하는 간선(Edge)의 집합입니다.
• 종류
  • 방향 여부에 따른 분류
    • 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프
    • 무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프
  • 가중치 여부에 따른 분류
    • 가중치 그래프(Weighted Graph) : 간선에 가중치 또는 비용이 할당된 그래프
    • 비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프
  • 순환 여부에 따른 분류
    • 순환 그래프(Cyclic Graph) : 그래프에 최소한 하나의 순환(또는 사이클)이 있는 경우
    • 비순환 그래프(Acyclic Graph) : 그래프에 순환이 없는 경우
• 용어
  • 인접(Adjacent) : 두 정점이 하나의 간선으로 연결되어 있으면 인접하다고 합니다.
  • 차수(Degree) : 노드에 연결된 간선의 수를 의미합니다.
• 표현 방법
  • 인접 행렬(Adjacency Matrix)
    • 인접 행렬은 그래프의 노드 간의 연결 관계를 2차원 배열로 표현하는 방법입니다.
    • n x n 크기의 행렬을 사용하여, 행렬의 (i,j) 위치의 값을 1 또는 가중치로 표현하여 노드 i와 j가 연결되어 있음을 표현합니다. 연결이 없을 경우 0 또는 무한대로 표현합니다.
    • 장점
      • 노드 간의 연결 여부를 O(1)의 시간 복잡도로 바로 확인할 수 있습니다.
    • 단점
      • 크기가 n x n 이므로 노드의 수에 따라 메모리 사용량이 크게 늘어납니다.
      • 희소 그래프의 경우, 많은 메모리가 낭비됩니다.
  • 인접 리스트(Adjacency List)
    • 인접 리스트는 각 노드에 연결된 이웃 노드의 리스트로 그래프를 표현하는 방법입니다.
    • 배열의 각 인덱스는 특정 노드를 나타내며, 해당 인덱스의 위치에는 해당 노드와 인접한 노드들의 리스트가 저장됩니다.
    • 장점
      • 실제로 연결된 노드의 정보만을 저장하므로, 메모리 사용이 효율적입니다.
      • 희소 그래프의 경우 인접 행렬보다 훨씬 메모리 효율적입니다.
    • 단점
      • 두 노드 간의 연결 여부를 확인하기 위해 O(n)의 시간이 걸릴 수 있습니다.

트리(Tree)

• 정의
  • 트리는 순환이 없고, 모든 노드가 연결된 그래프입니다. 
  • 트리는 n개의 노드와, n-1개의 간선으로 이루어져 있습니다. 
    • 문제에서 간선의 개수가 주어져 있지 않고, 노드의 개수와 트리라고 명시되어 있으면 간선의 개수를 n-1개로 생각하고 문제를 풀면 됩니다.
    • 반대로 간선의 개수가 n-1개로 주어지고, 트리라고 명시되어 있으면 노드의 개수를 n개로 생각하고 문제를 풀면 됩니다.
• 종류
  • 일반 트리(General Tree) : 임의의 수의 자식 노드를 가질 수 있는 트리입니다.
  • 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식을 가지는 트리입니다.
  • 이진 탐색 트리(Binary Search Tree) : 이진 트리의 일종으로, 왼쪽 서브트리에 있는 모든 노드의 값이 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 값이 현재 노드의 값보다 큰 특성을 갑습니다.
  • 균형 이진 트리(Balanced Binary Tree) : 트리의 깊이나 높이를 최소화하여 연산의 최악의 시간을 최소화하는 것을 목적으로 합니다. AVL 트리나 Red-Black 트리가 이에 해당됩니다.
  • 이 외에도 다양한 트리 종류가 존재합니다. (일반적으로 이진 트리 문제가 자주 나와 트리하면 이진 트리로 생각하고 푸는 실수를 할수도 있습니다. 문제에서 반드시 명시적으로 이진 트리라고 주어졌을 경우에만 이진 트리로 풀고, 그것이 아니라면 한 노드가 여러개의 자식 노드를 가질 수 있음을 생각해야합니다.)

아래 그림은 이진 트리의 예시입니다. 트리라고 해서 반드시 자식 노드가 두 개가 아닙니다. 자식 노드가 3개 이상일 수도 있습니다. (출처 : 나무위키)

 

그래프(Graph) vs 트리(Tree)

• 모든 트리는 그래프이지만, 모든 그래프가 트리는 아닙니다.
• 트리는 순환이 없는 특별한 유형의 그래프입니다.(트리는 노드가 n개면, 간선의 개수는 n-1개)
• 그래프는 순환을 포함할 수 있지만 , 트리는 순환을 포함할 수 없습니다.