prim's algorithm

a greedy algorithm to find an mst in a given undirected weighted graph.

a basic implementation (better complexity can be achieved with a better implementation, proposed later in this note):
$\text{[math]}$

at each step of prim's algorithm the graph $\text{[math]}$ is a tree

it follows trivially from the code.

$\text{[math]}$ is also a subgraph of an mst of $\text{[math]}$

proof by induction on the number of iterations in the loop
base step: immediately after initialization, $\text{[math]}$ , at this point, the graph $\text{[math]}$ contains a single arbitrary vertex of $\text{[math]}$ and contains no edges, each mst of $\text{[math]}$ contains all vertices in $\text{[math]}$ , so the claim is correct in this case.
induction hypothesis: assume that after the addition of $\text{[math]}$ vertices to $\text{[math]}$ and $\text{[math]}$ edges to $\text{[math]}$ , the tree $\text{[math]}$ is a subgraph of an mst of $\text{[math]}$ which we shall call $\text{[math]}$ . let $\text{[math]}$ be the minimum edge in $\text{[math]}$ that the algorithm adds to $\text{[math]}$ such that $\text{[math]}$ .
case 1: $\text{[math]}$ , the algorithm "picked" $\text{[math]}$ as the mst, the claim's correctness follows trivially.
case 2: $\text{[math]}$ , the algorithm "picked" another mst of $\text{[math]}$ , in this case we need to show that there is another mst of $\text{[math]}$ , which we call $\text{[math]}$ , such that $\text{[math]}$ . $\text{[math]}$ is an mst of $\text{[math]}$ , which means that $\text{[math]}$ contains a path $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ . and since $\text{[math]}$ , we know the path $\text{[math]}$ crosses from $\text{[math]}$ to $\text{[math]}$ , which means that $\text{[math]}$ must contain an edge $\text{[math]}$ such that $\text{[math]}$ .
let $\text{[math]}$ be the graph whose set of edges $\text{[math]}$ is received by removing $\text{[math]}$ from $\text{[math]}$ and adding $\text{[math]}$ , i.e. $\text{[math]}$ . according to spanning tree lemma 1, $\text{[math]}$ is a spanning tree of $\text{[math]}$ . we can see that trading $\text{[math]}$ for $\text{[math]}$ results in a different mst of $\text{[math]}$ . at the moment $\text{[math]}$ is added to $\text{[math]}$ , the edges $\text{[math]}$ and $\text{[math]}$ are both in $\text{[math]}$ and the algorithm chose $\text{[math]}$ before $\text{[math]}$ which means $\text{[math]}$ which means $\text{[math]}$ , but on the other side, $\text{[math]}$ is an mst of $\text{[math]}$ and so $\text{[math]}$ . and so $\text{[math]}$ , and $\text{[math]}$ , i.e. $\text{[math]}$ is another mst of $\text{[math]}$ . during the $\text{[math]}$ -th iteration of the loop, the algorithm "chooses" between $\text{[math]}$ and $\text{[math]}$ , and $\text{[math]}$ and $\text{[math]}$ .

prim's algorithm computes an mst of the input graph.

according to lem-prim-1, at the end of each iteration in the loop, $\text{[math]}$ is included in the mst of the input graph, at the end of the $\text{[math]}$ -th iteration, $\text{[math]}$ would contain $\text{[math]}$ vertices which means its an mst of $\text{[math]}$ .

improvements in the algorithm:
given that $\text{[math]}$ is the cut set, the time complexity for finding the minimal edge would be $\text{[math]}$ and since $\text{[math]}$ contains duplicate edges, consider the edges $\text{[math]}$ , the time complexity can be $\text{[math]}$ , we reduce this by defining $\text{[math]}$ such that $\text{[math]}$ is the minimal edge that connects $\text{[math]}$ to a vertex in $\text{[math]}$ , if there isnt such a vertex then $\text{[math]}$ , the minimum edge in $\text{[math]}$ would be included in $\text{[math]}$ , and $\text{[math]}$ . we propose a more efficient version of the algorithm that uses this idea to achieve $\text{[math]}$ complexity:
$\text{[math]}$

the time complexity of this algorithm is $\text{[math]}$