如下找出該圖的最小生成樹
prim算法是求解該類問題的一種經典算法
Prim算法的基本思路：
将圖中的所有的頂點分為兩類：樹頂點（已經被選入生成樹的頂點）和非樹頂點（還未被選入生成樹的頂點）。首先選擇任意一個頂點加入生成樹，接下來要找出一條邊添加到生成樹，
這需要枚舉每一個樹頂點到每一個非樹頂點所有的邊，然後找到最短邊加入到生成樹。依次，重複操作n-1次，直到将所有頂點都加入生成樹中。
算法實作如下
1 #include<bits/stdc++.h>
2 using namespace std;
3 void Prim(int n,int c[ ][100])
4 {
5 int lowcost[100];//各非樹頂點到樹頂點集的最短路徑
6 int closet[100];//非樹頂點到樹頂點集的最小邊中相對的頂點
7 bool foot[n+1];//表示是否已經為樹頂點，初始為false
8 memset(lowcost,0,sizeof(lowcost));
9 memset(closet,0,sizeof(closet));
10 foot[1]=true;//假設先把1作為初始頂點
11 for(int i=2;i<=n;i++){//假設從節點一開始
12 foot[i]=false;
13 closet[i]=1;
14 lowcost[i]=c[1][i];
15 }
16 for(int i=1;i<n;i++){
17 int min=99999;
18 int j=1;
19 for(int k=2;k<=n;k++){//計算非樹頂點到樹頂點集的最短路徑，并把對應頂點記為j
20 if((lowcost[k]<min)&&(foot[k]==false)){
21 min=lowcost[k];
22 j=k;
23 }
24 }
25 cout <<"選邊"<< "("<<closet[j] << "," <<j<<")" << endl;//把改變歸為已選邊，并把foot[j]設為true
26 foot[j]=true;
27 for(int k=2;k<=n;k++){//由于新的頂點加入樹頂點，是以要更新非樹頂點到樹頂點集的最短路徑lowcost[j]，和對應的clost[j]
28 if((c[j][k]<lowcost[k])&&(foot[k]==false)){
29 lowcost[k]=c[j][k];
30 closet[k]=j;
31 }
32 }
33 }
34
35
36 }
37 int main()
38 {
39 cout << "請輸入圖的頂點數" << endl;
40 int n;
41 cin >>n;
42 cout << "請輸入圖的邊數" << endl;
43 int m;
44 cin >> m;
45 cout << "請輸入圖的邊的兩個端點和邊的長度" << endl;
46 int c[100][100];
47 for(int i=1;i<=n;i++){
48 for(int j=1;j<=n;j++){
49 c[i][j]=99999;
50 }
51 }
52 int i1,j,k;
53 for(int i=1;i<=m;i++){
54 cin >>i1 >> j >> k;
55 c[i1][j]=k;
56 c[j][i1]=k;
57 }
58 Prim(n,c);
59 return 0;
60
61 } 運作結果如下