The goal of this whole lesson is to present two greedy algorithms for the minimum spanning tree problem. Before going in to the details of this algorithms, let me present you the higher level ideas of both these algorithms. So the first one is the Kruskal And the second one is you need to Prim. The high level idea of the algorithm by Kruskal is the following. So, we go through all edges in order of increasing width, and we repeatedly at the next lightest edge which doesn't produce a cycle. Alternatively, the main idea of the Prim's algorithm is to grow a tree repeatedly so initially it contains just one vertex, then we attach a new vertex to it, then a new vertex to it. And we always attach the new vertex to the current tree by the lightest available edge. Let me illustrate this again on a toy example. So for Kruskal's algorithm, again, we repeatedly add the next lightest edge that doesn't produce a cycle. Initially, our solution is empty, so we just add the first lightest edge. In this case, the lightest edge has weight 1, so we just put this edge into our solution. And there is also another edge which has cost or weight 1, so we also add it to our solution. The next one has weight 2. We add it. At the same time, the next one, the next lightest available edge has weight 3. However, if we added it to our current solution, this would produce a cycle. So we skip this edge. The next lightest available edge has weight 4. We add it because it doesn't produce a cycle. Then, again, we try to add the edge with weight 5 because it is the next lightest available edge. However, it produces a cycle. So we skip this edge, and instead we add the edge of weight 6, right? This gives us a solution, and we will soon justify that this method indeed gives an optimal solution. Now, to the Prim's algorithm. It works in a different way. So it repeatedly grows just 1, 3. For this, it will select a root for this tree. So I assume that this highlighted vertex is going to be the root of the tree that we are going to construct. At each iteration we are going to attach a new node to this tree, and we would like to do this by using the lightest possible edge. So for this vertex, we have four edges going out of this node. One of weight 4, one of weight 5, of weight 6, and of weight 8. In this case, we select, of course, the edge of weight 4. So we attach it. Now our tree contains two nodes, and we would like to attach a new node to this tree by lightest edge. So in this case, this is the vertex in the middle. And it has weight, the corresponding edge, has weight 1 so we attach it. The next one has weight 2. The next one has weight 6. And finally, the last node is attached by an edge of weight 1, right? So, in the next part of this lesson, we will present the implementation details of both these algorithms, but we first will prove that both these algorithms are correct. Namely, that they produce an optimal solution.