---
title: Prime演算法
tags: 演算法
description: 簡述使用Prime演算法來求得最小生成樹
---
# Prime演算法

Prime是一種以中心拓展的生成樹求法，在建立生成樹的途中，將整棵建構中的樹作為一個系統，以最小成本進行延展。

## 作法

與Kruskal不同的是，Prime需要有起點，而Kruskal不需要。

實際上的步驟如下

1. 隨便挑一個點，建議以字典序或鄰邊成本小為優先
2. 以這個點為基準，挑一個成本最小的相鄰邊延展，此時生成樹會有一個邊、兩個點
3. 以整個生成樹為基準，以目前來說是兩個點，找出成本最小的鄰邊，繼續延展，若出現環則跳過換成本次低的邊進行拓展
4. 以此類推重複步驟2-3，直到無法繼續選邊延展

## 程式範例

## 練習

## reference

> [link text](https:// "title")
> [name=Miyago]