چرا الگوریتم( prime=o(n2 است؟

روش ذخیره گراف در ماتریس به تعداد سطرها ستون داریم.اگر یال مستقیمی باشد وزن

یال را درآن قرار می دهیم روش اثبات را توضیح دهید.

 

 

الگوریتم kruskal را بصورت شبه بنویسید.


جواب :

Kruskal Pseudo Code
void Graph::kruskal(){
int edgesAccepted = 0;
DisjSet s(NUM_VERTICES);
while (edgesAccepted < NUM_VERTICES – 1){
e = smallest weight edge not deleted yet;
// edge e = (u, v)
uset = s.find(u);
vset = s.find(v);
if (uset != vset){
edgesAccepted++;
s.unionSets(uset, vset);
}
}
}