트리 vs 그래프

트리와 그래프는 모두 정점(Vertex)과 간선(Edge)으로 구성된 자료구조

---

트리(Tree)의 특징

1. 정의:
   • 트리는 사이클이 없는 연결된 그래프
   • 모든 노드가 하나의 루트에서 시작하여 부모-자식 관계로 연결
2. 특징:
   • N개의 정점이 있다면, N-1개의 간선이 존재
   • 사이클이 존재하지 않음 (Cycle-Free).
   • 항상 연결 그래프 (Connected Graph).
   • 노드 간에 유일한 경로가 존재합니다 (두 노드 사이의 경로는 하나뿐).
3. 루트 노드:
   • 트리에는 반드시 루트 노드가 존재하며, 이는 트리의 최상위 노드
   • 트리의 탐색은 이 루트 노드에서 시작
4. 방향성:
   • 트리는 일반적으로 방향성이 있으며, 부모 → 자식으로 진행

---

그래프(Graph)의 특징

1. 정의:
   • 그래프는 정점과 간선으로 구성된 자료구조로, 간선이 정점 쌍을 연결
   • 방향성이 있을 수도 있고 없을 수도 있음음
2. 특징:
   • N개의 정점이 있더라도 간선의 개수에는 제한이 없음 (트리처럼 N-1개의 간선 필요 없음).
   • 사이클이 존재할 수 있음.
   • 연결되지 않은 그래프도 존재할 수 있음 (Disconnected Graph).
   • 노드 간에 여러 개의 경로가 존재할 수 있음.
3. 루트 노드:
   • 그래프는 반드시 루트 노드가 존재하지 않아도 됨
4. 방향성:
   • 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨

---

트리와 그래프 구분 방법

1. 노드와 간선의 수:
   • 트리: 정점(N)과 간선(M)이 주어졌을 때, 항상 M=N−1M = N - 1이어야 함
   • 그래프: M≠N−1M \neq N - 1일 수 있음
2. 연결 여부:
   • 트리는 모든 정점이 하나로 연결된 연결 그래프여야 함
   • 그래프는 연결되지 않은 비연결 그래프일 수도 있음
3. 사이클 존재 여부:
   • 트리는 사이클이 없음
   • 그래프는 사이클이 존재할 수 있음
4. 유일한 경로:
   • 트리는 두 노드 사이에 유일한 경로만 존재
   • 그래프는 두 노드 사이에 여러 경로가 존재할 수 있음

---

예제

트리 예제:

5개의 정점, 4개의 간선
정점: {0, 1, 2, 3, 4}
간선: {(0, 1), (0, 2), (1, 3), (1, 4)}

트리 조건:

• M=N−1M = N - 1: 4=5−14 = 5 - 1, 조건 만족.
• 사이클 없음.
• 모든 정점이 하나로 연결됨.

그래프 예제:

5개의 정점, 5개의 간선
정점: {0, 1, 2, 3, 4}
간선: {(0, 1), (1, 2), (2, 3), (3, 0), (3, 4)}

그래프 조건:

• M≠N−1M \neq N - 1: 5≠5−15 \neq 5 - 1, 조건 불만족.
• 사이클 존재: (0 → 1 → 2 → 3 → 0).
• 모든 정점이 연결되었지만, 트리가 아님.

---

코드로 구현된 확인 방법

트리인지 확인하는 코드:

1. 정점 NN과 간선 MM을 확인
2. 간선의 수가 M=N−1M = N - 1인지 확인
3. 사이클이 존재하지 않는지 확인
4. 모든 정점이 연결되었는지 확인

#include <iostream>
#include <vector>
using namespace std;

bool isTree(int N, vector<pair<int, int>>& edges) {
    // 트리 조건: 간선 수 == 노드 수 - 1
    if (edges.size() != N - 1) return false;

    // 인접 리스트 생성
    vector<vector<int>> graph(N);
    for (auto& edge : edges) {
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }

    // 사이클 및 연결 여부 확인 (DFS)
    vector<bool> visited(N, false);
    bool hasCycle = false;

    function<void(int, int)> dfs = [&](int node, int parent) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, node);
            } else if (neighbor != parent) {
                hasCycle = true;
            }
        }
    };

    // 루트 노드(0)에서 탐색 시작
    dfs(0, -1);

    // 모든 노드가 연결되어 있는지 확인
    for (bool v : visited) {
        if (!v) return false; // 연결되지 않은 노드가 있음
    }

    return !hasCycle; // 사이클이 없어야 트리
}

int main() {
    int N = 5; // 정점 수
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}}; // 간선 목록

    if (isTree(N, edges)) {
        cout << "이 그래프는 트리입니다." << endl;
    } else {
        cout << "이 그래프는 트리가 아닙니다." << endl;
    }

    return 0;
}

---