阅读目录
- 基本概述
- 克鲁斯卡尔算法图解
- 克鲁斯卡尔算法分析
- Python代码实现
- 补充知识点：如何获取int（long）和 float 的最值
- 完整代码实现
基本概述
- 先看一个应用场景：
- 克鲁斯卡尔算法介绍：
克鲁斯卡尔算法图解
- 还是以上面的公交站图来解释：
- 最小连通子图（最小生成树）：
- 以上图（G4）来说明，假设用数组 R 来保存最小生成树的结果：
- 详细描述：
克鲁斯卡尔算法分析
- 如何判断是否构成回路：
- 解释上面为什么各点的终点是F：
依次将边加入到最小生成树后，形成了一条相连的轨迹（如上图），C 能到到的最后位置就是F，同理D、E也是；对于目前F来说，它的终点就是自身F；所以这几条边都有终点了！
Python代码实现
补充知识点：如何获取int（long）和 float 的最值
- 获取 int 型的最大值
import sys
print(sys.maxsize) # 9223372036854775807
# 说明：这个应该为长整形long的最大值，我们对照下Java获取最大的结果来看
'''
Java中获取基本数据类型的最值的方法: 调用基本数据类型的包装类的MIN_VALUE与MAX_VALUE属性即可
具体如下：
- Integer.MIN_VALUE ⇒ -2147483648
- Integer.MAX_VALUE ⇒ 2147483647
- Long.MIN_VALUE ⇒ -9223372036854775808
- Long.MAX_VALUE ⇒ 9223372036854775807
- Float.MIN_VALUE ⇒ 1.4E-45
- Float.MAX_VALUE ⇒ 3.4028235E38
- Double.MIN_VALUE ⇒ 4.9E-324
- Double.MAX_VALUE ⇒ 1.7976931348623157E308
'''
# 注意 Python3 没有Python2 中的sys.maxint方法
- 获得 float 型的最大值
（1）Python中可以用如下方式表示正、负无穷：
float("inf") # 注意着不是字符串，最大的浮点数就是这个'inf'
print(type(float('inf'))) # <class 'float'>
float("-inf")
（2）利用 inf 做简单加、乘算术运算仍会得到 inf
>>> 1 + float('inf')
inf
>>> 2 * float('inf')
inf
（3）inf 乘以0会得到 not-a-number(NaN)；除了inf外的其他数除以inf，会得到0
>>> 0 * float("inf")
nan
>>> 233 / float('inf')
0.0
>>> float('inf') / float('inf')
nan
- 运用到本次例子：为了更加好看，我们选取float类型的最值来表示
import sys
class GMap(object):
def __init__(self, vertex_data: [], matrix: []): # 传入顶点数组
self.edge_num = 0 # 边的个数
# self.vertex_data = vertex * [0] # 顶点数组
self.vertex_data = vertex_data
# self.matrix = [[0 for row in range(len(vertex_data))] for col in range(len(vertex_data))] # 邻接矩阵
self.matrix = matrix
# 使用 INF 表示两个顶点不能连通
self.inf = float('inf') # 获取浮点型最大值
# self.inf = sys.maxsize # 获取整形最大值
# 统计边
for i in range(len(vertex_data)):
for j in range(len(vertex_data)):
if self.matrix[i][j] != self.inf:
self.edge_num += 1
def print_test(self): # 打印测试
for i in range(len(self.vertex_data)):
for j in range(len(self.vertex_data)):
print(self.matrix[i][j], end=' ')
print()
if __name__ == '__main__':
char_vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
'''用 浮点型 最大值 float('inf') '''
array_matrix = [[0, 12, float('inf'), float('inf'), float('inf'), 16, 14],
[12, 0, 10, float('inf'), float('inf'), 7, float('inf')],
[float('inf'), 10, 0, 3, 5, 6, float('inf')],
[float('inf'), float('inf'), 3, 0, 4, float('inf'), float('inf')],
[float('inf'), float('inf'), 5, 4, 0, 2, 8],
[16, 7, 6, float('inf'), 2, 0, 9],
[14, float('inf'), float('inf'), float('inf'), 8, 9, 0]]
'''用 int 型号的最大值，默认是 int[8]'''
# array_matrix = [[0, 12, sys.maxsize, sys.maxsize, sys.maxsize, 16, 14],
# [12, 0, 10, sys.maxsize, sys.maxsize, 7, sys.maxsize],
# [sys.maxsize, 10, 0, 3, 5, 6, sys.maxsize],
# [sys.maxsize, sys.maxsize, 3, 0, 4, sys.maxsize, sys.maxsize],
# [sys.maxsize, sys.maxsize, 5, 4, 0, 2, 8],
# [16, 7, 6, sys.maxsize, 2, 0, 9],
# [14, sys.maxsize, sys.maxsize, sys.maxsize, 8, 9, 0]]
g = GMap(char_vertex, array_matrix)
g.print_test()
# float 型
'''
0 12 inf inf inf 16 14
12 0 10 inf inf 7 inf
inf 10 0 3 5 6 inf
inf inf 3 0 4 inf inf
inf inf 5 4 0 2 8
16 7 6 inf 2 0 9
14 inf inf inf 8 9 0
'''
# int 型
'''
0 12 9223372036854775807 9223372036854775807 9223372036854775807 16 14
12 0 10 9223372036854775807 9223372036854775807 7 9223372036854775807
9223372036854775807 10 0 3 5 6 9223372036854775807
9223372036854775807 9223372036854775807 3 0 4 9223372036854775807 9223372036854775807
9223372036854775807 9223372036854775807 5 4 0 2 8
16 7 6 9223372036854775807 2 0 9
14 9223372036854775807 9223372036854775807 9223372036854775807 8 9 0
'''
# 为了好看，我们就不用int最大值了，直接用浮点型最大值 float('inf')
完整代码实现
import sys
class GMap(object):
def __init__(self, vertex_data: [], matrix: []): # 传入顶点数组
self.edge_num = 0 # 边的个数
# self.vertex_data = vertex * [0] # 顶点数组
self.vertex_data = vertex_data
# self.matrix = [[0 for row in range(len(vertex_data))] for col in range(len(vertex_data))] # 邻接矩阵
self.matrix = matrix
# 使用 INF 表示两个顶点不能连通
self.inf = float('inf') # 获取浮点型最大值
# self.inf = sys.maxsize # 获取整形最大值
# 统计边的条数
for i in range(len(vertex_data)):
for j in range(i + 1, len(vertex_data)):
if self.matrix[i][j] != self.inf:
self.edge_num += 1
# print(self.edge_num)
def print_test(self): # 打印测试
for i in range(len(self.vertex_data)):
for j in range(len(self.vertex_data)):
print(self.matrix[i][j], end=' ')
print()
# 对边进行排序处理，这里使用一下冒泡排序，其他排序方式都可以
def sort_edges(self, edges: []):
for i in range(len(edges) - 1):
flag = False
for j in range(len(edges) - 1 - i):
if edges[j].weight > edges[j + 1].weight:
edges[j], edges[j + 1] = edges[j + 1], edges[j]
flag = True
if not flag:
break
# 查找传入顶点的位置
def get_position(self, ver_data: str):
"""
:param ver_data: 传入顶点的值，例如:"A""B"
:return: 找到返回ch顶点对应的下标，如果没找到，返回-1
"""
for i in range(len(self.vertex_data)):
if self.vertex_data[i] == ver_data: # 找到，返回顶点下标
return i
return -1 # 找不到，返回-1
# 获取图中的边，放到EData数组中
def get_edges(self):
"""
功能：获取图中边，放到EData[] 数组中，后面需要遍历该数组
是通过matrix 邻接矩阵来获取
EData[] 形式[['A','B',12],['B','F',7],....]
:return:
"""
index = 0
edges = [0] * self.edge_num
for i in range(len(self.vertex_data)):
for j in range(i + 1, len(self.vertex_data)):
if self.matrix[i][j] != self.inf:
edges[index] = EData(self.vertex_data[i], self.vertex_data[j], self.matrix[i][j])
index += 1
return edges
def get_end(self, ends: [], i: int):
"""
获取下标为i的顶点的终点，用来判断两个顶点的终点是否相同，是否会形成回路
:param self:
:param ends: 数组就是记录了各个顶点对应的终点是哪个，ends 数组是在遍历过程中，逐步形成的
:param i: 表示传入的顶点对应的下标
:return: 返回的就是 下标为i的整个顶点对应的终点的下标
"""
while ends[i] != 0:
i = ends[i]
return i
def kruskal(self):
index: int = 0 # 表示最后结果数组的索引
ends: [] = [0] * self.edge_num # 用于保存“已有最小生成树”中的每个顶点在最小生成树中的终点
# 创建结果数组，保存最后的最小生成树
result = [0] * self.edge_num
# 获取图中所有边的集合，一共12条边
edges = self.get_edges()
# 按照边的权值大小进行排序
self.sort_edges(edges)
# 遍历edges数组，将边添加到最小生成树中时，判断是否形成了回路
for i in range(self.edge_num):
# 获取到第i条边的第一个顶点（起点）
p1: int = self.get_position(edges[i].start) # p1=4
# 获取到第i条边的第2个顶点
p2: int = self.get_position(edges[i].end) # p2=5
# 获取p1这个顶点在已有的最小生成树中对应的终点
m: int = self.get_end(ends, p1) # m=4 初始化认为终点就是本身
# 获取p2这个顶点在已有最小生成树种的终点
n: int = self.get_end(ends, p2) # n=5
# 判断是否构成回路
if m != n: # 没有构成回路
ends[m] = n # 设置m 在已有最小生成树的终点
result[index] = edges[i] # 有一条边加入到result数组
index += 1
# 统计并打印“最小生成树”
print('最小生成树为：')
for item in result:
if item == 0:
continue
else:
print("<%s,%s>=%d" % (item.start, item.end, item.weight), end=" | ")
# 创建一个类 EData，它的对象实例就表示一条边
class EData(object):
def __init__(self, start: str, end: str, weight: int):
self.start = start
self.end = end
self.weight = weight
if __name__ == '__main__':
char_vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
'''用 浮点型 最大值 float('inf') '''
array_matrix = [[0, 12, float('inf'), float('inf'), float('inf'), 16, 14],
[12, 0, 10, float('inf'), float('inf'), 7, float('inf')],
[float('inf'), 10, 0, 3, 5, 6, float('inf')],
[float('inf'), float('inf'), 3, 0, 4, float('inf'), float('inf')],
[float('inf'), float('inf'), 5, 4, 0, 2, 8],
[16, 7, 6, float('inf'), 2, 0, 9],
[14, float('inf'), float('inf'), float('inf'), 8, 9, 0]]
'''用 int 型号的最大值，默认是 int[8]'''
# array_matrix = [[0, 12, sys.maxsize, sys.maxsize, sys.maxsize, 16, 14],
# [12, 0, 10, sys.maxsize, sys.maxsize, 7, sys.maxsize],
# [sys.maxsize, 10, 0, 3, 5, 6, sys.maxsize],
# [sys.maxsize, sys.maxsize, 3, 0, 4, sys.maxsize, sys.maxsize],
# [sys.maxsize, sys.maxsize, 5, 4, 0, 2, 8],
# [16, 7, 6, sys.maxsize, 2, 0, 9],
# [14, sys.maxsize, sys.maxsize, sys.maxsize, 8, 9, 0]]
g = GMap(char_vertex, array_matrix)
print('图的邻接矩阵为:')
g.print_test()
'''测试一下图的各条边的信息'''
print('图原先的边信息:')
for item in g.get_edges():
print(item.start, item.end, item.weight, end=" | ")
print()
print('原先总共有：%d 条边' % g.edge_num)
'''测试一下排序'''
# edges_array = g.get_edges()
# g.sort_edges(edges_array)
# for item in edges_array:
# print(item.start, item.end, item.weight, end=" | ")
'''获取最小生成树'''
g.kruskal()
'''输出结果：
图的邻接矩阵为:
0 12 inf inf inf 16 14
12 0 10 inf inf 7 inf
inf 10 0 3 5 6 inf
inf inf 3 0 4 inf inf
inf inf 5 4 0 2 8
16 7 6 inf 2 0 9
14 inf inf inf 8 9 0
图原先的边信息:
A B 12 | A F 16 | A G 14 | B C 10 | B F 7 | C D 3 | C E 5 | C F 6 | D E 4 | E F 2 | E G 8 | F G 9 |
原先总共有：12 条边
最小生成树为：
<E,F>=2 | <C,D>=3 | <D,E>=4 | <B,F>=7 | <E,G>=8 | <A,B>=12 |
'''
