힙9 다익스트라 알고리즘 다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요하겠지만, 일단은 간단하게 구성해보았습니다. (참조 : http://sdev.tistory.com/72 , http://sdev.tistory.com/71) 이 소스는 애시당초 프림 알고리즘 소스를 만들었던 것을 고친지라, 코멘트가 프림에 맞추어져 있습니다. // Dijkstra.cpp : Defines the entry point for the console application. // #include "stdafx.h" #defineNIL(0) ///인접리스트를 위한 구조체 선언 struct vlist { int vert.. 2014. 10. 18. 자료구조의 보석 힙(Heap) 2010-02-19 19:27:20 오늘은 자료 구조의 보석인 힙(Heap)을 찾아서 가기로 해요.. 태고의 도시 야율론에 힙이라는 보물이 숨겨져 있다는 보물지도를 얻은 이비는 친구인 리시타와 피오나와 함께 야율론으로 떠나는 배를 탑니다. 이 보물지도는 고대 문자인 에리스문으로 되어 있는데, 이것을 해석하는 것은 아주 어렵다고 합니다. 특히 다중상속문이 존재하는 이 언어는, 고도의 지식을 요합니다. 더구나 템플릿을 이용하기도 하는데, 이 템플릿은 스택, 큐, 동적 배열을 한단어로 표현할 수 있을 정도로 강력한 마법 언어로 알려져 왔습니다. 다행히 이 보물지도에 있는 에리스문은 상속도 없고 템플릿도 없습니다. 리시타와 피오나 모두 준비가 되었다고 하는군요. 선장인 이비가 출발을 외칩니다..~ 뿌웅..~~~.. 2011. 9. 27. Prim algorithm with heap Prim algorithm with heap 제가 좋아하는 자료구조는 힙(Heap)이라는 것입니다. 힙은 이진트리 중에 특별한 형태를 사용하고 있습니다. 꽉 찬 이진트리를 사용함으로써 배열을 그대로 이진트리로 사용할 수 있습니다. 이중에서 최소힙과 최대힙이 있는데, 루트의 값이 가장 작은 경우를 최소힙, 가장 큰 경우를 최대힙으로 이해하면 됩니다. 힙의 조건은 다음과 같습니다. 힙의 제일 아래층을 제외하고 꽉 차있고, 제일 아래층은 왼쪽부터 꽉 차있다. 힙의 모든 노드는 하나의 값을 가지고 있다. 각 노드의 값은 자식의 값보다 항상 작다. (최소힙) 최대힙의 경우에는 3)항만 다릅니다. 꽉 찬 이진트리이기 때문에 배열로 바로 구현할 수 있습니다. 그렇지 않다면 자식들의 링크를 보관해야 하죠. 다음의 힙을.. 2011. 9. 27. 이전 1 2 다음 728x90
