最小生成树 Kruskal算法及聚类场景应用
最小生成树 Kruskal算法及聚类场景应用
Kruskal算法是解决最小生成树问题的经典算法之一，其核心思想是通过逐步选择权值最小的边来构建最小生成树，同时确保不会形成环。本文将详细介绍Kruskal算法的原理、实现步骤和复杂度分析，并结合实际应用场景（轨迹聚类）进行说明。
1 前置基础
1.1 无向图
图论中的一种基本概念。它由顶点（Vertices）和边（Edges）组成，其中边没有方向性，即一条边连接两个顶点时，表示这两个顶点是相互连接的，彼此之间的连接没有方向。
顶点：图中的每个节点称为顶点（Vertex），用集合
V
表示，
V = {v1, v2, v3, ..., vn}
，其中
n
是顶点的数量。边：顶点之间的连接称为边（Edge），用集合
E
表示。无向图的边没有方向性，即边
(u, v)
和边
(v, u)
表示的是同一条边。
1.2 无向图中的环
在无向图中，一个环（Cycle）是一条起点和终点相同的路径，并且在路径中除了起点和终点，其他所有的顶点和边都只能经过一次。
- 举例：设顶点集
V = {A, B, C, D}
，如果存在边集
E = {(A, B), (B, C), (C, D), (D, A)}
，这就形成了一个环
A-B-C-D-A
，因为从顶点
A
开始，经过若干边后最终又回到了
A
，并且没有重复经过任何边或中间顶点。
1.3 连通分量
在一个无向图中，如果两个顶点之间存在至少一条路径能够连接这两个顶点，则称这两个顶点是连通的。如果一组顶点是两两连通的，并且它们包含的所有边和顶点构成一个子图，这个子图就是图的一个连通分量。
无向图的连通分量：在无向图中，连通分量是指图中最大的连通子集，每个连通分量中的任意两个顶点是连通的，但这个连通分量与图中其他连通分量没有连接。
有向图的连通分量：在有向图中，连通性有更多复杂性。一个强连通分量是指在有向图中，对于一个连通子集中的任意两个顶点 uuu 和 vvv，都存在一条从 uuu 到 vvv 的路径以及从 vvv 到 uuu 的路径。
连通分量的性质：
不交性：不同的连通分量是互相不相交的，换句话说，一个顶点只能属于一个连通分量。
最大性：连通分量是最大的连通子图，任何额外添加顶点或边会导致不再是连通分量。
子图的连通性：一个连通分量是图的子图，并且是连通的。
1.4 秩
秩（rank）是用于衡量树的“高度”或“深度”的一种近似值。它不是树的确切高度，而是用于帮助决定在合并两个集合时，应该将哪个树挂在另一个树下，以尽量保持树的高度尽可能小。
2 Kruskal算法
2.1 Kruskal算法背景
最小生成树（MST，Minimum Spanning Tree）问题是图论中的经典问题之一。给定一个加权无向连通图，最小生成树是该图的一个子图，它包含图中所有的顶点，并且是一棵没有环的树，且使所有边的权重和最小。
Kruskal算法正是用于解决最小生成树问题的一种贪心算法，它的特点是通过逐步选择权值最小的边来构建最小生成树，过程中确保不会形成环。
2.2 Kruskal算法的核心思想
Kruskal算法基于贪心策略，逐步构建最小生成树。其核心思想是按边权从小到大选择边，保证加入的边不会形成环，直到所有顶点都连接在一起。
主要步骤是：
边排序：首先将图中的所有边按权值从小到大排序。
贪心选择：依次选择权值最小的边，如果加入该边不会导致生成树中形成环，则将其加入最小生成树；否则跳过该边。
终止条件：重复上述步骤直到选取的边数为
n-1
（
n
是图中顶点数），此时最小生成树构建完成。
2.3 Kruskal算法的具体步骤
具体过程可以分为以下几个步骤：
2.3.1 初始化
输入：给定一个加权无向连通图，图的表示通常为
(V, E)
，其中
V
是顶点的集合，
E
是边的集合，每条边有一个权值。输出：最小生成树，边的集合
T
，它是
E
的一个子集，使得所有的顶点都被连接且边的总权值最小。
2.3.2 步骤
将所有边按权值排序： 首先，将图中所有边按照权值从小到大进行排序。
初始化并查集： 将图中的每个顶点初始化为一个单独的集合（每个顶点都是其自身的“连通分量”）。并查集会用来判断两个顶点是否属于同一连通分量，从而避免形成环。
逐一处理边： 从排序后的边列表中，依次选择每条边：
使用并查集的
find()
操作来判断这条边的两个顶点是否属于同一连通分量。如果不属于同一连通分量，则将该边加入到最小生成树中，并使用
union()
操作将这两个顶点所在的连通分量合并。如果属于同一连通分量，跳过该边，以避免生成环。
- 终止条件： 重复上述步骤，直到最小生成树中包含
n-1
条边（
n
为图中顶点的数量）。此时所有顶点都已连通，最小生成树构建完成。
2.4 如何使用并查集判断连通性
并查集（Union-Find）是解决连通分量问题的常用数据结构，能够高效处理连通性查询和集合合并操作。并查集的核心操作有两个：
查找（Find）：查找一个顶点所属的集合（即查找其根节点）。
合并（Union）：将两个不同的集合合并为一个集合。
2.4.1 并查集的查找操作
查找操作用于找到某个顶点所在连通分量的“根”代表节点。为了提高效率，使用路径压缩优化：在查找过程中，将访问路径上的所有节点直接连接到根节点上，避免树的高度过大，从而加快后续的查找操作。
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # 路径压缩
return parent[x]
2.4.2 并查集的合并操作
合并操作用于将两个不同的连通分量合并成一个。为了防止树的高度过高，使用按秩合并优化：将秩（rank）较小的树连接到秩较大的树上，从而保持树的平衡。
def union(x, y):
rootX = find(x)
rootY = find(y)
if rootX != rootY: # 如果两个顶点的根不同，进行合并
if rank[rootX] > rank[rootY]:
parent[rootY] = rootX
elif rank[rootX] < rank[rootY]:
parent[rootX] = rootY
else:
parent[rootY] = rootX
rank[rootX] += 1 # 当秩相同时，合并后需要增加秩
2.4.3 判断连通性
当处理某条边
(u, v)
时，使用
find(u)
和
find(v)
来判断这两个顶点是否在同一个连通分量中。如果
find(u) == find(v)
，则表示它们在同一个连通分量中，加入这条边会导致环的形成；否则可以安全地加入这条边。
def is_connected(u, v):
return find(u) == find(v)
2.5 Kruskal算法的复杂度分析
时间复杂度：
边的排序时间复杂度为
O(E log E)
，其中
E
是边的数量。并查集的查找和合并操作在使用路径压缩和按秩合并的情况下，单次操作的时间复杂度接近
O(1)
，所以处理每条边的连通性判断的复杂度是
O(E)
。综合时间复杂度为
O(E log E)
。空间复杂度：
并查集存储了顶点的父节点和秩，空间复杂度为
O(V)
，其中
V
是顶点的数量。
2.6 Kruskal 过程图解
3 Kruskal算法聚类场景应用
因为我是应用在对跟踪的障碍物轨迹进行聚类，我就以这个场景举例
数据准备：
轨迹数据收集：获取每个障碍物的轨迹数据，这些数据通常包括时间戳、位置坐标（例如 (s,l,t)。
数据格式化：将轨迹数据格式化为便于处理的结构，如数组或数据框，以便于后续分析。
距离计算：
选择距离度量：根据数据特性选择适当的距离度量方法，如欧几里得距离、曼哈顿距离或动态时间规整（DTW）。
构建距离矩阵：计算所有轨迹点之间的距离，形成一个距离矩阵 D，矩阵中的每个元素 D[i][j]表示轨迹 i和轨迹 j之间的距离。
构建边集：
创建边的列表：将距离矩阵转换为边集，每条边由一对轨迹点和对应的距离（权重）组成。
排序边：按照边的权重（距离）从小到大对边集进行排序，以便在后续步骤中优先考虑相似的轨迹。
使用Kruskal算法：
初始化：创建一个空的最小生成树和一个用于跟踪不同连通分量的并查集（Union-Find）数据结构。
遍历边集：
对于每条边 (i,j,w)，判断连接的两个轨迹 i 和 j 是否在同一连通分量中（即是否形成环路）：
如果不在同一分量中，则将这条边加入最小生成树，并合并这两个分量。
如果在同一分量中，则忽略这条边，继续检查下一条边。
重复此过程，直到所有轨迹都被连接在一起，或者所有边都已被检查完。
聚类结果提取：
聚类划分：根据最小生成树的结构，确定不同的聚类。这个可以根据实际场景来