CS 공부 & 면접 맛보기 0x08 [자료구조] : 그래프와 트리의 차이점

그래프와 트리의 차이점

질문

그래프(Graph)와 트리(Tree)의 차이점은 무엇인가요?

면접 답변

그래프(Graph)와 트리는 모두 노드(Node)와 간선(Edge)으로 구성된 자료구조입니다. 그러나 중요한 차이점이 있습니다:

• 그래프는 순환(사이클)이 존재할 수 있으며, 방향 그래프와 무방향 그래프가 존재합니다.
• 트리는 그래프의 특수한 형태로, 사이클이 없고, 모든 노드는 하나의 부모를 가지며, 자식은 최대 2개입니다.
• 트리는 계층적 구조를 표현할 때 사용되며, 그래프는 복잡한 데이터 관계나 경로 탐색에 사용됩니다.

---

설명: 그래프(Graph)란?

• 정의: 그래프는 노드(정점)와 간선(엣지)으로 이루어진 자료구조입니다.
• 구성 요소:
  • 노드(Node): 데이터를 저장하는 정점.
  • 간선(Edge): 노드를 연결하는 선. 방향이 있을 수도 있고, 없을 수도 있습니다.
• 특징:
  • 순환(사이클)이 존재할 수 있음.
  • 방향 그래프와 무방향 그래프 존재.
  • 길찾기, 네트워크, 소셜 그래프 분석에 사용됨.

C++ 그래프 구현 (인접 리스트 방식)

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

class Graph {
public:
    int vertices;
    vector<vector<int>> adjList;

    Graph(int V) {
        vertices = V;
        adjList.resize(V);
    }

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);  // 무방향 그래프
    }

    void printGraph() {
        for (int i = 0; i < vertices; ++i) {
            cout << "노드 " << i << ": ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);

    cout << "그래프 인접 리스트 출력:\n";
    g.printGraph();
    return 0;
}

 

설명: 트리(Tree)란?

• 정의: 트리는 그래프의 특수한 형태로, 사이클이 없는 방향 그래프(DAG)입니다.
• 구성 요소:
  • 루트 노드(Root Node): 트리의 시작점
  • 부모 노드(Parent Node): 상위 노드
  • 자식 노드(Child Node): 하위 노드
• 특징:
  • 사이클이 없음.
  • 루트 노드부터 시작하여 하위 노드로 연결.
  • 연결 요소가 하나이며, 두 노드를 연결하는 경로가 유일함.
  • 부모가 하나만 존재하고, 자식은 최대 2개(이진 트리 기준).
• 사용 사례:
  • 파일 시스템, 계층적 데이터, 이진 탐색 트리

C++ 트리 구현 (이진 트리)

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else {
        root->right = insert(root->right, key);
    }
    return root;
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    insert(root, 3);
    insert(root, 7);

    cout << "이진 트리 중위 순회: ";
    inorderTraversal(root);
    cout << endl;
    return 0;
}

 

그래프와 트리의 비교표

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

순환 여부	순환(사이클) 존재 가능	순환 없음
간선 방향	방향 및 무방향 가능	항상 방향 그래프
부모-자식 관계	부모-자식 관계 없음	부모-자식 관계 명확
연결성	연결 요소가 여러 개일 수 있음	하나의 연결 요소만 존재

결론

• 그래프와 트리는 모두 노드와 간선으로 구성된 자료구조입니다.
• 트리는 그래프의 일종이며, 사이클이 없고 방향성을 가지는 특징이 있습니다.
• 그래프는 복잡한 관계 표현에, 트리는 계층적 데이터 표현에 유리합니다.