图的最小生成树_图的最小生成树概念

一 、最小生成树的定义和性质

• 最小生成树说是树，其实上只是图的衍生物(裁掉某些边),并不能用树形结构来写代码
• 最小生成树指的是总权值最小的那颗生成树
• 最小生成树是针对带权无向联通图的
• 最小生成树可能有多个树形，但是一定只有一个序列
• 设顶点数为n 则边数必为n-1

二、Prim算法

定义:图G=(V,E)   生成树T=(U,E1)
步骤:	①判断图G是否为联通图        通过计算对图进行广度搜索得到图的联通分支数,进而判断
        ②初始化生成树T         	   从图G中任取一点加入到生成树T的顶点集合U中
        ③对顶点集合V和顶点集合U，任取x∈V，y∈U。当d(x,y)最小时，将x从集合V中取出放入U中
        ④不断重复上述过程指导顶点集合V为空
1
2
3
4
5

代码（实际上就是不断得从另一集合取合适的点加入U中） 时间复杂度为O(V^2)

	//最小生成树的Prim算法   分成两个集合U、V,求U、V中路径最小的点x,y   x在U内、y在V内。不断的把点从V移动到U
	MGraph_ND* Prim(MGraph_ND* Basic_Graph) {
		if (Basic_Graph->Branch>1)return nullptr;//不连通，无最小生成树
		MGraph_ND* MST = new MGraph_ND(Basic_Graph->Vertex_num);
		int Current_i = 0;
		int Current_j = 0;
		int Max =CountMax(MST);
		int min = 0;
		Prim_InitMST(MST);
		MST->Vertex[0] = Basic_Graph->Vertex[0];//放入第0号元素
		Basic_Graph->Vertex[0] = -1;//取出0号元素
		MST->Vertex_num++;
		//n个节点,n-1次循环
		for (int k = 0; k < Basic_Graph->Vertex_num-1; k++) {
			min =Max;
			for (int i = 0; i < Basic_Graph->Vertex_num; i++) {
				//i在集合V内
				if (Basic_Graph->Vertex[i] != -1) {
					for (int j = 0; j < Basic_Graph->Vertex_num; j++) {
						//j在集合U内
						if (MST->Vertex[j] != -1) {
							if (Basic_Graph->Edge[j][i] <= min && Basic_Graph->Edge[j][i]>0) {
								min = Basic_Graph->Edge[j][i];
								Current_i = i;
								Current_j = j;
							}
						}
					}

				}
					
			}
			Basic_Graph->Vertex[Current_i] = -1;//从集合V中取出
			MST->Vertex[Current_i] = Current_i;//加入集合U
			MST->Edge[Current_j][Current_i] = min;//加边
			MST->Edge[Current_i][Current_j] = min;//加边
			MST->Vertex_num++;
			MST->Edge_num++;
		}
		MST->Branch = Count_Linked();
		return MST;
	}
	
	-----Init
	//Prim算法要求刚开始时 U集合内 点和边均为空
	void Prim_InitMST(MGraph_ND* MST) {
		for (int i = 0; i < MST->Vertex_num; i++) {
			MST->Vertex[i] = -1;//无结点
			for (int j = 0; j < MST->Vertex_num; j++) {
				MST->Edge[i][j] = -1;//无边
			}
		}
		MST->Vertex_num = 0;
		MST->Edge_num = 0;
		MST->Branch = 0;
	}
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

三、Kruskal算法

定义:图G=(V,E)   生成树T=(U,E1)
步骤:	①判断当前图是否为联通图
        ②初始化生成树T      ⭐这里域Prim算法不同的是，Kruskal算法需要刚开始就确定好所有顶点位置，后续再更新边
        ③计算当前的联通分支数      因为生成树内没有边，所有联通分支数就是顶点数
        ④当生成树的联通分支数大于1时：
        			找出生成树内最短的边，记录顶点坐标(u,v)和长度length
        			如果u和v属于不同分支则将u、v划入同一集合中，并更新生成树
        			否则将这条边抛弃⭐(这步很重要,否则会成环)
1
2
3
4
5
6
7
8

可以使用划分等价类的形式，不断得将不同联通分支的点聚合。最终变成只有一个联通分支

代码

//最小生成树的Kruskal算法   已初始化点  只需要找到边
	MGraph_ND* Kruskal(MGraph_ND* Basic_Graph) {
		if (Basic_Graph->Branch > 1)return nullptr;//不连通，无最小生成树
		MGraph_ND* MST = new MGraph_ND(Basic_Graph->Vertex_num);
		int branch = MST->Vertex_num;
		Set *sets[MaxSize];
		Kruskal_InitMST(MST);
		for (int i = 0; i < MST->Vertex_num; i++) {
			sets[i] = new Set(i);
		}
		//连通分支数大于1
		while(branch>1){
			int i;
			int j;
			int Min = 1000;
			for (int  m = 0; m < Basic_Graph->Vertex_num; m++) {
				for (int n = 0; n < Basic_Graph->Vertex_num; n++) {
					//求最小的边
					if (Basic_Graph->Edge[m][n]<=Min && Basic_Graph->Edge[m][n]>0)
					{
						Min = Basic_Graph->Edge[m][n];
						i = m;
						j = n;
					}
				}
			}
			Set* pi=sets[i];
			Set* pj=sets[j];
			while (pi->parent != nullptr) { pi = pi->parent; }
			while (pj->parent != nullptr) { pj = pj->parent; }
			//i和j属于不同联通分支
			if (pi->tag!= pj->tag) {
				Basic_Graph->Edge[i][j] = -1;//从原集合中取出边
				Basic_Graph->Edge[j][i] = -1;
				MST->Edge[i][j] = Min;//向U中放入边
				MST->Edge[j][i] = Min;
				MST->Edge_num++;
				Set* parent = new Set(pi->tag>pj->tag ?pj->tag:pj->tag);//取较小的那个为tag
				pi->parent = parent;
				pj->parent = parent;
				cout << sets[0];
				branch--;
			}
			else {
				Basic_Graph->Edge[i][j] = -1;//i和j属于相同联通分支,应该丢弃,否则构成回路，最终导致死循环
				Basic_Graph->Edge[j][i] = -1;

			}

		}
		return MST;
	}

	----Init
		//Prim算法要求刚开始时 U集合内 边均为空,只有空点
	void Kruskal_InitMST(MGraph_ND* MST) {
		for (int i = 0; i < MST->Vertex_num; i++) {
			MST->Vertex[i] = i;//无结点
			for (int j = 0; j < MST->Vertex_num; j++) {
				MST->Edge[i][j] = -1;//无边
			}
		}
		MST->Edge_num = 0;
		MST->Branch = 0;
	}
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