16. 그래프(Graph)와 트리(Tree)란?

 

 

 

"그래프(Graph)와 트리(Tree)"

 

 

개발을 하다보면 데이터가 나열만 되는 게 아니라, 서로 연결되는 관계로 등장하는 순간이 많다.

 

예를 들어 

Unity에서 Hierarchy는 부모-자식 구조로 묶이고,

 길찾기·퀘스트 선행 조건·상태 전이처럼 관계가 복잡해지면 노드와 연결로 설계하는 편이 더 자연스럽다.

 

그래서 오늘은 그래프(Graph)와 트리(Tree) 가 무엇인지, 둘의 차이,

C#에서 어떻게 표현하는지 정리해볼 예정이다.

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

1) 그래프(Graph)란?

그래프는 노드(Node)와 간선(Edge)으로 연결 관계를 표현하는 자료구조다.

 

무방향 그래프

A—B처럼 양방향 연결

(친구 관계, 길 연결)

방향 그래프

A→B처럼 방향이 있는 연결

(의존성, 흐름)

가중치 그래프

간선에 비용/거리/시간 같은 값이 붙음

(최단 경로 문제)

사이클(cycle)

A→B→C→A처럼 순환이 생길 수 있음

 

2) 트리(Tree)란?

 

트리는 그래프의 특수한 형태로, 

보통 계층(부모-자식) 구조를 표현할 때 사용한다.

 

트리의 핵심 특징
사이클이 없음 (순환 없음)
노드 N개면 간선은 N-1개
보통 루트(root)를 기준으로 위→아래로 내려가는 계층 구조

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

3) 트리 vs 그래프, 언제 뭘로 생각해야 할까?

 

트리로 보는 게 자연스러운 상황

부모가 있고 자식이 따라오며
한 노드가 위에서 아래로 구조적으로 묶이는 형태

(Transform Hierarchy, UI 계층, 본(Bone) 구조)

 

 

그래프로 보는 게 자연스러운 상황

연결이 계층이 아니라 그물망처럼 얽히며
한 노드가 여러 방향으로 이어지고

순환/가중치/다중 경로가 존재하는 형태

(길찾기, 퀘스트 선행 조건, 의존 관계, 상태 전이)

 

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

4) 그래프&트리 예시 코드

 

 

그래프

 

C#에서 그래프는 보통 Dictionary로 정점을 관리하고,

각 정점의 이웃을 List로 저장하는 인접 리스트 형태로 표현한다.

 

using System.Collections.Generic;

Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>
{
    { 0, new List<int> { 1, 2 } },       // 정점 0의 이웃
    { 1, new List<int> { 0, 2, 3 } },    // 정점 1의 이웃
    { 2, new List<int> { 0, 1 } },       // 정점 2의 이웃
    { 3, new List<int> { 1, 4 } },       // 정점 3의 이웃
    { 4, new List<int> { 3 } },          // 정점 4의 이웃
};

 

 

 

 

 

 

트리

 

C#에서 트리는 보통 노드를 클래스로 만들고,

각 노드가 자식 노드(Left/Right)를 참조하도록 연결해 계층 구조를 표현한다.

 

using System.Collections.Generic;
using UnityEngine;

namespace TreeEx
{
    public class Node
    {
        public int Value;
        public Node Left;
        public Node Right;

        public Node(int value)
        {
            Value = value;
        }
    }

    public class TreeManager : MonoBehaviour
    {
        private Node root;

        private void Start()
        {
            //         0
            //      1     2
            //    3  4  5  6

            root = new Node(0);

            root.Left = new Node(1);
            root.Left.Left = new Node(3);
            root.Left.Right = new Node(4);

            root.Right = new Node(2);
            root.Right.Left = new Node(5);
            root.Right.Right = new Node(6);
        }
    }
}

 

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

4) 오늘의 한 줄 요약

 

『  트리와 그래프는 노드와 연결로 관계를 표현하는 자료구조이며, 트리는 사이클이 없는 계층형 그래프의 특수한 형태다. 』