الگوریتم کراسکال

[آبجی]

در الگوریتم کراسکال یال‌های گراف را به ترتیب صعودی مرتب می کنیم. از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
‎

1 function Kruskal(G)
2 for each vertex v in G do
3 Define an elementary cluster C(v) ← {v}.
4 Initialize a priority queue Q to contain all edges in G, using the weights as keys.
5 Define a tree T ← Ø //T will ultimately contain the edges of the MST
6 // n is total number of vertices
7 while T has fewer than n-1 edges do
8 // edge u,v is the minimum weighted route from/to v
9 (u,v) ← Q.removeMin()
10 // prevent cycles in T. add u,v only if T does not already contain a path between u and v.
11 // Note that the cluster contains more than one vertex only if an edge containing a pair of
12 // the vertices has been added to the tree.
13 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14 if C(v) ≠ C(u) then
15 Add edge (v,u) to T.
16 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
17 return tree T
نحوهٔ کار الگوریتم کراسکال به این صورت است که یک جنگل از درخت هارا به ترتیب با هم ادغام می‌کند تا به یک درخت واحد برسد.