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
来源: http://www.jianshu.com/p/0ee8176d200b