最近在研究使用序列模型来实现图像任务的深度学习，发现将图像数据转换成序列数据总会存在空间位置信息的损失，而图结构能够提供一个很强大的表征方式，因此希望研究一下如何将其进行进一步的应用。
为了深刻的理解图结构，这里从一个最简单的用最小生成树表示无向图的例子进行切入。
无向图（Undirected Graph）是一种图结构，在这种图中，边（Edge）没有方向性。换句话说，如果存在一条边连接两个顶点（Vertex），则可以从任意一个顶点到达另一个顶点。无向图通常表示为 ( G = (V, E) )，其中：
在无向图中，边 ( (u, v) ) 表示顶点 ( u ) 和顶点 ( v ) 之间存在一条边，且 ( (u, v) ) 和 ( (v, u) ) 是等价的。
示例
考虑一个无向图 ( G ) ，其顶点集合 ( V = {1, 2, 3, 4} ) ，边集合 ( E = {(1, 2), (2, 3), (3, 4), (4, 1)} )。这个图可以表示为：
1 -- 2
| |
4 -- 3
无向图的特性
无向图在很多领域都有应用，例如网络拓扑、社交网络分析、生物网络等。
最小生成树（Minimum Spanning Tree，简称 MST）是无向加权图中的一个子图，它包含图中的所有顶点，并且使得所有边的权重之和最小。换句话说，最小生成树是连接图中所有顶点的权重最小的无环子图。
特性
应用
最小生成树在许多实际问题中有重要应用，例如：
常见算法
对于一个具有n个顶点的无向图，最多有$\frac{n(n-1)}{2}条边$ 举一个具有6个顶点的无向图为例
(0)-1-(1)
| \ | \
5 2 3 3
| \ | \
(2) (3)-1-(5)
\ | /
3 2 4
\ | /
(4)
这里设置了9条边,将它表示为列表，并且按照边的权重从小到大排序
[
# (顶点1,顶点2,边权重)
(0, 1, 1),
(3, 5, 1),
(0, 3, 2),
(3, 4, 2),
(1, 5, 3),
(1, 3, 3),
(2, 4, 3),
(4, 5, 4),
(0, 2, 5),
]
利用迭代来找出最小的连通图。
第一轮迭代
选择最小边
对于连通分量0，最小的边是(0, 1, 1)
对于连通分量1，最小的边是(0, 1, 1)
对于连通分量2，最小的边是(2, 4, 3)
对于连通分量3，最小的边是(3, 5, 1)
对于连通分量4，最小的边是(3, 4, 2)
对于连通分量5，最小的边是(3, 5, 1)
合并连通分量
选择(0, 1, 1)合并连通分量0和1。
(0)-1-(1)
(2) (3) (5)
(4)
选择(3, 5, 1)合并连通分量3和5。
(0)-1-(1)
(2) (3)-1-(5)
(4)
选择(3, 4, 2)合并连通分量3和4。
(0)-1-(1)
(2) (3)-1-(5)
|
2
|
(4)
选择(2, 4, 3)合并连通分量2和4。
(0)-1-(1)
(2) (3)-1-(5)
\ |
3 2
\ |
(4)
更新并查集
第二轮迭代
选择最小边
对于连通分量0-1，最小的边是(0, 3, 2)
对于连通分量2-3-4-5，最小的边是(0, 3, 2)
选择(0, 3, 2)合并连通分量0和3。
(0)-1-(1)
\
2
\
(2) (3)-1-(5)
\ |
3 2
\ |
(4)
更新并查集，发现所有的顶点都已连通，算法结束
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def contractive_boruvka(edges, n):
uf = UnionFind(n)
mst_edges = []
mst_weight = 0
iteration = 0
while len(mst_edges) < n - 1:
iteration += 1
print(f"Iteration {iteration}:")
# 初始化每个组件的最小边
min_edge = [-1] * n
for index, (u, v, weight) in enumerate(edges):
root_u = uf.find(u)
root_v = uf.find(v)
if root_u != root_v:
if min_edge[root_u] == -1 or edges[min_edge[root_u]][2] > weight:
min_edge[root_u] = index
if min_edge[root_v] == -1 or edges[min_edge[root_v]][2] > weight:
min_edge[root_v] = index
# 收缩每个组件的最小边
for edge_index in min_edge:
if edge_index != -1:
u, v, weight = edges[edge_index]
root_u = uf.find(u)
root_v = uf.find(v)
if root_u != root_v:
uf.union(u, v)
mst_edges.append((u, v, weight))
mst_weight += weight
print(f" Connecting {u} - {v} with weight {weight}")
print(f" MST so far: {mst_edges}")
print()
return mst_edges, mst_weight
# 示例使用
edges = [
# (顶点1,顶点2,边权重)
(0, 1, 1),
(3, 5, 1),
(0, 3, 2),
(3, 4, 2),
(1, 5, 3),
(1, 3, 3),
(2, 4, 3),
(4, 5, 4),
(0, 2, 5),
]
n = 6
mst_edges, mst_weight = contractive_boruvka(edges, n)
print("Final MST edges:", mst_edges)
print("Total weight of MST:", mst_weight)