14. 트리와 그래프

트리와 그래프

컴퓨터 과학에서 여러 방면으로 널리 쓰이는 자료구조에는 트리와 그래프가 있다.

우선 트리와 그래프가 무엇인지부터 알아보면 트리는 그래프의 한 종류이다
그렇기에 그래프에 대한 설명을 먼저 하면

그래프

우선 그래프는 정점(node)들 사이의 관계를 간선(edge)으로 표현하는 구조이다.

컴퓨터 네트워크, 도로 및 지도에서의 최단 경로 탐색(Dijkstra, BFS), 의존성 그래프(빌드 시스템)
상태 전이 모델, 전자회로, 추천 시스템 등 많은 현실의 문제의 대부분을 그래프로 모델링할 수 있다.
그렇기에 그래프는 다양한 분야에서 문제를 추상화하고 효율적으로 해결하기 위한 자료 구조로 사용된다.

정점은 말 그대로 하나의 점이고, 간선은 방향이 있을 수도 있고, 양쪽을 연결할 수도 있다.
노드 간에는 2개 이상의 경로가 있을 수도 있고, cycle(순환)구조를 가질 수도 있고 없을 수도 있다.

그러면 노드와 간선은 코드로 어떻게 표현할 수 있을까?

크게 인접 리스트와 인전 행렬이 있는데 메모리 측면에서 장점이 있는 인접 리스트로 주로 사용하게 된다.

인접 행렬은 n개의 정점이 있을 때

vector<vector<int>> graph(n, vector<int>(n));
cin >> a >> b;
graph[a][b]=1; // 양방향
graph[b][a]=1;

2차원 graph를 통해서 모든 정점들의 관계를 표현한다.
2차원 배열에서 체크가 되어있으면 연결이 된 것이고, 아니라면 간선이 없는 것이다.
모든 node 간의 관계를 알 수 있지만 메모리를 n^2만큼 가지기 때문에 너무 큰 메모리를 잡게 될 수도 있다.

그래서 인접 리스트 방법은 해당 정점에 대해 이어져 있는 node만 저장한다.

vector<vector<int>> graph(n);
cin >> a >> b; // 양방향
graph[a].push_back(b);
graph[b].push_back(a);

를 통해서 a에 연결된 node와 b에 연결된 정점만 저장할 수 있다.

빠르게 정점들간의 연결 관계를 확인해야 할 때는 hashmap을 통해서

vector<map<int, int>> graph(n);
cin >> a >> b;
graph[a][b]=1;
graph[b][a]=1;

처럼 구현하기도 한다.

그래프의 종류로는

• 간선에 방향이 없는 무향 그래프 ex) 친구 관계, 연결 관계
• 방향이 있는 유향 그래프 ex) 호출 관계, 웹 링크
• 가중치 그래프 ex) 최단 경로, 최소 비용
• DAG라는 사이클이 없는 유향 그래프
• 트리라는 사이클이 없는 무향 그래프
• 이분 그래프라는 정점을 두 그룹으로 나누고, 간선은 서로 다른 그룹 사이에만 존재

등이 있다.
이들은 고유한 성질들이 또 있고, 이를 활용해서 문제를 푸는데 이용할 수 있다.

트리

트리는 위에서 봤듯 그래프의 한 종류로 사이클이 없는 무향 그래프이다.
또, 모든 정점에서 서로 도달이 가능한 연결 그래프이다.

그렇기에 정점 수가 N이면 간선 수는 항상 N−1개를 가지게 된다.

이 성질 때문에 트리에서는 임의의 두 정점 사이의 경로가 항상 정확히 하나만 존재한다.
이 유일한 경로에 의해서 트리는 계층 구조를 표현하기에 매우 편하다.

트리의 용어

트리를 쓸 때는 보통 한 정점을 기준으로 잡고 루트(root)를 가진 트리로 본다.

• 루트(root): 트리의 시작이 되는 정점.
• 부모(parent) / 자식(child): 루트 방향이 부모, 아래가 자식.
• 형제(sibling): 같은 부모를 가지는 정점들.
• 리프(leaf): 자식이 없는 정점.
• 서브트리(subtree): 어떤 정점을 루트로 하는 하위 트리.
• 깊이(depth): 루트에서부터 내려온 칸 수.
• 높이(height): 트리에서 가장 깊은 리프의 깊이.

이런 용어들이 DFS/BFS, DP, 세그먼트 트리, 트라이 같은 모든 트리 알고리즘 설명의 기본 단위가 된다.

트리를 특별하게 다루는 이유는 실제 문제에서 응용하기 좋기 때문이다.

트리는 계층적인 관계를 표현하는 데 적합한 구조로, 운영체제의 디렉터리 구조
데이터베이스 인덱스(B-트리, B+트리), HTML/XML DOM, 컴파일러의 파스 트리 등에서 사용된다.

특히 탐색, 정렬, 범위 질의 등에 효율적인 이진 탐색 트리(BST), 균형 트리(AVL, Red-Black Tree),
힙(Heap) 등은 알고리즘 관련 내용에서 빠질 수 없이 활용되는 내용이다.

---

이렇게 간단하게 트리와 그래프의 내용에 대해 정리했고, 그래프에서 차수 수열에 따른 성질에 대해 정리하려고 한다.
백준에서 차수열 태그가 붙어있는 문제들을 전부 풀어봤는데 상당히 재미가 있었다.