貪心算法是一段一段地提供解決方案，總是選擇下一段提供最明顯和最直接的利益。所以問題是選擇當時的局部最優解。在這種情況下，決策是在當前可用信息的基礎上做出的，而不考慮當前決策對未來的影響。在貪心算法中，我們在每個狀態下都決定我們要選擇什麼，以使它成為最優。貪心算法有其優點。

• 貪心算法是相當容易解決的問題。
• 分析貪婪算法的運行時間通常比分析其他技術(如分治法)容易得多。因為分治中子問題的規模每次都在增加。
• 的例子。
• 使用Dijkstra算法尋找兩個頂點之間的最短路徑。
• 使用Prim /Kruskal算法在圖中尋找最小生成樹，等等。

Prim最小生成樹:

在Prim的最小生成樹中，生成樹意味著所有的頂點必須是連通的。所以，這兩個不相交的頂點子集必須連接起來，形成a跨越樹。它們必須與最小權值邊相連才能成為a最低生成樹。

算法
1）創建一個集合集用於跟蹤已經包含在MST(最小生成樹)中的頂點。
2）給圖中的所有頂點賦一個鍵值。將所有鍵值初始化為INFINITE。將第一個頂點的鍵值賦為0，這樣它就可以第一個被選中。
3）而Set不包括所有頂點

1. 一)選擇一個頂點u哪個不在裏麵集並且鍵值最小。
   b)包括u設置。
2. c)的所有相鄰頂點的鍵值更新u．要更新鍵值，請遍曆所有相鄰頂點。對於每個相鄰頂點v，如果邊的權值uv的前一個鍵值小於v，將鍵值更新為的權重uv。
   鍵值僅用於尚未包含在MST中的頂點，這些頂點的鍵值表示將它們連接到包含在MST中的頂點集的最小權值邊。