连通图的生成树的定义：所谓一个连通图的生成树是一个极小的连通子图，它含有图中的全部n个顶点，但是只足以构成一棵树的n-1条边。
- 通过上面的定义可得出连通图生成树的3个条件：
1、图示连通图。
2、图中包含N个顶点。
3、图中边的数量等于N-1。
例题：
假设现在有N个顶点，每个顶点连接的路径不一样。请你设计一个算法，快速找出能覆盖所有顶点的路径。
image.png
注意：这个问题并不是求两点之间的最短路径问题；而是设计一个路线，能够覆盖所有顶点。
准备工作
首先拿到图之后，将图转化为邻接矩阵的形式。下面两个算法都会用到邻接矩阵。
创建邻接矩阵：
let INFINITYC = 65535
let MAXVEX = 20
/* 创建邻接矩阵 */
struct MGraph {
var arc = [Array<Int>]()
var numVertexes:Int = 0
var numEdges:Int = 0
}
func createMGraph(_ G: inout MGraph) -> Void {
//输入边数和顶点数
G.numEdges = 15 //边数
G.numVertexes = 9 //顶点
G.arc = [Array<Int>](repeating: [Int](repeating: 0, count: G.numVertexes), count: G.numVertexes)
//初始化图
for i in 0..<G.numVertexes {
for j in 0..<G.numVertexes {
if i == j {
G.arc[i][j] = 0
} else {
G.arc[i][j] = INFINITYC
}
}
}
G.arc[0][1]=10;
G.arc[0][5]=11;
G.arc[1][2]=18;
G.arc[1][8]=12;
G.arc[1][6]=16;
G.arc[2][8]=8;
G.arc[2][3]=22;
G.arc[3][8]=21;
G.arc[3][6]=24;
G.arc[3][7]=16;
G.arc[3][4]=20;
G.arc[4][7]=7;
G.arc[4][5]=26;
G.arc[5][6]=17;
G.arc[6][7]=19;
for i in 0..<G.numVertexes {
for j in i..<G.numVertexes {
G.arc[j][i] = G.arc[i][j]
}
}
}
算法一：普⾥姆(Prim)算法
该算法的关键点是俩个数组，adjvex[]用于记录相关顶点下标(eg: adjvex[5] == 0，表示此时V5与V0相连)；lowcost[]用于记录相关顶点之间边的权值(eg: lowcost[1] == 10, 表示此时V0与V1之间边的权值为10)；注意此时为初始状态，假定V0 已经存入树里面。
image.png
/**
Prim算法生成最小生成树
*/
func MiniSpanTree_Prim(_ G: MGraph) -> Void {
//计数
var sum = 0
//保存相关顶点下标, 初始化，假定所有顶点都与V0相连接
var adjvex = [Int](repeating: 0, count: G.numVertexes)
//保存相关顶点间的权值
var lowcost = [Int]()
//初始化第一个权值为0，即V0加入生成树
lowcost.append(0)
//1、初始化
for i in 1..<G.numVertexes { //循环除下标为0以为的全部顶点
lowcost.append(G.arc[0][i]) //将于V0相关的所有权值存入到数组中
}
//2、循环除了下标为0以外的全部顶点，找到lowcost数组中最小的顶点K
for _ in 1..<G.numVertexes {
/*初始化最小权值为 ∞*/
var min = INFINITYC
var k = 0
///获取当前能拿到的所有 边 中，权值最小的边的尾顶点
var j = 0
while j < G.numVertexes { //循环所有顶点
/*如果当前权值不为0，且权值小于min*/
if lowcost[j] != 0 && lowcost[j] < min {
/*当前权值为最小值，并更新min*/
min = lowcost[j]
k = j
}
j += 1
}
/*打印当前顶点边中权值最小的边*/
print("(V\(adjvex[k]), V\(k)) = \(G.arc[adjvex[k]][k])")
sum += G.arc[adjvex[k]][k]
//3、将当前顶点的权值设置为0，表示此顶点已经完成任务
lowcost[k] = 0
/**
循环所有顶点，找到与顶点K相连接的顶点
1.与顶点 k 相连接
2.该节点没有被加入生成树
3.顶点 k 与 顶点 j 之间的权值 小于 顶点 j 与其他顶点的权值，则更新lowcost数组
*/
///每次要遍历的顶点是随机的，所以要每次要从头开始遍历。但是不需要跟 0 进行比较
for i in 1..<G.numVertexes { //遍历顶点（0之外，此时联想一下二位数组，假设在第二行，则从[1,1]开始，如果在第三行，则从[2,1]开始）
if lowcost[i] != 0 && G.arc[k][i] < lowcost[i] {
lowcost[i] = G.arc[k][i]
adjvex[i] = k
}
} }
print("sum = \(sum))")
}
var G = MGraph.init()
createMGraph(&G)
MiniSpanTree_Prim(G)
输出结果为：
(V0, V1) = 10
(V0, V5) = 11
(V1, V8) = 12
(V8, V2) = 8
(V1, V6) = 16
(V6, V7) = 19
(V7, V4) = 7
(V7, V3) = 16
sum = 99
算法二：克鲁斯卡尔(Kruskal)算法
此算法的关键是，先规划路线，将每一条边的起始位置,结束位置以及权重都事先统计出来，然后在所有的路径中规划最小生成树。
思路：
1、将 邻接矩阵 转化为 边表数组
2、对 边表数组 根据权值按照从小到大的顺序排序
3、遍历所有的边，通过 parent 数组找到边的连接信息，避免闭环问题
4、如果不存在闭环问题，则加入到 最小生成树种 种，并且修改 parent 数组
image.png
第一次执行最小生成树
image(1).png
第二次执行最小生成树
image(2).png
第三次执行最小生成树
image(3).png
以此类推，第八次执行最小生成树的时候
第八次执行最小生成树
注意：此时begin == 5，在parent数组中 parent[5] == 8；则找到8，parent[8] == 6，所以n = 6。因为end == 6，并且parent[6] == 0 所以m = 6。
image(8).png
就这样一直执行下去，直到执行完毕
Kruskal 算法代码如下：
1、定义边表数组的结构：
/* 对象数组Edge结构的定义 */
struct Edge {
var begin:Int = 0
var end:Int = 0
var weight:Int = 0
}
2、创建排序函数与查找函数，用于对边表数组进行排序和查找尾结点
func sort(_ G: MGraph, _ edges: inout [Edge]) -> Void {
//根据权值大小进行排序（从小到大）
for i in 0..<G.numEdges {
for j in i+1..<G.numEdges {
if edges[i].weight > edges[j].weight {
edges.swapAt(i, j)
}
}
}
print("边集数组根据裙纸排序之后：")
for k in 0..<G.numEdges {
print("(\(edges[k].begin), \(edges[k].end)) \(edges[k].weight)")
}
}
func Find(_ parent: [Int], _ f: Int) -> Int {
var num = f
while parent[num] > 0 {
num = parent[num]
}
return num
}
3、规划最小生成树
/**
生成最小生成树
*/
func MiniSpanTree_Kruskal(_ G: MGraph) -> Void {
//定义一个数组用来判断边与边是否形成环路，用来记录顶点见的连接关系，通过它来防止最小生成树产生闭环
var parent = [Int](repeating: 0, count: MAXVEX)
//定义边集数组，edge的结构为begin,end,weight,均为整型
var edges = [Edge](repeating: Edge.init(), count: MAXVEX)
//1、构建边集数组
var k = 0
for i in 0..<G.numVertexes-1 {
for j in i+1..<G.numVertexes {
//如果当前路径的权值 != ∞
if G.arc[i][j]<INFINITYC {
//将路径对应的begin,end,weight 存储到edges 边集数组中
edges[k].begin = i
edges[k].end = j
edges[k].weight = G.arc[i][j]
//边集数组计算器 k++
k += 1
}
}
}
//2、对边集数组进行排序
sort(G, &edges)
//3、计算最小生成树
print("打印最小生成树：")
var sum = 0
/* 循环每一条边 G.numEdges 有15条边 */
for i in 0..<G.numEdges {
//获取begin，end 在parent数组中的信息
//如果 n = m，将 begin 和 end 连接，就会产生闭环
let n = Find(parent, edges[i].begin)
let m = Find(parent, edges[i].end)
/* 如果 n != m 说明此边没有与现有的生成树形成环路 */
if n != m {
/*将此边的结尾顶点放入下标为起点的parent中*/
/*表示此顶点已经在生成树集合中*/
parent[n] = m
/*打印最小生成树路径*/
print("(\(edges[i].begin), \(edges[i].end)) \(edges[i].weight)")
sum += edges[i].weight
}
}
print("sum = \(sum)")
}
var G = MGraph.init()
createMGraph(&G)
MiniSpanTree_Kruskal(G)
4、输出结果为：
边集数组根据裙纸排序之后：
(4, 7) 7
(2, 8) 8
(0, 1) 10
(0, 5) 11
(1, 8) 12
(3, 7) 16
(1, 6) 16
(5, 6) 17
(1, 2) 18
(6, 7) 19
(3, 4) 20
(3, 8) 21
(2, 3) 22
(3, 6) 24
(4, 5) 26
打印最小生成树：
(4, 7) 7
(2, 8) 8
(0, 1) 10
(0, 5) 11
(1, 8) 12
(3, 7) 16
(1, 6) 16
(6, 7) 19
sum = 99
网友评论