Greedy algorithms tutorial

Problem Detail: 

Could anyone point me to simple tutorial on greedy algorithm for Minimum Spanning tree - Kruskal's and Prims' Method

I am looking for a tutorial which

• does not include all the mathematical notation
• explains algorithm along with the analysis of the running time.

Asked By : Sid

Answered By : Anton

Here is a simple definition for greedy algorithm.

There are many greedy algorithms for different problems and in order to understand them you must also know well the subject of the problem. This question on stackoverflow gives some examples of greedy algorithms usage.

EDIT : After you made your question more clear I will try to sketch the algorithms by using "minimum mathematical notation". Both the Kruskal's and Prim's algorithms build MST in connected graph.

Let we have graph G with vertices V and edges E.

Prim's algorithm

1. Select some vertex r from V and add it to the tree. r will be the root of the tree

2. Until all vertexes V are in the tree :

   Find the shortest edge from E that has one end in the already constructed tree and the other in some of the vertices of the graph that are not in the tree and add the edge and the new vertex to the tree

3. When the condition in step 2. is not correct you will have the MST constructed

Kruskal's algorithm

1. Construct forest of trees where each tree is a single vertex from V

2. Until all trees are connected into single one :

   Find the shortest edge from E that connects two unconnected trees and connect them with it. That step constructs from two trees a new one.

3. When the condition in step 2. is not correct all the trees will be connected into single one that is the MST

Note: After each iteration we have a tree/trees because there is no way to add a edge that forms a cycle

Note: The tree consists of vertexes and edges (it is kind of graph). When adding a vertex to the tree we add it to the set of vertices and when adding edge - to the set of edges.

Running Time

This part really needs mathematical notation and depends on specifics in the implementation of the algorithms, so I will leave it only with some answers and links to Wikipedia,where there are some general explanations.

Prim's Algorithm = O(E.log E) = O(E. log V)

Kruskal's Algorithm = O(E.log E) = O(E. log V)

Please read the explanations and ask only the things that are unclear to you(maybe in different question if they are related to the asymptotic notations)

"Greedy Part"

The greedy part in both of the algorithms is choosing to add the shortest edge to the tree. The shortest edge is the logically optimal choice when constructing Minimal Spanning Trees.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6634