最近在轨迹规划模块需要用到一些聚类算法，于是了解到了最小生成树Kruskal算法+Prim算法，本次先给大家讲一下我对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算法基于贪心策略，逐步构建最小生成树。其核心思想是按边权从小到大选择边，保证加入的边不会形成环，直到所有顶点都连接在一起。

主要步骤是：

1. 边排序：首先将图中的所有边按权值从小到大排序。
2. 贪心选择：依次选择权值最小的边，如果加入该边不会导致生成树中形成环，则将其加入最小生成树；否则跳过该边。
3. 终止条件：重复上述步骤直到选取的边数为 n-1（n 是图中顶点数），此时最小生成树构建完成。

2.3 Kruskal算法的具体步骤

具体过程可以分为以下几个步骤：

2.3.1 初始化

• 输入：给定一个加权无向连通图，图的表示通常为(V, E)，其中 V 是顶点的集合，E 是边的集合，每条边有一个权值。
• 输出：最小生成树，边的集合T，它是E的一个子集，使得所有的顶点都被连接且边的总权值最小。

2.3.2 步骤

1. 将所有边按权值排序： 首先，将图中所有边按照权值从小到大进行排序。

2. 初始化并查集： 将图中的每个顶点初始化为一个单独的集合（每个顶点都是其自身的“连通分量”）。并查集会用来判断两个顶点是否属于同一连通分量，从而避免形成环。

3. 逐一处理边： 从排序后的边列表中，依次选择每条边：

   • 使用并查集的find()操作来判断这条边的两个顶点是否属于同一连通分量。
   • 如果不属于同一连通分量，则将该边加入到最小生成树中，并使用union()操作将这两个顶点所在的连通分量合并。
   • 如果属于同一连通分量，跳过该边，以避免生成环。

4. 终止条件： 重复上述步骤，直到最小生成树中包含n-1条边（n为图中顶点的数量）。此时所有顶点都已连通，最小生成树构建完成。

2.4 如何使用并查集判断连通性

并查集（Union-Find）是解决连通分量问题的常用数据结构，能够高效处理连通性查询和集合合并操作。并查集的核心操作有两个：

1. 查找（Find）：查找一个顶点所属的集合（即查找其根节点）。
2. 合并（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 是否在同一连通分量中（即是否形成环路）：
      • 如果不在同一分量中，则将这条边加入最小生成树，并合并这两个分量。
      • 如果在同一分量中，则忽略这条边，继续检查下一条边。
  • 重复此过程，直到所有轨迹都被连接在一起，或者所有边都已被检查完。

• 聚类结果提取：

  • 聚类划分：根据最小生成树的结构，确定不同的聚类。这个可以根据实际场景来