Notes
  • About this notes
  • Algorithms
    • Sorting
    • Complexity
    • Recurrence
    • Divide-and-Conquer
    • Heapsort
    • Graph Algorithms
    • Greedy Method
Powered by GitBook
On this page
  • Minimum Spanning Tree
  • Brute-force method:
  • Greedy method:
  1. Algorithms

Greedy Method

PreviousGraph Algorithms

Last updated 6 years ago

  • 在一連串的選擇中做 local optimal decision 會在最終產生 global optimal solution

  • 只有少數 optimization problem 可以使用 Greedy

  • 但大部分問題仍可以用 Greedy 找到近似解 (acceptable solution)

Minimum Spanning Tree

A minimum spanning tree of G is a spanning tree of G with the smallest total weight.

  • 假設 G=(V,E), ∣V∣=n, ∣E∣=mG=(V,E),\ |V|=n,\ |E|=mG=(V,E), ∣V∣=n, ∣E∣=m

  • 邊數： ∣E′∣=∣V∣−1|E'|=|V|-1∣E′∣=∣V∣−1

  • 滿足 spanning tree (點之間連通 connected)

Brute-force method:

  • nn−2n^{n-2} nn−2 possible spanning trees for nnn points

  • Exponential time complexity

Greedy method:

  • Kruskal’s algorithm: O(m log m)O(m\ log\ m)O(m log m)

  • Prim’s algorithm: O(n2)O(n^2)O(n2)