Слайд 8Алгоритм ROCK
Procedurecluster (S, k)
Begin
1. link := compute-links (S)//Вычисляем связи в множестве точек
S
2. for each s from S do
3. q[s] := build-local-heap (link,S)//Из каждой точки множества S на основе связей формируем кластер
4. Q:=build-global-heap (S,q) //Содержит список всех кластеров множества S
5. whilesize (Q) >kdo {//Формируем кластеры, точки, которых имеют максимальное число связей до тех пор, пока не получим желаемое число кластеров
6. u := extract-max (Q)
7. v := max (q[u])
8. delete (Q,v)
9. w:= merge (u,v)
10. for each x from (q[u] or q[v]) do {
11. link [x,w] := link [x,u] + link [x,v]
12. delete (q[x],u); delete (q[x],v)
13. insert (q[x],w,g(x,w)); insert (q[w],x,g(x,w));
14. update (Q,x,q[x])
15. }
16. insert (Q,w,q[w])//Добавляем кластер в список всех кластеров
17. deallocate (q[u]); deallocate (q[v]);
18. }
end.