vector kruskalvector edgesint numvertices disjsets dsnumvertices }priority_queue pqedges }vector mstwhilemst size!numvertices edge pq pop)/edge (uvsettype uset ds finde getu)settype vset ds finde getv)ifuset !vset /accept the edge mst push_backe )ds unionusetvset )return mstfigure pseudocode for kruskal' algorithm actually (|elog | |in practicethe algorithm is much faster than this time bound would indicate applications of depth-first search depth-first search is generalization of preorder traversal starting at some vertexvwe process and then recursively traverse all vertices adjacent to if this process is performed on treethen all tree vertices are systematically visited in total of (| |timesince | (| |if we perform this process on an arbitrary graphwe need to be careful to avoid cycles to do thiswhen we visit vertexvwe mark it visitedsince now we have been thereand recursively call depth-first search on all adjacent vertices that are not already marked we implicitly assume that for undirected graphs every edge (vwappears twice in the adjacency listsonce as (vwand once as (wvthe procedure in figure performs depth-first search (and does absolutely nothing elseand is template for the general style for each vertexthe data member visited is initialized to false by recursively calling the procedures only on nodes that have not been visitedwe guarantee that we do not loop indefinitely if the graph is undirected and not connectedor directed and not strongly connectedthis strategy might fail to visit some nodes we then search for an unmarked node