Prim’s algorithm searches minimum spanning tree in a weighted undirected graph. In other words, it finds a sub-set of edges that forms a tree, where all vertices of a given graph are included and total weight of all edges is minimized.

Let’s consider the following example. You are an engineer and you’re going to build electrical grid to provide electricity to all houses bellow. The weight represents distance between two houses.

Of course, the houses can be connected in a random way and the problem will be solved. Continue reading Prim’s Algorithm →

Kruskal’s algorithm is used to find minimum spanning tree in a weighted undirected graph. A spanning tree of a undirected graph G is a sub-graph that includes all vertices of G and satisfies conditions of a tree. On the diagram below you can find two graphs and only left graph can be considered as spanning tree.

Because, the right graph has a cycle and this fact violates condition which states that a tree cannot have a cycle.  Continue reading Kruskal’s Algorithm →