건빵의 블로그

우선 Spanning tree의 정의에 대해서 되돌아볼 필요가 있다. 스패닝 트리는 어떠한 그래프의 서브그래프이면서 그래프의 모든 버텍스를 포함하는 트리이다. 그러한 그래프가 edge에 weight를 가질때, weight의 합을 최소화하는 스패닝 트리를 Minimum spanning tree라 하며 그것을 구하는 알고리즘으로 Prim's algorithm과 Kruskal's algorithm이 있다. 위 두가지 방법은 Greedy Approach를 이용하여서 각자의 기준을 가지고 스패닝 트리를 만들게 된다. 우선 첫째로, Prim의 알고리즘은 하나의 버텍스에서 시작하여 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연결된 버텍스를 선택하고 연결한다. 여기에서 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연..

오늘은 저녁에 놀아야 되니까, 좀 일찍 정리해보자 ㅋ Trees 트리는 Graph부분에서도 나왔지만 자료구조에서도 매우 중요하게 다뤄지는 중요한 개념이라 그런지 따로 언급된다. Graph부분에서는 트리는 acyclic connected graph라고 하였다. 또 다른 정의로써, tree는 모든 vertices의 쌍 사이에 유일한 path가 존재하는 ugraph이다. 또한 rooted tree는 지정된 root vertex를 가지고 모든 edge가 root로부터 directed away(?) 되는 트리이다. directed away는 정확한 해석은 모르겠지만 루트로의 길의 일부분이 된다? 정도로 받아들이면 될 것 같다. 이 부분에서 헷갈려야 하지 말아야 하는 것이 rooted tree와 tree이다. 우리..