Where can the source code of Prim Algorithm be found?

Answer 1

Algorithm's don't have source code per se. Source code depends on the programming language used to implement the algorithm and this will obviously vary from language to language. However, we often use pseudo-code to provide an informal language-agnostic implementation in human-readable form. Pseudo-code is not source code because it is not machine-readable and has no formal standard. However, it employs established structured programming conventions such as loops and variables, thus the code can be easily adapted to suit many high-level programming languages.

Prim's algorithm can be informally described as follows:

1. Initialise a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 until all vertices are in the tree.

In pseudo-code, the algorithm can be implemented as follows:

Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialise these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.

Initialise an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).

Repeat the following steps until Q is empty:

1. Find and remove a vertex v from Q having the minimum possible value of C[v]
2. Add v to F and, if E[v] is not the special flag value, also add E[v] to F
3. Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:

• Set C[w] to the cost of edge vw
• Set E[w] to point to edge vw

Return F

Source: wikipedia