# 树的数据结构、最小支撑树（上） -- 潘登同学的图论笔记
@
无向树
定义
树是连通且不含有任何简单回路的无向图
树中度数为1的顶点称为叶子，度数大于1的顶点称为分支点；
注：
- 一阶简单图k也是树
- 树必定不包含重边和自环，树一定是简单图
既然树是简单图，那么直接把图的数据结构拿过来用就行
二叉树
重点要介绍的是二叉树，二叉树具有很多优良的性质，在排序、语句联想、表达式处理等很多方面很有作用；
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分
先是树的节点TreeNode
那么实现TreeNode需要一些什么属性和方法呢?
- 节点的名称
- 节点上的值、节点的左右子节点是什么、节点的父节点
- 查看左节点、右节点与父节点对象、判断是否有左右节点、父节点
- 显示设置(如果在命令行把TreeNode输入, 显示的东西, 如果不写的话, 就会显示对象地址)
- 可迭代函数
class TreeNode():
def __init__(self, key, val, left=None, right=None, parent=None):
self.key = key
self.payload = val
self.left = left
self.right = right
self.parent = parent
def hasleft(self):
return self.left
def hasright(self):
return self.right
def isleft(self):
return self.parent and self.parent.left == self
def isright(self):
return self.parent and self.parent.right == self
def isroot(self):
return not self.parent
def isLeaf(self):
return not (self.left or self.right)
def hasAnyChildren(self):
return self.left or self.right
def hasBothChildren(self):
return self.left and self.right
def replaceNodeData(self, key, val, left, right):
self.key = key
self.payload = val
self.left = left
self.right = right
if self.hasleft():
self.left.parent = self
if self.hasright():
self.right.parent = self
def __str__(self):
return '数据是:{}'.format(self.payload)
def __iter__(self):
if self:
if self.hasleft():
# 递归调用
for elem in self.left:
yield elem
yield self.key # 把根节点放在中间，最终的输出就是从小到大
if self.hasright():
# 递归调用
for elem in self.right:
yield elem
实现完节点了,接下来就是实现二叉树了;
二叉树有这样的性质：
对于一个节点来说，父节点大于左节点、小于右节点
那么树的数据结构都包括什么呢?
- 树中节点的个数、根节点对象
- 查看树的节点个数
- 向树中加入新节点的函数
- 通过节点名称查看节点对象
- 删除节点的函数(最繁杂)
import TreeNode
class BinaryNodeTree():
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def __iter__(self):
return self.root.__iter__()
def put(self, key, val):
if self.root:
self._put(key, val, self.root)
else:
self.root = TreeNode(key, val)
self.size += 1
def _put(self, key, val, currentNode):
if key < currentNode.key:
if currentNode.hasleft():
# 如果有左节点就递归调用自身
self._put(key, val, currentNode.left)
else:
currentNode.left = TreeNode(key, val, parent=currentNode)
else:
if currentNode.hasright():
# 如果有右节点就递归调用自身
self._put(key, val, currentNode.right)
else:
currentNode.right = TreeNode(key, val, parent=currentNode)
def __setitem__(self, key, val):
# 索引赋值
self.put(key, val)
def get(self, key):
'''
Returns
-------
TreeNode.payload 节点属性.
'''
if self.root:
res = self._get(key, self.root)
if res:
return res.payload
else:
return None
def _get(self, key, currentNode):
'''
Parameters
----------
key : TYPE
currentNode : TYPE
TreeNode节点对象.
Returns
-------
TreeNode 节点对象.
'''
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key, currentNode.left)
else:
return self._get(key, currentNode.right)
def __getitem__(self, key):
# 索引取值
return self.get(key)
def __contains__(self, key):
# 判断key是否在树内(用in来判断)
if self._get(key, self.root):
return True
else:
return False
def delete(self, key):
if self.size > 1:
nodeToRemove = self._get(key, self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size -= 1
else:
raise KeyError('Error, key not in Tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size -= 1
else:
raise KeyError('Error, key not in Tree')
def __delitem__(self, key):
# del方法
self.delete(key)
def remove(self, nodeToRemove):
# 删除节点有三种情况
# 该节点没有子节点
if nodeToRemove.isLeaf():
if nodeToRemove == nodeToRemove.parent.left:
# 如果这个节点是其父节点的左子节点
nodeToRemove.parent.left = None
else:
# 如果这个节点是其父节点的右子节点
nodeToRemove.parent.right = None
# 该节点有一个子节点，把该子节点上移
elif nodeToRemove.hasAnyChildren() and not nodeToRemove.hasBothChildren():
# 如果被删的那个节点只有左子节点
if nodeToRemove.hasleft():
# 且他是父节点的左子节点
if nodeToRemove.isleft():
# 将该节点的父节点的左节点设为该节点的左节点
nodeToRemove.parent.left = nodeToRemove.left
# 将该节点的父节点设为该节点左节点的父节点
nodeToRemove.left.parent = nodeToRemove.parent
# 且他是父节点的右子节点
elif nodeToRemove.isright():
# 将该节点的父节点的右节点设为该节点的左节点
nodeToRemove.parent.right = nodeToRemove.left
# 将该节点的父节点设为该节点左节点的父节点
nodeToRemove.left.parent = nodeToRemove.parent
else:
# 该节点是根节点(那就把该节点的左节点变成根节点)
nodeToRemove.replaceNodeData(nodeToRemove.left.key,
nodeToRemove.left.value,
nodeToRemove.left.left,
nodeToRemove.left.right)
# 如果被删的那个节点只有右子节点
elif nodeToRemove.hasright():
# 且他是父节点的左子节点
if nodeToRemove.isleft():
# 将该节点的父节点的左节点设为该节点的右节点
nodeToRemove.parent.left = nodeToRemove.right
# 将该节点的父节点设为该节点右节点的父节点
nodeToRemove.right.parent = nodeToRemove.parent
# 且他是父节点的右子节点
elif nodeToRemove.isright():
# 将该节点的父节点的右节点设为该节点的右节点
nodeToRemove.parent.right = nodeToRemove.right
# 将该节点的父节点设为该节点右节点的父节点
nodeToRemove.right.parent = nodeToRemove.parent
else:
# 该节点是根节点(那就把该节点的右节点变成根节点)
nodeToRemove.replaceNodeData(nodeToRemove.right.key,
nodeToRemove.right.payload,
nodeToRemove.right.left,
nodeToRemove.right.right)
# 该节点有两个子节点,找到比该节点大一点点的那个节点来替代（称为后继）
# 而根据二叉查找树的性质，这个后继出现在该节点的右节点的最左下节点
elif nodeToRemove.hasBothChildren():
currentnode = nodeToRemove.right
while currentnode.left:
# 一直往左找，直到其左节点为None
currentnode = currentnode.left
# 如果找到的这个后继是叶节点，就直接把他换到nodeToRemove的位置
if currentnode.isLeaf():
# 如果后继节点是其父节点的左子节点
if currentnode.isleft():
currentnode.parent.left = None
else: # 如果该节点是其父节点的右子节点
currentnode.parent.right = None
# 把该节点的父节点设为后继节点的父节点
currentnode.parent = nodeToRemove.parent
nodeToRemove.replaceNodeData(currentnode.key,
currentnode.payload,
nodeToRemove.left,
nodeToRemove.right)
# 如果找的的这个后继节点不是叶节点(有且只有右节点)
# 那这个后继节点的右子节点一定会小于其父节点，就直接把他的右节点接到其父节点的左节点上
else:
# 把后继节点的父节点设为其后继节点的右节点的父节点
currentnode.right.parent = currentnode.parent
# 如果该节点是父节点的左节点
if currentnode.isleft():
# 把后继节点父节点的左节点设为后继节点的右节点
currentnode.parent.right = currentnode.right
elif currentnode.isright():
# 把后继节点父节点的右节点设为后继节点的右节点
currentnode.parent.right = currentnode.right
# 把该节点的父节点设为后继节点的父节点
currentnode.parent = nodeToRemove.parent
nodeToRemove.replaceNodeData(currentnode.key,
currentnode.payload,
nodeToRemove.left,
nodeToRemove.right)
森林
定义
不含任何简单回路的图（不一定连通），其实就是很多个树；故称森林
依然用图的数据结构就行....
无向树理论部分
定理
设n阶无向连通图G的边数满足$m=n-1$,则图G中至少存在两个度数为1的顶点
证明： 因为G是连通的，从而各个顶点的度数都大于零，设图G有t个顶点度数为1，其余顶点度数至少为2，则 $$2m=\sum_{i=1}deg(v_i) \geq t + 2(n-t)$$ 由$m=n-1$得，$t\geq 2$
无向树的等价定义
设$T$是$(n,m)$-无向图，则下述命题等价
- a)$T$是数，即$T$连通且不存在简单回路
- b)$T$的每一对相异顶点之间存在唯一的简单道路
- c)$T$不存在简单回路，但在任何两个不相邻的顶点之间加一条新边后，得到的图中存在简单回路（也称为‘极大无圈’）
- d)$T$连通且$m=n-1$
- e)$T$连通，但是删去任何一边后便不再连通，即$T$中每一条边都是桥（也称为‘极小连通’）
- f)$T$不存在简单回路且$m=n-1$
接下来是一大段的证明
证明
- a)=>b) 对阶数n进行归纳
当$n=1$时，$T$不存在相异顶点，b）显然成立
设$n=k$时，b）成立，当$n=k+1$时，已知$T$连通且不含简单回路，则存在度数为1的顶点，记之为v，并设uv为悬挂边（u是在树原有节点外新增的一个节点）；
对于$T-{v}$中任意两个相异顶点$W_1和W_2$,$W_1到W_2$的任一条简单道路都不会经过uv，所以新增的边uv对$W_1、W_2$之间的唯一道路无影响
对于$T-{v}$中任意一顶点$W$,$W到u$的道路唯一，故$W到v$的道路也唯一，故对$T$中任意两个顶点，道路都唯一
通俗的解释就是，加入在广东与辽宁往返的只有一种方式，在青海与辽宁往返也只有一种方式，那么从广东到青海就必然只有一种方式，要么就是直接到青海、要么就是通过辽宁间接到青海，不可能有两种方式，否则广东到辽宁就不止有一种方式了；
b)=>c) 对阶数n进行归纳
当$n=1$时，$T$只有孤立顶点，c）显然成立
设$n=k$时，c）成立，当$n=k+1$时，首先证明$T$中不存在简单回路，如果$T$中存在简单回路，$v_1,v_2,\ldots,v_k$,则从$v_2到v_1$存在两条不同的道路，与b）矛盾；
而对于任意两个不相邻的顶点$u和v$,由条件b），存在u到v的简单道路，则新增边$uv$后便得到简单回路；
c)=>d) 对阶数n进行归纳
当$n=1$时，$T$只有孤立顶点，d）显然成立
设$n=k$时，d）成立，当$n=k+1$时,首先证明$T$是连通的，如果$T$不是连通的，那么可以选择连通分支$Y_1，Y_2$，连接两连通分支后，将无法形成回路，故$T$是连通的
由于$T$是连通的且不包含任何回路，那一定会存在顶点度数为1的顶点，记之为v，并设$uv$为悬挂边（u是在树原有节点外新增的一个节点），则由归纳假设$T-{v}$顶点数$n'$与边数$m'$满足$m'=n'-1$,故T的顶点数n与边数m的关系为$m=n-1$
d)=>e) 对阶数n进行归纳
当$n=1$时，$T$只有孤立顶点，e）显然成立
设$n=k$时，e）成立，当$n=k+1$时,$T$存在度数为1的顶点，记之为v，并设$uv$为悬挂边（u是在树原有节点外新增的一个节点），则由归纳假设$T-{v}$中每一条边都是桥，于是$T$中每一条边都是桥
e)=>f) 对阶数n进行归纳
当$n=1$时，$T$只有孤立顶点，f）显然成立
设$n=k$时，f）成立，当$n=k+1$时,首先证明$T$不包含简单回路，如果存在简单回路，那么删掉回路中的任意一段也不能使图不连通；
由于$T$连通且不包含任何回路，$T$中存在度数为1的顶点，记之为v，并设$uv$为悬挂边（u是在树原有节点外新增的一个节点），则由归纳假设$T-{v}$顶点数$n'$与边数$m'$满足$m'=n'-1$，故$T$的顶点数n与边数m满足$m=m'+1=n'-1+1=n-1$
f)=>a) 对阶数n进行归纳
当$n=1$时，$T$只有孤立顶点，a）显然成立
设$n=k$时，a）成立，当$n=k+1$时,$T$中存在度数小于2的顶点
1.若$T$中存在孤立顶点v, 若考虑$T-{v}$任何一个边uw，$T-{v}-uw$的顶点数$n'$与边数$m'$满足$m'=n'-1$,由归纳假设$T-{v}-uw$连通，因此存在u到w的道路，因此存在u到w的道路，又因为uw是一条边，故$T$中存在回路，与f)相矛盾，所以$T$中不存在孤立顶点v
2.$T$中不存在孤立顶点，故$T$中必然存在度数为1的顶点，记之为v，并设$uv$为悬挂边，由归纳假设，$T-{v}$连通，因此$T$也连通；
上面的表述有这样的结论 设$T$是无向图，则满足下述3个条件中至少两个时$T$是树
- $T$连通
- $T$不存在简单回路
- $m=n-1$
推论
- 任何非平凡树至少有2个叶子节点
- 对于任何无向图，若图中不存在简单回路，则$m=n-1$（反过来不成立）
支撑树
定义
若连通图G的支撑子图$T$是一棵树，则称$T$为G的生成树或支撑树，记为$T_G$
定理
无向图G具有支撑树，当且仅当G是连通图
证明：
- (必要性)因为树是连通的，所以如果无向图G具有子树作为支撑子图，则G必定也是连通的
- (充分性)若G中无回路，G本身就是支撑树。如果G中存在回路C，则去掉C中任意一条边，得到图$G_1$,$G_1$仍是连通的（重复该步骤，直到没有回路为止）
最小支撑树
定义
设$(G,W)$是无向连通赋权图，$T$是$G$的一颗支撑树，$T$的各边权值之和称为$T$的权，记为$W(T)$;$G$中所有支撑树中权最小的称为$G$的最小支撑树（最小生成树）
构造最小生成树的算法
Prim算法
输入： 赋权简单图$G$
输出： $G$的最小支撑树 $T=(V_T, E_T)$
算法思路：维护两个集合$V_T和E_T$,$E_T$中为所有已经确定属于最小支撑树的边；$V_T$保存$E_T$中所有边的端点，每一步都将距离$V_T$‘最近’但不属于$V_T$的顶点移入$V_T$
- 1.$V_T \leftarrow {V}$, 其中v为任一顶点，$E_T \leftarrow \empty$
- 2.若$V_T = V$,则输出$T=(V_T,E_T)$
- 3.1.否则，在集合$E$选取权值最小的边$uv$,其中$u\in V_T且v\in V-V_T$
- 3.2.$V_T\leftarrow V_T\cup {v},E_T \leftarrow E_T\cup {uv}$,返回2
算法实现
#%% Prim算法
from Graph import Graph
import sys
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
class Solution:
def createGraph(self, g_dict=None, g_matrix=None):
'''
input: g_dict(邻接表) or g_matrix(邻接矩阵)
output: directgraph(有向图)
'''
graph = Graph()
if g_dict:
for from_key in g_dict:
for to_key in g_dict[from_key]:
# 这里就是注意提到的f跟着c走所以原图的c是[f,c],这个很重要
graph.addEdge(from_key, to_key[0], to_key[1])
elif g_matrix.any():
# 先给顶点起个名字
name = [str(i) for i in range(1, len(g_matrix)+1)]
for i, from_key in enumerate(name):
for j, to_key in enumerate(name):
if g_matrix[i][j] != float('inf'):
graph.addEdge(from_key, to_key, g_matrix[i][j])
return graph
def Prim(self, graph):
V = [i for i in graph]
Vt = [V[0]]
Et = []
while set(Vt) != set(V):
temp_v = list(set(V) - set(Vt))
v = None
uv = sys.maxsize
for i in Vt:
for j in temp_v:
if j in i.getConnections() and i.getWeight(j) < uv:
v = j
uv = i.getWeight(j)
Vt.append(v)
Et.append(uv)
print('最小生成树是：','总长度:', sum(Et))
for i,j in zip(Vt, Et):
print(f'{i.getId()}--', j, '->', end='\t')
print(Vt[-1].getId())
return Vt,Et
def draw(self, graph, Vt):
'''
Parameters
----------
graph : graph
原图对象.
Vt : list
prim算法得出的.
Returns
-------
plt.
'''
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
G = nx.DiGraph()
GT = nx.DiGraph()
for i in graph:
for j in graph:
if i != j and j in i.getConnections():
G.add_edge(i.getId(), j.getId(), weight=i.getWeight(j))
if Vt.index(i)-Vt.index(j) == -1:
GT.add_edge(i.getId(), j.getId(), weight=i.getWeight(j))
pos = nx.spring_layout(G,seed=41)
options = {
"font_size": 20,
"node_size": 200,
"node_color": "green",
"edgecolors": "white",
"edge_color": 'blue',
"font_color": 'red',
"linewidths": 2,
"width": 2,
'alpha':0.8,
'with_labels':True
}
plt.figure(figsize=(12,6))
plt.subplot(121)
nx.draw(G, pos, **options)
plt.title('原图')
plt.subplot(122)
nx.draw(GT, pos, **options)
plt.title('最小支撑树')
plt.show()
if __name__ == '__main__':
inf = float('inf')
a = np.array([[0, 1, 12, inf, inf, inf],
[inf, 0, 9, 3, inf, inf],
[inf, inf, 0, inf, 5, inf],
[inf, inf, 4, 0, 13, 15],
[inf, inf, inf, inf, 0, 4],
[inf, inf, inf, inf, inf, 0]])
s = Solution()
graph = s.createGraph(g_matrix=a)
Vt, Et = s.Prim(graph)
s.draw(graph, Vt)
- 结果如下：
Kruskal算法
输入： 赋权简单图$G$
输出： $G$的最小支撑树 $T=(V_T, E_T)$
算法思路：每一步都选择权值最小而且不与已选边构成回路的边，直到边数等于顶点数-1为止
- 1.把图G的边权值按不减的顺序排列成一个序列$e_1,e_2,\ldots,e_m$,$E'\leftarrow E, E_T \leftarrow \empty$
- 2.若$|E_T|=|V|-1$，则输出$T=(V,E_T)$
- 3.1.否则，假设e是$E'$中权值最小的边，$E'\leftarrow E'-{e}$
- 3.2.如果$e与E_T$中的边构不构成回路，则$E_T\leftarrow E_T\cup{e}$,返回2
注意 这里的判断是否构成回路，需要采用DFS或者BFS，所以算法没有Prim这么简洁;而我采用BFS，因为BFS好理解一些
算法实现
#%% Kruskal算法
from Vertex import Vertex
from Graph import Graph
import sys
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
class New_Vertex(Vertex): # 某一个具体问题的数据结构需要继承原有数据结构
def __init__(self, key):
super().__init__(key)
self.color = 'white' # 新增类属性(用于记录节点是否被走过)
self.pred = None # 顶点的前驱 BFS需要
# 新增类方法, 设置节点颜色
def setColor(self, color):
self.color = color
# 新增类方法, 查看节点颜色
def getColor(self):
return self.color
# 新增类方法, 设置节点前驱
def setPred(self, p):
self.pred = p
# 新增类方法, 查看节点前驱
def getPred(self): # 这个前驱节点主要用于追溯，是记录离起始节点最短路径上
return self.pred # 该节点的前一个节点是谁
def getConnections_number(self): # 查看相邻顶点的个数，用于后面找出最小支撑树
return len(self.connectedTo)
class New_Graph(Graph): # 继承Graph对象
def __init__(self):
super().__init__()
# 重载方法 因为原先Graph中新增节点用的是Vertex节点,但现在是用New_Vertex
def addVertex(self, key): # 增加节点
'''
input: Vertex key (str)
return: Vertex object
'''
if key in self.vertList:
return
self.numVertices = self.numVertices + 1
newVertex = New_Vertex(key) # 创建新节点
self.vertList[key] = newVertex
return newVertex
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, items): # 往队列加入数据
self.items.insert(0, items)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
class Stack(): # 这个栈是后进先出 将列表的尾部设置为栈顶
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
return self.stack.pop()
def peek(self):
if self.isEmpty():
return None
else:
return self.stack[-1]
def isEmpty(self):
return self.stack == []
def size(self):
return len(self.stack)
def __len__(self):
return self.size()
def __iter__(self):
return iter(self.stack)
class Solution:
def createGraph(self, g_dict=None, g_matrix=None):
'''
input: g_dict(邻接表) or g_matrix(邻接矩阵)
output: directgraph(有向图)
'''
graph = New_Graph()
if g_dict:
for from_key in g_dict:
for to_key in g_dict[from_key]:
# 这里就是注意提到的f跟着c走所以原图的c是[f,c],这个很重要
graph.addEdge(from_key, to_key[0], to_key[1])
elif g_matrix.any():
# 先给顶点起个名字
name = [str(i) for i in range(1, len(g_matrix)+1)]
for i, from_key in enumerate(name):
for j, to_key in enumerate(name):
if g_matrix[i][j] != float('inf'):
graph.addEdge(from_key, to_key, g_matrix[i][j])
return graph
def Kruskal(self, graph):
V = []
E = []
Vt = New_Graph()
for i in graph:
Vt.addVertex(i.getId()) # 先把节点加入新图中
for j in graph:
if i != j and j in i.getConnections():
V.append([i, j])
E.append(i.getWeight(j))
edge_number = 0
while edge_number != len(graph) - 1:
e = sys.maxsize
v = None
# 找出最小的边
for i,k in enumerate(E):
if k < e:
v = V[i]
e = k
E.remove(e)
V.remove(v)
# 如果不可达
if not self.arrive(Vt, Vt.getVertex(v[0].getId()), Vt.getVertex(v[1].getId())):
Vt.addEdge(v[0].getId(), v[1].getId(), e)
edge_number += 1
Tree_v = Stack()
for i in Vt:
if i.getConnections_number() == 0:
Tree_v.push(i)
break
while len(Tree_v) != 2*len(Vt)-1:
end = Tree_v.peek()
for i in Vt:
if end in i.getConnections():
cost = i.getWeight(end)
Tree_v.push(cost)
Tree_v.push(i)
print('最小生成树是：','总长度:', sum([i for i in Tree_v if isinstance (i,float)]))
while len(Tree_v) != 1:
print(f'{Tree_v.pop().getId()}--', f'{Tree_v.pop()}->', end='')
print(f'{Tree_v.pop().getId()}')
return Vt
def arrive(self, graph, start, end):
'''
Parameters
----------
graph : New_Graph对象
DESCRIPTION.
start : Vertex对象
起始顶点.
end : Vertex对象
终止节点.
Returns
-------
: bool
True or False.
'''
for i in graph:
i.setColor('white')
start.setPred(None) # 前驱节点
vertQueue = Queue() # 队列
vertQueue.enqueue(start) # 把起始节点加入图中
while vertQueue.size() > 0: # 当搜索完所有节点时，队列会变成空的
currentVert = vertQueue.dequeue() # 取队首作为当前顶点
for nbr in currentVert.getConnections(): # 遍历临接顶点
if (nbr.getColor() == 'white'): # 当邻接顶点是白色的时候
nbr.setColor('gray')
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
currentVert.setColor('balck')
return not (end.getColor()=='white')
def draw(self, graph, Vt):
'''
Parameters
----------
graph : graph
原图对象.
Vt : graph
Kruskal算法得出的.
Returns
-------
plt.
'''
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
G = nx.DiGraph()
GT = nx.DiGraph()
for i in graph:
for j in graph:
if i != j and j in i.getConnections():
G.add_edge(i.getId(), j.getId(), weight=i.getWeight(j))
for i in Vt:
for j in Vt:
if i != j and j in i.getConnections():
GT.add_edge(i.getId(), j.getId(), weight=i.getWeight(j))
pos = nx.spring_layout(G,seed=41)
options = {
"font_size": 20,
"node_size": 200,
"node_color": "green",
"edgecolors": "white",
"edge_color": 'blue',
"font_color": 'red',
"linewidths": 2,
"width": 2,
'alpha':0.8,
'with_labels':True
}
plt.figure(figsize=(12,6))
plt.subplot(121)
nx.draw(G, pos, **options)
plt.title('原图')
plt.subplot(122)
nx.draw(GT, pos, **options)
plt.title('最小支撑树')
plt.show()
if __name__ == '__main__':
inf = float('inf')
a = np.array([[0, 1, 12, inf, inf, inf],
[inf, 0, 9, 3, inf, inf],
[inf, inf, 0, inf, 5, inf],
[inf, inf, 4, 0, 13, 15],
[inf, inf, inf, inf, 0, 4],
[inf, inf, inf, inf, inf, 0]])
s = Solution()
graph = s.createGraph(g_matrix=a)
Vt = s.Kruskal(graph)
s.draw(graph, Vt)
- 结果如下：
看到了与上面的Prim算法的结果一致，但是显然算法复杂了很多，究其原因是因为我们的图的数据结构主体是顶点，边权重只是作为节点的一个属性存在，所以我们不能直接操作边、这就导致了需要一个额外的空间去一边储存节点、一边判断边，最后还需要栈来控制道路输出，一旦图的数据结构修改之后，这个算法就能简化下来，感兴趣的童鞋可以试试....
因为这个算法难度属实很高，我分多几章来写，理解算法除了理解算法的步骤，对数据结构的处理也至关重要，树的数据结构、最小支撑树（上）就是这么多了，继续学习下一章吧！
