 # 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 :

Undirected Graph Applet Appears Here

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).

Example Minimum Spanning Tree Applet

Example Minimum Spanning Tree Applet

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.
• Start with T = EMPTY SET
• 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 :

INSERT APPLET HERE E-mail : graham@cs.man.ac.uk