Algorithm Study

그래프와 트리의 차이점

백준 16437 문제를 풀면서 그래프, 트리의 차이가 제대로 정리되어 있지 않다는 것을 알았다. 그래서 정리해보려고 한다. 그래프 2개 이상의 경로가 가능 노드들 사이에서 무방향/방향에서 양방향 경로를 가질 수 있다. 루트노드라는 개념이 없다. 부모-자식 관계라는 개념이 없다. 그래프의 순회는 DFS, BFS로 이루어진다. 그래프는 싸이클을 형성하거나 형성하지 않는다. 방향 그래프와 무방향 그래프로 나눠진다. 간선의 유무는 그래프에 따라 다르다. 트리 트리는 그래프의 특별한 케이스이고, "최소 연결 트리"라고도 한다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. 한 개의 루트 노드만이 존재하며, 모든 자식노드는 한 개의 부모노드만을 가진다. 트리의 순회는 전위순회, 중위순회, 후위 순회로 이루어..