Prim算法

变量解释：

Prim算法需要三个数组和一个mincost变量。

1.  mincost就是用于记录从源点开始，生成这个生成树所需要的最小代价。

2.  adjvex[]数组：用于记录顶点之间的路径， 比如从源点出发，生成了一个生成树，此时我想知道，顶点3是从源点经过哪一个顶点到达3顶点的。则可以访问adjvex[3]即可，adjvex[i]里面保存的就是从哪一个顶点到达i顶点的。

3.  lowcost[]数组： 用于记录从顶点出发到达各个顶点所需要的最小代价，例如我想知道到达顶点3需要多少代价，则访问lowcost[3]即可，这记录的是从源点到顶点3需要的最小代价。

4.  visited[]数组，用于判断某个顶点是否已经加入生成树，若visited[i]=0, 表示i顶点还未加入生成树。

变量说明：

比如: 此时prim算法进行到了某一步，得到上图的数组表。

第一，adjvex[]数组，adjvex[V3] = 2 表示经过顶点V2到达顶点V3的，

                                  adjvex[V0]=0,  表示从顶点0到达顶点0的，即 V0是源点

第二：lowcost[]数组， lowcost[v1]=34 ， 表示从源点到达V1需要34的代价。

    **不要看lowcost[i]=0的值，我只是用这个图片举例，因为我是网上找不到其他的可用的图了，所以就用上图代替了，搞明白上述说的adjvex数组和lowcost数组是干什么的就好。

prim算法：

1.首先创建一个有权无向图。

2.对这个有权无向图进行prim算法

创建有权无向图：

#include<iostream>
using namespace std;
#define MaxSize 100
#define INF 55665typedef struct{int vertex[MaxSize];int arc[MaxSize][MaxSize];int vertexNum, arcNum;
}Graph;int visited[MaxSize];void SetVisited(Graph G, int visited[])
{for(int i=0; i<G.vertexNum; i++){visited[i]=0;}
}void CreatGraph(Graph &G, int n, int e, int arr[])
{G.vertexNum=n;G.arcNum=e;for(int i=0; i<G.vertexNum; i++){G.vertex[i]=arr[i];}for(int i=0; i<G.vertexNum; i++){for(int j=0; j<G.vertexNum; j++){if(i==j){G.arc[i][j]=0;}else{G.arc[i][j]=INF;}}}for(int i=0; i<G.arcNum; i++){int a,b,w;cin>>a>>b>>w;G.arc[a][b]=w;G.arc[b][a]=w;} }void show(Graph G){for(int i=0; i<G.vertexNum; i++){for(int j=0; j<G.vertexNum; j++){cout<<G.arc[i][j]<<" ";}cout<<endl;}
}

Prim算法：

//查找顶点v到非生成树代价最小的那个邻接点
int find_arc(Graph G, int lowcost[])
{int min=65566;int index;for(int i=0; i<G.vertexNum; i++){if(visited[i]==0 && lowcost[i]<min){min = lowcost[i];index = i;}}return index;}void Prim(Graph G, int v)
{int adjvex[MaxSize];    int lowcost[MaxSize];int mincost=0;//初始化for(int i=0; i<G.vertexNum; i++){adjvex[i]=v;				//表示从顶点v到达各个顶点i的 lowcost[i]=G.arc[v][i];		//此时生成树只有顶点v，所以生成树到非生成树的代价就是顶点v到各个顶点的代价 }visited[v]=1;					//v顶点已经加入了生成树，所以设置visited为1 for(int i=1; i<G.vertexNum; i++){//找到生成树到非生成树代价最小的顶点 int index = find_arc(G,lowcost);visited[index]=1;    	//把找到的顶点加入生成树 mincost += lowcost[index];cout<<"("<<adjvex[index]<<","<<G.vertex[index]<<")"<<"  ";//加入生成树后，判断是否因为加入新节点，导致生成树到非生成树之间代价减小。 for(int j=0; j<G.vertexNum; j++){if(G.arc[index][j]<lowcost[j] && visited[j]==0){lowcost[j]= G.arc[index][j];   adjvex[j]=index;}}}//打印prim算法历程 cout<<endl;cout<<"vertex=   ";for(int i=0; i<G.vertexNum; i++){cout<<adjvex[i]<<" ";}cout<<endl;cout<<"lowcost=  ";for(int i=0; i<G.vertexNum; i++){cout<<lowcost[i]<<" "; }cout<<endl;cout<<"mincost= "<<mincost<<endl;
}int main()
{int n,e;cin>>n>>e;int arr[n];for(int i=0; i<n; i++){cin>>arr[i];}Graph G;CreatGraph(G, n, e, arr);//show(G);Prim(G, 3);return 0;
}

test

6 10
0 1 2 3 4 5
0 1 6
0 2 1
0 3 5
1 2 5
1 4 3
2 3 5
2 4 6
2 5 4
3 5 2
4 5 6

结果: