数据结构----C++实现Prim算法（贪心算法）

叁歲伎倆 2022-10-25 11:26 217阅读 0赞

> ### **理解最小生成树的定义** ###
> 
>  *  **生成树：连通图的生成树是包含全部顶点的一个极小连通子图**
>  *  **生成树的代价：在无向连通网中，生成树上各边的权值之和**
>  *  **最小生成树：在无向连通网中，代价最小的生成树**

### **应用场景：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？** ###

> ### Prim算法——基本思想 ###

**Prim算法：从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有的顶点都纳入为止。**

**                                           Prim算法构造最小生成树的过程**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

> **（1）图采用什么存储结构呢？**

**因为需要不断读取任意两个顶点之间边的权值，所以图采用邻接矩阵存储**

> **（2）如何存储候选最短边集（连接U和V-U的候选最短边）？**

**例如：\{(v0 , v1)34,(v0 , v2)46,(v0, v3)∞,(v0 , v4)∞,(v0, v5 )19\}**

**数组adjvex\[n\]：表示候选最短边的邻接点数组**

**lowcost\[n\]：表示候选最短边的权值**

adjvex\[i\] = j;lowcost\[i\] = w

**含义是：候选最短边（i, j）的权值为w，其中i∈V-U，j∈U**

初始时，lowcost\[v\] = 0，表示将顶点v加入集合U中；

adjvex\[i\] = v，lowcost\[i\] = edge\[v\]\[i\]（0 ≤ i ≤ n-1）

例如：\{(v0 , v0)0, (v0 , v1)34, (v0 , v2)46, (v0, v3)∞, (v0 , v4)∞, (v0, v5 )19\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

**每一次迭代，设数组lowcost\[n\]中的最小权值是lowcost \[j\]，则令lowcost\[j\] = 0，表示将顶点 j 加入集合U中；**

**由于顶点 j 从集合V-U进入集合U，候选最短边集发生变化，需要更新：**

![20210131161609724.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]

> **（3）Prim算法的关键是什么？**

![20210131161741212.png][]

**Prim算法：先构造满足条件的候选最短边集，再查找最短边**

> **Prim算法C++代码实现：**

#include <iostream>
    using namespace std;
    const int MaxVertex = 10;
    const int MaxEdge = 100;
    const int vertexNum = 6;
    typedef string DataType;
    struct shortEdge
    {
    	int adjvex; //邻接点 
    	int lowcost; //最小代价 
    }shortEdge[MaxVertex];
    
    class MGraph
    {
    	public:
    		MGraph(); //构造函数 
    		~MGraph(); //析构函数
    		void Prim(int v); //Prim算法求最小生成树
    		int MinEdge(); //查找最短边的邻接点 
    	private: 
    		DataType vertex[MaxVertex] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
    		int edge[MaxVertex][MaxVertex] = {
       {0,34,46,INT_MAX,INT_MAX,19}, 
    								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
    								{46,INT_MAX,0,17,INT_MAX,25},
    								{INT_MAX,INT_MAX,17,0,38,25},
    								{INT_MAX,12,INT_MAX,38,0,26},
    								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
    };
    //构造函数 
    MGraph::MGraph(){
    		
    }
    //析构函数
    MGraph::~MGraph(){
    
    }
    //构造最小生成树 
    void MGraph::Prim(int v) //从顶点v出发 
    {
    	int i, j, k;
    	for(i=0; i<vertexNum; i++) //初始化辅助数组 
    	{
    		shortEdge[i].lowcost = edge[v][i];
    		shortEdge[i].adjvex = v;
    	}
    	shortEdge[v].lowcost = 0;
    	for(k=1; k<vertexNum; k++) //迭代n-1次 
    	{
    		j = MinEdge(); //寻找最短边的邻接点j 
    		cout<<vertex[j]<<" "<<vertex[shortEdge[j].adjvex]<<" "<<shortEdge[j].lowcost<<" "<<endl;
    		shortEdge[j].lowcost = 0; //顶点j加入集合U 
    		for(i=0; i<vertexNum; i++) //调整辅助数组 
    		{
    			if(edge[i][j]<shortEdge[i].lowcost){
    				shortEdge[i].lowcost = edge[i][j];
    				shortEdge[i].adjvex = j;
    			}
    		}
    	}
    }
    //查找最短边的邻接点 
    int MGraph::MinEdge()
    {
    	int min = INT_MAX, j;
    	for(int i=0; i<vertexNum; i++)
    	{
    		if(shortEdge[i].lowcost<min && shortEdge[i].lowcost!=0)
    		{
    			min = shortEdge[i].lowcost;
    			j = i;
    		}
    	}
    	return j;
    }
    
    int main()
    {
    	MGraph MG{};
    	MG.Prim(0);
    }

> **实现截图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]

> **最小生成树：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][]

> ### 我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞+收藏+加关注喔~ ###
> 
> **如果文章有不正确的地方，欢迎交流指正，我将虚心请教~o(>ω<)o**
> 
> **我会定期更新文章，继续为您提供优质文章**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221024/e9a1590c2b724ce89fb1aa34b402b9f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: /images/20221024/f6de2509739c4df6a14c618afff800b1.png
[20210131161609724.png]: /images/20221024/32a630805c0a412b8edca36c73106634.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: /images/20221024/df4118b5322f45e4a8ce0fa5281879cb.png
[20210131161741212.png]: /images/20221024/f393423d527246f38d83402f7f3e6b9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: /images/20221024/da81585438d44dad86899733b96afbe8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: /images/20221024/7d401780de99467c85bfaba484cf3ce2.png