Prim

问题背景

加入你遇到这样一个问题，在一个表示了很多村庄的交通图中，其中有每两个村庄之间的交通开销。我们怎么才能够将所有的村庄都相连，并且没有回路，即离散数学里的极小连通图。我们的Prim算法给出了一种经典的解决方法。

思路分析

数学抽象

我们运用离散数学中的图来简化模型，将村庄视作点，边视作连线，然后赋予对应的一个权值。

关键思路分析

• 以点为中心

  因为最终生成的路径一定要包含所有的顶点，所以我们可以从点的角度考虑。任取一个点，找到与其邻接的所有顶点，然后找到最小的权值对应的顶点，把该点放入我们的点集合里，然后然后重复上面的步骤就可以了。

• 更新权值

  一个比较关键的地方就是要不断检查权值，然后对应进行更新。

  其实思路总体还是比较清晰，简单，不过在代码里面有很多巧妙的地方

代码设计

• 如何存储点的信息

  我们定义一个Prim特有的数据结构来进行存储

  // 这个就是Prim算法的特殊数据结构，就是你使用这个算法就必须要想起的一个结构
  //  
  // ADT
  typedef struct closeedge {
  	int adjvex;
  	int lowcast;	//?  low cast 
  };

  思路很妙，lowcast记录该点的最小开销，而adjvex对应最小开销的对应的边。不过我们还有一个问题，那就是我们会发现，怎么检查一个点是否已经在我们的已经考虑过的集合里，然后又怎么决定两条边是否相连，我们分别对下面 的问题进行解决。

  #define OK	1
  #define BAD	0
  #define MVNum	100
  // ? love favorite 
  #define INF 0x3F3F3F3F
  using Status = int;
  using VerTexType = char;
  using ArcType = int;
  typedef struct {
  	VerTexType vertices[MVNum];
  	ArcType arcs[MVNum][MVNum];
  	int vertexnum{MVNum};
  	int arcnum{ 0 };		//? Low cost
  }AMGraph;

  我们使用边集数组的数据结构来表示，（这就是数据结构的魅力），然后我们在初始化的时候将对角线初始化为0，以lowcast=0来代表不能建路径，以INF一个极大值来检查是否连通。这就是算法中的关键思路

• 判断条件（如上）

完整代码

/*****************************************************************//**
 * \file   MTS.cpp
 * \brief  For Ms.Winter
 *  3/24/2023
 * \author 86158
 * \date   March 2023
 *********************************************************************/
// Now we come to the MTS
//? Most Cost Spannig Tree 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
// Macro 
#define OK	1
#define BAD	0
#define MVNum	100
// ? love favorite 
#define INF 0x3F3F3F3F
using Status = int;
using VerTexType = char;
using ArcType = int;
typedef struct {
	VerTexType vertices[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vertexnum{MVNum};
	int arcnum{ 0 };		//? Low cost
}AMGraph;

inline int locate(const AMGraph& G, int v)
{
	for (int i = 0; i < G.vertexnum; i++)
		if (v == G.vertices[i])
			return i;
	return -1;
}
Status CreateUDN(AMGraph& G)
{
	memset(G.arcs, INF, sizeof(G.arcs));
	for (int i = 0; i < G.vertexnum; i++)
		G.arcs[i][i] = 0;		// It must been done !
	cout << "first please input the arcnum and vernum of the graph";
	cin >> G.vertexnum >> G.arcnum;
	cout << "Now please enter the vertices first";
	for (int i = 0; i < G.vertexnum; i++)
		cin >> G.vertices[i];
	VerTexType v1 = 0, v2 = 0;
	ArcType weight{ -1 };
	int i{ 0 }, j{ 0 };
	cout << "Now please enter all the arcs and weight";
	for (int j = 0; j < G.arcnum; j++)
	{
		cin >> v1 >> v2 >> weight;
		i = locate(G, v1);
		j = locate(G, v2);
		G.arcs[i][j] = weight;			// UDN
		G.arcs[j][i] = weight;			// UDN
	}
	return OK;
}


// 这个就是Prim算法的特殊数据结构，就是你使用这个算法就必须要想起的一个结构
//  
// ADT
typedef struct closeedge {
	int adjvex;
	int lowcast;	//?  low cast 
};

// 关键思路的分析 ，就是把点作为一个集合，从所有与这个集合相连的点中挑选
// 运用一个数组存储对应的顶点的最小开销，与此同时，再使用一个数组来记录对应的边的
// 另一个顶点 然后 为了判定一个点是否已经在集合内，我们将其cast 设置为0
// 并且最开始的时候我们的矩阵里使用的是一个INF 数据设计很巧妙
// The prim from a blogger 
void Prim(AMGraph& G, int v)	//? We choose a start point v0
{
	// First we use the closeedge
	closeedge C[MVNum];		// Special data struct
	// Init it with the v point
	int min_casts = 0;
	for (int i = 0; i < G.vertexnum; i++)
	{
		C[i].adjvex = v;
		C[i].lowcast = G.arcs[v][i];
	}
	cout << "对应的边是";
	for (int i = 1; i < G.vertexnum; ++i)
	{
		int temp = 0;
		int min_cast = INF;	// Just the case
		for (int j = 0; j < G.vertexnum; j++)
		{
			if (C[j].lowcast != 0 && C[j].lowcast < min_cast)
			{
				temp = j;
				min_cast = C[j].lowcast;
			}
		}
		cout << " ( " << temp << "," << C[temp].adjvex << " )";
		min_casts += min_cast;
		C[temp].lowcast = 0;	// You've seen what the use just to see if used!!!
		for (int k = 0; k < G.vertexnum; k++)
		{
			if (C[k].lowcast != 0 && G.arcs[temp][k] < C[k].lowcast)
			{
				C[k].lowcast = G.arcs[temp][k];
				C[k].adjvex = k;		// Now you see what the adjvex mean
			}
		}
	}
	cout << "All casts are " << min_casts << endl;
}
// we could see the o(n^2)
// We could also use the KrustalAL other method

//? Krustal 算法的实现
// 对应的我们KRUSTAL 算法也有对应的特有的数据结构 就是我们的边集数组

typedef struct {
	int begin, end;
	ArcType weight;		// ? the begin mean the point of the arcs
}Edge;

// 并且我们也要用到并查集的知识 感觉非常巧妙

总结

之前很少细想算法设计的思路，自己的思维没有得到锻炼，其中的数学简化思想与代码设计很巧妙与优美，完