Algorithms and Data Structures for Programming Contests

Greedy Algorithms (Cont'd)

Regroup

High-level solution

1. Translate input into a graph representation.
   Careful! We want a graph where each pen is a "node", the outside is also one "node", and there are "edges" between any two pens that share an edge.
2. Pick edges with smallest cost, until every pen is connected — skip edges between pens that are already connected.

Minimum Spanning Trees

Definition

• Given graph with edge costs (see example graph below), find subset of edges that connects all vertices and whose total cost is minimum.

Kruskal's algorithm

1. Initialization:
   1. Sort the edges by non-decreasing cost.
   2. Initialize an empty tree (subset of edges).
2. Repeat n−1 times (where n is the number of vertices):
   1. Select an edge with smallest cost whose endpoints are not already connected, and add it to the partial tree.

Prim's algorithm

1. Initialization:
   1. Pick a start vertex s. The entire graph is partitioned into two sides: vertices connected to s, and the rest.
   2. Initialize an empty tree (subset of edges).
2. Repeat n−1 times:
   1. Select a minimum-cost edge between some vertex connected to s and some unconnected vertex, and add it to the tree.

Runtime

• O(n m), where m is the number of edges in the graph.
• Can be improved to O(n log n) through the use of appropriate data structures.

Argument of correctness

• Why do we need this? Think about making change problem, or minimum-cost path problem for graph above, starting at node a...
• Hinges on property that the choice made by greedy at each step is guaranteed to lead to an optimal solution.
• Formally, argued through an "exchange argument".

To learn more...

• Wikipedia entry on Greedy algorithms.

Back to Algorithms

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.