Prim

Prim

Winter Lv4
  2023-03-24 19:47:09 2023-03-24 19:47 Created   2023-03-25 20:04:40 2023-03-25 20:04 Updated    1.4k Words  6 Mins  

问题背景

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

思路分析

数学抽象

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

关键思路分析

  • 以点为中心

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

  • 更新权值

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

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

代码设计

  • 如何存储点的信息

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #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一个极大值来检查是否连通。这就是算法中的关键思路

  • 判断条件（如上）

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*****************************************************************//**
 * \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;

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


总结

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

hh

  • Post title：Prim
  • Post author：Winter
  • Create time：2023-03-24 19:47:09
  • Post link：https://spikeihg.github.io/2023/03/24/Prim/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
On this page
Prim
  1. 问题背景
  2. 思路分析
    1. 数学抽象
    2. 关键思路分析
      1. 以点为中心
      2. 更新权值
    3. 代码设计
      1. 如何存储点的信息
      2. 判断条件（如上）
  3. 完整代码
  4. 总结