트리[ Tree ]와 그래프[ Graph ]의 기초

트리와 그래프는 컴퓨터 과학에서 매우 중요한 자료구조입니다. 이 글에서는 트리와 그래프의 기초적인 개념과 차이점을 이해하고, Java와 C 언어로 기본적인 구현 예제를 통해 학습해 보겠습니다.

트리란 무엇인가?

트리는 계층적 구조를 가진 자료구조로, 노드와 간선으로 구성됩니다. 트리는 여러 노드가 연결된 구조지만, 특정한 규칙을 가지고 있어 그래프와는 다른 특성을 가집니다.

• 루트 노드 (Root Node): 트리의 최상위에 위치한 노드로, 트리의 시작점입니다.
• 자식 노드 (Child Node): 특정 노드에서 이어져 나오는 노드들입니다.
• 부모 노드 (Parent Node): 자식 노드를 가지는 노드입니다.
• 잎 노드 (Leaf Node): 자식 노드가 없는 노드입니다.
• 서브트리 (Subtree): 트리의 하위 구조로, 특정 노드를 루트로 하는 모든 자손 노드를 포함합니다.
• 높이 (Height): 트리의 높이는 루트 노드에서 가장 깊은 잎 노드까지의 거리입니다.

트리는 사이클이 없는 연결 그래프의 한 종류로, 트리 내의 모든 노드들은 오직 하나의 부모만을 가집니다.

그래프란 무엇인가?

그래프는 노드와 간선으로 이루어진 자료구조로, 복잡한 관계나 네트워크를 표현하는 데 유용합니다.

• 노드 (Node): 그래프의 정점을 의미합니다.
• 간선 (Edge): 두 노드를 연결하는 선입니다.
• 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프입니다.
• 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프입니다.
• 가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.
• 사이클 (Cycle): 노드를 통해 다시 자기 자신으로 돌아오는 경로가 있는 경우, 이를 사이클이라고 합니다.

트리와 달리 그래프는 사이클을 가질 수 있으며, 여러 노드 간의 관계를 자유롭게 나타낼 수 있습니다.

트리의 예제 (Java와 C)

트리를 구현하기 위해 가장 간단한 형태는 이진 트리입니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리입니다. 다음은 이진 트리의 기본적인 구조를 Java와 C로 구현한 예제입니다.

Java로 구현한 이진 트리

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    BinaryTree(int key) {
        root = new Node(key);
    }

    BinaryTree() {
        root = null;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("이진 트리가 생성되었습니다.");
    }
}

이 예제에서는 간단한 이진 트리를 생성하였습니다. 루트 노드를 생성하고, 자식 노드를 추가하여 트리를 구성합니다.

C로 구현한 이진 트리

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int key;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int key) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("이진 트리가 생성되었습니다.\n");
    return 0;
}

C 언어에서도 유사하게 구조체를 사용하여 이진 트리를 생성하였습니다. newNode 함수를 통해 새로운 노드를 생성하고, 루트 노드와 자식 노드를 연결합니다.

그래프의 예제 (Java와 C)

그래프를 구현하는 방법은 다양하지만, 인접 리스트(Adjacency List)를 사용하는 것이 일반적입니다. 다음은 간단한 그래프를 인접 리스트로 구현한 예제입니다.

Java로 구현한 그래프

import java.util.LinkedList;

class Graph {
    private int vertices;
    private LinkedList<Integer> adjList[];

    Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; ++i) {
            adjList[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    void printGraph() {
        for (int v = 0; v < vertices; v++) {
            System.out.print("정점 " + v + " 연결됨: ");
            for (Integer node : adjList[v]) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }

    public static void main(String args[]) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printGraph();
    }
}

이 예제에서는 정점과 간선을 추가하여 간단한 방향 그래프를 구성하고 출력합니다. 각 정점에 연결된 노드들이 출력됩니다.

C로 구현한 그래프

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int dest;
    struct Node* next;
};

struct AdjList {
    struct Node* head;
};

struct Graph {
    int vertices;
    struct AdjList* array;
};

struct Node* newNode(int dest) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->dest = dest;
    node->next = NULL;
    return node;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));

    for (int i = 0; i < vertices; ++i)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* node = newNode(dest);
    node->next = graph->array[src].head;
    graph->array[src].head = node;
}

void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->vertices; ++v) {
        struct Node* node = graph->array[v].head;
        printf("정점 %d 연결됨: ", v);
        while (node) {
            printf("%d ", node->dest);
            node = node->next;
        }
        printf("\n");
    }
}

int main() {
    struct Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

C로 구현된 그래프 예제에서는 인접 리스트를 사용하여 그래프를 구성하고, 각 정점과 연결된 노드를 출력합니다.

결론

트리와 그래프는 데이터 간의 관계를 표현하는 데 매우 중요한 자료구조입니다. 트리는 계층적이고 순차적인 관계를 표현하며, 그래프는 복잡하고 다양한 관계를 자유롭게 나타낼 수 있습니다. 위에서 Java와 C 언어로 트리와 그래프의 간단한 구현을 통해 기초 개념을 이해하고 직접 코딩해 보는 경험을 했습니다. 더 나아가 이러한 자료구조를 활용하여 다양한 문제를 해결하는 연습을 통해 실력을 향상시킬 수 있습니다.