Prim算法思想如下：
首先將圖的點分為兩部分，一種是訪問過的u，一種是沒有訪問過的v
1:首先在訪問過的頂點中找一條到u到v的一條權(quán)值最小的邊
2:然后將這條邊中的v中的頂點添加到u中，
直到邊的個數(shù)=頂點數(shù)-1
如下圖所示，下面是prim算法的圖示
image.png
（原圖）
image.png
(a -1)
image.png
(a -2)
image.png
(a -3)
image.png
(a -4)
image.png
(a -5)
image.png
(a -6)
<h3>算法的流程圖如下：</h3>
image.png
代碼如下：
//
// main.cpp
// Prim
//
// Created by 橘子和香蕉 on 2018/12/2.
// Copyright ? 2018 橘子和香蕉. All rights reserved.
//
/*
圖的存儲采用鄰接表
算法的思想就是柬甥，從已經(jīng)找到的集合u和從還沒有找到的集合v中選取最小的邊
這就要標(biāo)示那些結(jié)點訪問過墙牌，哪些結(jié)點沒有訪問過；
還要維護一個數(shù)組暗甥，這個數(shù)組的目的就是記錄u到v中邊的權(quán)重的集合喜滨；
怎么記錄記錄呢？
1：首先將開始點作為基點撤防，并且將這個頂點設(shè)置為訪問過虽风，來初始化這個數(shù)組，每個數(shù)組的的下標(biāo)就是一個結(jié)點寄月，使每個數(shù)據(jù)項==開始點到每個結(jié)點對應(yīng)的距離辜膝；
2:循環(huán)條件：一直到生成樹的邊的個數(shù)=頂點個數(shù)-1；
循環(huán)體：「 在距離的數(shù)組中找到一個最小的邊漾肮，注意厂抖，這個頂點沒有訪問過；
找到這個頂點克懊，然后將它標(biāo)記為訪問過忱辅；
以這個頂點來更新這個距離數(shù)組；如果新的頂點到下標(biāo)的頂點的距離小于之前的距離谭溉，就要跟更新墙懂；更新的這個頂點要是沒有訪問過的
！０缒睢Ｋ鸢帷！９裼搿Ｇ汕凇！Ｅ啊Ｂぁ！Ｕ城选签舞！注意，下面的不是演習(xí)：
距離的數(shù)組柒瓣；下標(biāo)是頂點；數(shù)據(jù)項是對應(yīng)的距離吠架，就是找的頂點到?jīng)]有找到的點的邊的 權(quán)重芙贫，也就是u中到這個下標(biāo)頂點的距離；
」
首先隨便指一個點作為遍歷的開始點傍药；
先
*/
#include <iostream>
using namespace std;
typedef struct node{
char data;//數(shù)據(jù)域
int isAccess;//用來標(biāo)記是否被訪問過
}node;
#define VERTEXNUM 100
class Graph{
private:
node vertex[VERTEXNUM];//頂點表
int edge[VERTEXNUM][VERTEXNUM];//邊表
int vertexNum;//頂點個數(shù)
int edgeNum;//邊的個數(shù)
int locate(char data);//在頂點表中找data的位置
void initEdge();
public:
Graph(int vertexNum,int edgeNum);//構(gòu)造函數(shù)磺平，初始化vertexNUm和edgeNum
void create();//創(chuàng)造一個圖
int Prim(char data);//prim算法
void printGraph();//輸出
};
void Graph::printGraph(){
cout<<endl;
cout<<endl;
cout<<"頂點邊:\n";
cout<<"vertexNum:"<<vertexNum<<" edgeNum:"<<edgeNum<<endl;
for (int i = 0; i<vertexNum; i++) {
cout<<vertex[i].data<<"\t";
}
cout<<endl;
cout<<"邊表如下：\n";
for (int j = 0; j<vertexNum; j++) {
for (int k = 0; k<vertexNum ; k++) {
cout<<edge[j][k]<<"\t";
}
cout<<endl;
}
}
int Graph::locate(char data){
for (int i = 0; i<vertexNum;i++) {
if(vertex[i].data == data){
return I;
}
}
return -1;
}
Graph::Graph(int vertexNum,int edgeNum){
this->vertexNum = vertexNum;
this->edgeNum = edgeNum;
initEdge();
}
void Graph::create(){
cout<<"input Graph data\n";
for (int i = 0; i<vertexNum; i++) {
cin>>vertex[i].data;
vertex[i].isAccess = false;
}
char start ,end;
int wieght = -1;
for (int j = 0; j<edgeNum; j++) {
cout<<"input start and end of edge:\n";
cin>>start>>end>>wieght;
int startPosition = locate(start);
int endPosition = locate(end);
edge[startPosition][endPosition] = wieght;
edge[endPosition][startPosition] = wieght;
}
}
void Graph:: initEdge(){//初始化edge數(shù)組
for (int i = 0; i<vertexNum; i++) {
for (int j =0 ; j<=i; j++) {
edge[i][j] = INT_MAX;//每一項都設(shè)置為最大項
edge[j][i] = INT_MAX;
}
}
for (int i = 0; i<vertexNum; i++) {
for (int j = 0; j<vertexNum; j++) {
cout<<edge[i][j]<<"\t";
}
cout<<endl;
}
}
int Graph::Prim(char data){
int numWeight = -0;//定義權(quán)重魂仍，圖的最小權(quán)重
int distince[vertexNum];//定義距離的數(shù)據(jù)
int position = locate(data);
vertex[position].isAccess = true;//設(shè)置為訪問過
int minNodePostion = position;//定義最小結(jié)點
for (int i =0; i<vertexNum; i++) {//初始化距離數(shù)組
if(edge[minNodePostion][i] < INT_MAX){
distince[i] = edge[minNodePostion][I];
}else{
distance[I] = INT_MAX
}
}
int treeEdgeNum = 0;
while (treeEdgeNum < vertexNum -1) {
int min = INT_MAX;
for (int i =0 ; i<vertexNum; i++) {
if( vertex[i].isAccess == false && distince[i] < min){
min = distince[I];
minNodePostion = i;
}
}
vertex[minNodePostion].isAccess = true;
numWeight += distince[minNodePostion];
for (int i = 0; i<vertexNum; i++) {
if(vertex[i].isAccess == false && edge[minNodePostion][i] < distince[I]){
distince[i] = edge[minNodePostion][I];
}
}
for (int i = 0; i<vertexNum; i++) {
cout<<distince[i]<<"\t";
}
cout<<endl;
treeEdgeNum++;
}
return numWeight;
}
int main(){
Graph a(6,8);
a.create();
a.printGraph();
int num = a.Prim('1');
cout<<"num: "<<num<<endl;
return 1;
}
測試的圖就是上面的圖a
運行結(jié)果如下：
image.png
