edges in that are not in and we end up with the minimal spanning tree xn which completes the proof that is minimal spanning tree the time complexity of the standard prim' algorithm is ( because at each step we need to choose vertex to add to sand then update the closest arraynot dissimilar to the simplest form of dijkstra' algorithm howeveras with dijkstra' algorithma binary or binomial heap based priority queue can be used to speed things up by keeping track of which is the minimal weight vertex to be added next with an adjacency list representationthis can bring the complexity down to (( )log nfinallyusing the more sophisticated fibonacci heap for the priority queue can improve this further to ( nlog nthususing the optimal approach in each caseprim' algorithm is (nlog nfor sparse graphs that have ( )and ( for highly connected graphs that have ( just as with floyd' versus dijkstra' algorithmwe should consider whether it eally is necessary to process every vertex at each stagebecause it could be sufficient to only check actually existing edges we therefore now consider an alternative edge-based strategykruskal' algorithm greedy edge-based approach this algorithm does not consider the vertices directly at allbut builds minimal spanning tree by considering and adding edges as followsassume that we already have collection of edges thenfrom all the edges not yet in choose one with minimal weight such that its addition to does not produce circleand add that to if we start with being the empty setand continue until no more edges can be addeda minimal spanning tree will be produced this approach is known as kruskal' algorithm for the same graph as used for prim' algorithmthis algorithm proceeds as followsa in practicekruskal' algorithm is implemented in rather different way to prim' algorithm the general idea of the most efficient approaches is to start by sorting the edges according to their weightsand then simply go through that list of edges in order of increasing weightand either add them to or reject them if they would produce circle there are implementations of that which can be achieved with overall time complexity (elog )which is dominated by the (elog ecomplexity of sorting the edges in the first place this means that the choice between prim' algorithm and kruskal' algorithm depends on the connectivity of the particular graph under consideration if the graph is sparsei the