图的最小生成树——Prim算法

Prim算法思想如下
首先将图的点分为两部分,一种是访问过的u,一种是没有访问过的v

1:首先在访问过的顶点中找一条到u到v的一条权值最小的边
2:然后将这条边中的v中的顶点添加到u中,
直到边的个数=顶点数-1
如下图所示,下面是prim算法的图示
图的最小生成树——Prim算法
(原图)
图的最小生成树——Prim算法
(a -1)
图的最小生成树——Prim算法
(a -2)
图的最小生成树——Prim算法
(a -3)
图的最小生成树——Prim算法
(a -4)
图的最小生成树——Prim算法

(a -5)
图的最小生成树——Prim算法

(a -6)

算法的流程图如下:


图的最小生成树——Prim算法
代码如下:
//
//  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
运行结果如下:
图的最小生成树——Prim算法

上一篇:数据结构——图的广度遍历


下一篇:迷宫求解(回溯思想,栈实现c++,数据结构)