Given a connected and undirected graph, a spanning tree of that graph is a sub-graph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.
A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.
There are lots of applications of MST, while the most well-known is network design: telephone, electrical, hydraulic, TV cable, computer, road
The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn’t a tree you can always remove some edges and save money.
Like Kruskal’s algorithm, Prim’s algorithm is also a Greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges.
Below are the steps for finding MST using Kruskal’s algorithm
- Sort all the edges in non-decreasing order of their weight.
- Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
- Repeat step#2 until there are (V-1) edges in the spanning tree.
void qsort (void base, size_t num, size_t size, int (compar)(const void,const void));
base: Pointer to the first object of the array to be sorted, converted to a void*.
num: Number of elements in the array pointed to by base. size_t is an unsigned integral type.
size: Size in bytes of each element in the array. size_t is an unsigned integral type.
compar: Pointer to a function that compares two elements. This function is called repeatedly by qsort to compare two elements. It shall follow the following prototype:
int compar (const void p1, const void p2);
Taking two pointers as arguments (both converted to const void*). The function defines the order of the elements by returning (in a stable and transitive manner):
return value meaning
<0 0="" the="" element="" pointed="" to="" by="" p1="" goes="" before="" p2="" is="" equivalent="" \="">0 The element pointed to by p1 goes after the element pointed to by p20>
void bsearch (const void key, const void base, size_t num, size_t size, int (compar)(const void,const void));
Searches the given key in the array pointed to by base (which is formed by num elements, each of size bytes), and returns a void pointer to a matching element, if found. The rule of the compar is quite the same as qsort*.
Note the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater.
Always welcome new ideas and
practical tricks, just leave them in the comments!