"""
基本思想:
从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相连接的边中选取一条最短(权值最小)的边，把这条边以及相邻的
节点加入到树中，此时就是一棵有两个节点的树了；然后从这棵树中的相邻的边中选取一条权值最小的边加入及节点加入到树中；
以此类推
简单算法：
随意选取一个节点当做树开始的节点，然后遍历树的节点，选择权值最小的边的相邻节点，先判断是否已经在树中，如果不在，则
加入到树中；循环以上操作
下面的例子中，复杂度可能会有点高
注意：
连通图
树，不限于二叉树
"""
class Node(object):
def __init__(self, _key):
self.key = _key
def __str__(self):
return self.key
__repr__ = __str__
class Edge(object):
def __init__(self, _start, _end, _value):
self.start = _start
self.end = _end
self.value = _value
def __str__(self):
return '{}--{}--{}'.format(self.start, self.end, self.value)
__repr__ = __str__
class Main(object):
def __init__(self):
self.all_nodes = []
self.all_edges = []
self.tree_nodes = []
self.tree_edges = []
self.init_data()
def init_data(self):
"""
手动初始化数据
"""
# 节点
v1 = Node('v1')
v2 = Node('v2')
v3 = Node('v3')
v4 = Node('v4')
v5 = Node('v5')
v6 = Node('v6')
self.all_nodes.extend([v1, v2, v3, v4, v5, v6])
# 边
# 无向图，每两个节点间需要创建来回两条边
self.all_edges.extend([
Edge(v1, v2, 6), Edge(v2, v1, 6),
Edge(v1, v3, 1), Edge(v3, v1, 1),
Edge(v1, v4, 5), Edge(v4, v1, 5),
Edge(v2, v5, 3), Edge(v5, v2, 3),
Edge(v2, v3, 5), Edge(v3, v2, 5),
Edge(v3, v4, 5), Edge(v4, v3, 5),
Edge(v3, v5, 6), Edge(v5, v3, 6),
Edge(v3, v6, 4), Edge(v6, v3, 4),
Edge(v4, v6, 2), Edge(v6, v4, 2),
Edge(v5, v6, 6), Edge(v6, v5, 6)
])
def get_end_nodes_by_start_node(self, start):
"""
得到所有与start连接的节点
"""
nodes = []
# 从边的集合中，根据一个节点，得到相连的节点的列表
for edge in self.all_edges:
if edge.start == start:
nodes.append(edge.end)
return nodes
def get_edge_with_start_and_end(self, start, end):
"""
根据start和end节点，得到边的信息
"""
for edge in self.all_edges:
if edge.start == start and edge.end == end:
return edge
def get_min_node_from_tree_nodes(self):
min_value = 999999
min_node = None
min_edge = None
print('-' * 50)
print('****************************tree_nodes = {}'.format(self.tree_nodes))
# 遍历已经加入到tree_nodes中的节点（已经构成树的节点）
for tree_node in self.tree_nodes:
# 得到树中每一个节点的的相邻节点
for end_node in self.get_end_nodes_by_start_node(tree_node):
# 得到两个节点组成的边
edge = self.get_edge_with_start_and_end(tree_node, end_node)
print(f'start={tree_node},end={end_node},edge={edge}')
# 判断边的value与min_value的大小比较
# 以及判断end节点是否已经在树中了，避免出现环
if edge.value <= min_value and end_node not in self.tree_nodes:
min_value = edge.value
min_node = end_node
min_edge = edge
# 返回end节点和组成的边
return min_node, min_edge
def create_tree(self):
# 从节点的第一个位置开始
self.tree_nodes.append(self.all_nodes.pop(0))
# 判断是否所有的节点都已经在最小生成树中
while self.all_nodes:
min_node, min_edge = self.get_min_node_from_tree_nodes()
# 打印用
self.tree_edges.append(min_edge)
# 将节点加入到树中
self.tree_nodes.append(min_node)
# 从all_nodes中移除掉，表明这个节点已经使用了
self.all_nodes.remove(min_node)
def print_tree(self):
# 节点添加到树中的顺序
print(self.tree_nodes)
# 树中边的数据
print(self.tree_edges)
if __name__ == '__main__':
m = Main()
m.create_tree()
m.print_tree()
网友评论