1197번을 풀다가 최소 스패닝 트리는 무방향 그래프라는 것을 알았다.
그런데 트리는 유방향 그래프 아닌가? 그래프와 트리에 대해 헷갈려서 정리한다.
그래프
그래프는 정점과 정점 사이를 잇는 간선으로 이루어져있다.
유방향 그래프와 무방향 그래프로 나뉜다. 유방향 그래프는 간선으로 이어진 두 정점 중 시작 정점만 인접정점으로 도착 정점을 가지고 있고 무방향 그래프는 시작정점 도착정점 둘 다 서로를 인접정점으로 가지고 있으니 꽤 큰 차이다.
트리
트리는 그래프의 일종이다. 그리고 순환(사이클)을 허용하지 않는다.
부모 - 자식 관계가 존재하며, 루트 노드가 존재한다. 그런데 여기서 헷갈렸던게 한글로 검색하면 대부분
트리에 대해서 방향 그래프만 존재한다고 나와있다. 하지만 최소 스패닝 트리는 무방향 그래프였다.
https://en.m.wikipedia.org/wiki/Tree_(graph_theory)
Tree (graph theory) - Wikipedia
Labeled treesEdit Cayley's formula states that there are nn−2 trees on n labeled vertices. A classic proof uses Prüfer sequences, which naturally show a stronger result: the number of trees with vertices 1, 2, …, n of degrees d1, d2, …, dn respectiv
en.m.wikipedia.org
영문 위키백과를 보면 그래프 이론에서 트리를 무방향 그래프라고 보고 있고 방향을 가진 트리도 존재한다고 써져 있다.
그리고 백준에 질문했더니 "루트와 부모-자식 관계가 중요한 경우 방향 그래프로 보는 것이 옳지만, 상황에 따라서는 무방향 그래프로 보는 것이 맞는 경우도 있습니다." 라는 답변을 받았다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] 벨만 포드 알고리즘 (0) | 2023.02.20 |
|---|---|
| [알고리즘] BFS, DFS 언제 사용할까? (0) | 2023.02.13 |
| [알고리즘] 최소 스패닝 트리 - 프림(Prim) 알고리즘 (0) | 2023.02.08 |
| [알고리즘] 플로이드 와샬 알고리즘 (0) | 2023.02.07 |
| [알고리즘] 약수의 개수 구하기 (0) | 2023.01.11 |