Prim算法思想如下：
首先将图的点分为两部分，一种是访问过的u，一种是没有访问过的v
1:首先在访问过的顶点中找一条到u到v的一条权值最小的边
2:然后将这条边中的v中的顶点添加到u中，
直到边的个数=顶点数-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.
//
/*
图的存储采用邻接表
算法的思想就是，从已经找到的集合u和从还没有找到的集合v中选取最小的边
这就要标示那些结点访问过，哪些结点没有访问过；
还要维护一个数组，这个数组的目的就是记录u到v中边的权重的集合；
怎么记录记录呢？
1：首先将开始点作为基点，并且将这个顶点设置为访问过，来初始化这个数组，每个数组的的下标就是一个结点，使每个数据项==开始点到每个结点对应的距离；
2:循环条件：一直到生成树的边的个数=顶点个数-1；
循环体：「 在距离的数组中找到一个最小的边，注意，这个顶点没有访问过；
找到这个顶点，然后将它标记为访问过；
以这个顶点来更新这个距离数组；如果新的顶点到下标的顶点的距离小于之前的距离，就要跟更新；更新的这个顶点要是没有访问过的
！！！！！！！！！！！！注意，下面的不是演习：
距离的数组；下标是顶点；数据项是对应的距离，就是找的顶点到没有找到的点的边的 权重，也就是u中到这个下标顶点的距离；
」
首先随便指一个点作为遍历的开始点；
先
*/
#include <iostream>
using namespace std;
typedef struct node{
char data;//数据域
int isAccess;//用来标记是否被访问过
}node;
#define VERTEXNUM 100
class Graph{
private:
node vertex[VERTEXNUM];//顶点表
int edge[VERTEXNUM][VERTEXNUM];//边表
int vertexNum;//顶点个数
int edgeNum;//边的个数
int locate(char data);//在顶点表中找data的位置
void initEdge();
public:
Graph(int vertexNum,int edgeNum);//构造函数，初始化vertexNUm和edgeNum
void create();//创造一个图
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数组
for (int i = 0; i<vertexNum; i++) {
for (int j =0 ; j<=i; j++) {
edge[i][j] = INT_MAX;//每一项都设置为最大项
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;//定义权重，图的最小权重
int distince[vertexNum];//定义距离的数据
int position = locate(data);
vertex[position].isAccess = true;//设置为访问过
int minNodePostion = position;//定义最小结点
for (int i =0; i<vertexNum; i++) {//初始化距离数组
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
运行结果如下：
image.png
网友评论