Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
- Навигация на страницата:
- Алгоритъм на Крускал (Kruskal)
- DisjSet s(NUM_VERTICES); PriorityQueue h(NUM_EDGES); Vertex u,v;
Алгоритъм на Крускал (Kruskal)Стратегията тук е да се избере ребро с най-малко тегло и да се одобри, ако не форми-ра цикъл. За графа от предходния пример действията са показани на фиг. 36. При това се попълва таблица, в която за всяко ребро се записва неговото тегло и флаг, който показва дали върха е отхвърлен или не. Табл. за графа от предходния пример е показана на фиг. 37.
Погледнато формално алг. на Крускал работи с множество дървета. В нач. това са │V│ броя дървета, състоящи се от по един връх. Добавяйки ребро,сливаме 2 дървета в едно. Алг.приключва когато са включени необх.брой ребра. При това е налице само едно дърво и то е търсеното. При добавяне-то на ребро се използва следното правило: ако v и w са два върха в едно дърво, ребро-то, което ги свързва, не се избира за разгле-ждане,защото формира цикъл.В противен случай реброто се включва и двете дървета (включващи v и w) се сливат. Вижда се, че множествата са инвариантни (върховете в тях стоят постоянно) и към тях само мд се добавят нови чрез сливане на дървета. Реб-рата могат да се сортират за ускоряване на търсенето, но изграждането на heap е по-добра идея за ускоряване. Void Graph::kruskal() { int edgeAccepted; DisjSet s(NUM_VERTICES); PriorityQueue h(NUM_EDGES); Vertex u,v;SetType uset, vset; Edge e; h = readGraphIntoHeapArray(); h.buildHeap(); edgeAccepted=0;while (edgeAccepted { h.deleteMin(e); uset = s.find(u); vset = s.find(v); if (uset!=vset){ edgesAccepted++; s.unionSets(uset,vset); }} }Оценката на алг. е O(│E│log│Е│) в най-лошия случай, което се определя от heap операциите. Отбележете, че тъй като │E│ = O(│V│2), то времето за изпълнение ще бъде O(│E│log│V Изтегляне 1.47 Mb. Сподели с приятели:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||