Greedy Algorithm
Concept
Making the locally optimal choice at each stage, but may not be the optimal choice for the global solution.
If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimization methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.
In greedy alogorithm questions, it usually does not encounter SAME previous subproblems, which are what DP questions have.
Minimum spanning trees (MST)
1.Finding minimum spanning FOREST in a DISCONNECTED graph : includes every vertex, where the sum of the weights of all the edges in the tree is minimized.
2.Finding minimum spanning TREE in a CONNECTED graph : composed of a minimum spanning tree for each connected component.
Kruskal's algorithm (add edges)
Approach: disjoint-set (Union-find)
Prim's algorithm (add vertex)
Different from Dijkstra's algo : no need to acuumulate values for each node, only need to find local optimal edge.
Approach: BFS
Time complexity:
1.Binary heap(priority queue)=> O(ElogV), where E is the number of total edges and V is the number of vertex.
2.Fibonacci heap => O(VlogV + E).
![](images/prim's.png)
(The above image is from ASU SER501.)
Graph search and finding a shortest path
Dijkstra's algorithm
1.Using BFS to traverse each vertex.
2.Should be a connected, all positive weights graph. Algorithm applies to both directed and undirected graph.
3.If there exists a negative weight of edges, it will cause cycle and can't find a shortest path.
4.A key technique in shortest path algorithms is relaxation.
![](images/relaxation.png)
(The above image is from ASU SER501.)
5.May not result in a MST.
Approach: BFS
Time complexity:
1.Binary heap(priority queue) => O(ElogV), where E is the total number of edges and V is the total number of vertex. Look here for explaination
2.Fibonacci heap => O(VlogV + E).
Space complexity: O(V)
![](images/Dijkstra’s.png)
(The above image is from ASU SER501.)
Decision tree
Not garantee to find an optimal solution
Huffman tree
Travelling salesman problem
[Medium] No.763 Partition Labels
Approach: Greedy
Time Complexity: O(N), where N is the length of input string.
Space Complexity: O(1), keep data structure last of not more than 26 characters.
[Medium] No.678 Valid Parenthesis String
Approach: Greedy
Time Complexity: O(N), where N is the length of input string.
Space Complexity: O(1)