Greedy Algorithms
"Greedy algorithms work in phases. In each phase, a decision is made that appears to be good, without regard for future consequences. Generally, this means that some local optimum is chosen. This 'take what you can get now' strategy is the source of the name for this class of algorithms. When the algorithm terminates, we hope that the local optimum is equal to the global optimum. If this is the case, then the algorithm is correct; otherwise, the algorithm has produced a suboptimal solution. If the best answer is not required, then simple greedy algorithms are sometimes used to generate approximate answers, rather than using the more complicated algorithms generally required to generate an exact answer."
- Data structures and algorithm analysis in C
- Mark Allen Weiss
Minimum Spanning Trees
Given a connected, undirected graph
G = <N,E>
where each edge has an associated 'length' (or 'weight').
For example :
We want a subset, T, of edges, E, such that the graph remains connected if only the edges in T are used, and the sum of the lengths of edges in T is as small as possible.
Such a subgraph must be a tree, and is called a Minimum Spanning Tree.
For the above graph, the following are both minimum spanning trees (cost 7).
PROBLEM : Devise an algorithm to find a minimum spanning tree.
Kruskal's Algorithm
Greedy algorithm to find minimum spanning tree.
Want to find set of edges T.
- Keep track of connected components of graph with edges T
- Initially components are single nodes
- At each stage, add the cheapest edge that connects two nodes not already connected
To see the minimum spanning tree calculated using Kruskal's algorithm for the above graph, press the Example button below, or you can draw your own graphs by pressing the New Graph button :
E-mail : graham@cs.man.ac.uk