图的应用——最小生成树

最小生成树

• 生成树（极小连通子图）：含有图中全部n个顶点，但只有n-1条边。并且n-1条边不能构成回路。
  

  在这里插入图片描述
• 生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。
  

  在这里插入图片描述

求最小生成树

• 使用不同的遍历图的方法，可以得到不同的生成树
• 从不同的顶点出发，也可能得到不同的生成树。
• 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。在网的多个生成树中，寻找一个各边权值之和最小的生成树

构造最小生成树的准则

• 必须只使用该网中的边来构造最小生成树；
• 必须使用且仅使用n-1条边来联结网络中的n个顶点
• 不能使用产生回路的边

贪心算法(Greedy Algorithm)

• 算法原理：以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。undefined
• 算法优点：因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效率高。贪婪算法的精神就是“只顾如何获得眼前最大的利益”,有时不一定是最优解。

Prim（普里姆）算法

算法思想 —— 归并顶点

• 在图中任取一个顶点K作为开始点。令U={k}，W=V-U，其中V为图中所有顶点集
• 在U中选取一个顶点，W中选取另一个顶点，使二者对应的边是最短的一条。将该边作为最小生成树的边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点。
• 重新调整U中顶点到W中顶点的距离， 使之保持最小，再重复此过程，直到W为空集止。
  

  在这里插入图片描述

算法设计

• 在算法中需要设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边struct { VertexType adjvex; // U集中的顶点 VRType lowcost; // 边的权值 } closedge[MAX_VERTEX_NUM];void MiniSpanTree_P(MGraph G, VertexType u){ // 用普利姆算法从顶点u出发构造网G的最小生成树 k = LocateVex_MG(G, u); for(j = 0; j < G.vexnum; ++j) // 辅助数组初始化 if(j != k){ closedge[j].adjvex = new char[10]; strcpy(closedge[j].adjvex, G.vexs[k]); closedge[j].lowcost = G.arcs[k][j].adj; } closedge[k].lowcost = 0; // 初始, U = {u} closedge[k].adjvex = new char[10]; strcpy(closedge[k].adjvex, G.vexs[k]); for(i = 0; i > G.vexnum; i ++){ // //继续向生成树上添加顶点 mincost = INF; // 找权值最小的顶点 for(m = 0; m < G.vexnum; ++m) if(mincose > closedge[m].lowcost && closedge[m].lowcost != 0){ mincose = closedge[m].lowcost; k = m; } // 求出加入生成树的下一个顶点(k) if(closedge[k].lowcost != 0) //输出生成树上一条边 cout << closedge[k].adjvex << G.vexs[k] << closedge[k].lowcost; closedge[k].lowcost = 0; // 第k顶点并入U集 for(j = 0; j < G.vexnum; j++) // 修改其它顶点的最小边 if(G.arcs[k][j].adj < closedge[j].lowcost){ strcpy(closedge[j].adjvex, G.vexs[k]); closedge[j].lowcost = G.arcs[k][j].adj; } } }
• lowcosti:表示以i为终点的边的最小权值,当lowcosti=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
• adjvexti:表示对应lowcosti的起点，即说明边<adjvexi,i>是MST的一条边，当adjvexi=0表示起点i加入MST

KrusKal（克鲁斯卡尔）算法

算法思想 —— 归并边

• 将图中所有边按权值递增顺序排列；
• 依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。
  

  在这里插入图片描述

算法设计

构造非连通图 ST=( V,{ } );

k = i = 0; // k 计选中的边数

while (k<n-1) {

++i;

检查边集 E 中第 i 条权值最小的边(u,v);

**若(u,v)加入ST后不使ST中产生回路，

则 输出边(u,v); 且 k++;**

}

typedef struct {
	// 增加边结构定义
	int beginvex, endvex;  // 边的起点、终点
	VRType cost;  // 边的权值
} edgetype;

edgetype edges[MAX_VERTEX_NUM];

void MiniSpanTree_Kruskal(ALGraph &G){
	int parents[MAX_VERTEX_NUM];
	cin >> G.vexnum >> G.arcnum;  // 顶点数、弧数
	for(i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.vertices[i].data = new char[10];
		cin >> G.vertices[i].data;  // 读入顶点信息并初始化
		G.vertices[i].firstarc = NULL;
	}
	for(k = 0; k < G.arcnum; k++){
		// 建立边表
		v1 = new char[10];
		v2 = new char[10];
		cin >> v1 >> v2 >> w;
		i = LocateVex_ALG(G, v1);
		j = LocateVex_ALG(G, v2);
		edges[k].beginvex = i;
		edges[k].endvex = j;
		edges[k].cost = w;
		p = new ArcNode;
		p->info = NULL;
		p->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p;
	}
	Sort(G, edges);  // 按权值大小，对边进行排序
	for(i = 0; i < G.vexnum; i++)
		parents[i] = 0;
	for(i = 0; i < G.arcnum; i++){
		bnf = Find(parents, edges[i].beginvex);  // 查找边头分量
		edf = Find(parents, edges[i].endvex);  // 查找边尾分量
		if(bnf != edf){
			parents[bnf] = edf;
			cout << edges[i].beginvex << edges[i].endvex;
			cout << " " << edges[i].cost << endl;
		}
	}
}

int Find(int parents[], int f){
	// 查找函数
	while(parents[f] > 0) f = parents[f];
	return f;
}

Prim和KrusKal比较

算法名 | Prim | KrusKal

• | - | - 时间复杂度 | O(n^2) | O(eloge) 适应范围 | 稠密图 | 稀疏图