Minimum Spanning Tree - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki
加权无向图Weighted Undirected Graph
|
边权Edge Weight |
| 一般定义 |
边上的权值，代表两个结点的距离（不同场景有不同的意思） |
| 表示方法 |
w(e) |
| 图例 |
|
| 邻接表 |
链表上的结点也要储存边权的值 |
| 邻接矩阵 |
矩阵中aij上不再是0或1，而是边权的值 |
定义
|
生成树Spanning Tree |
最小生成树Minimum Spanning Tree |
| 定义 |
生成树是连接所有节点的边的无环子集 |
生成树的所有边的边权之和最小 |
| 图例 |
|
|
|
割Cut（两个Partition） |
横割Crosses a Cut（横跨两个Partition的边） |
| 定义 |
图的所有结点分成两个不相交的子集的组件Partition |
若与边相连的两个结点分别在两个组件Partition中，则该边会横割Crosses a cut两个分区Partition |
| 图例 |
|
|
入门链接
最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示
最小生成树
【数据结构】prim算法和kruskal算法求最小生成树
详解
算法: 最小生成树
属性
- 无环
- 若把图中的最小生成树切开两部分（移除其中一条边），则两部分依然是最小生成树
- 对于可通过在最小生成树上的某两个结点添加一条边（原图就存在的边，只是标红）形成的每一个环，形成的环上的最大边权的边肯定不在最小生成树中，这意味着添加的那条边才是该环上边权最大的边
- 如下左图中的红边是该图的最小生成树，下右图中上面新添加一条红边后，其中的几条红边（这里是所有红边）形成了一个环，这条新添加的红边就是该环上边权最大的边
- 对于可通过在最小生成树上的某两个结点添加一条边（原图就存在的边，只是标红）形成的每一个环，形成的环上的最小边权的边可能在或可能不在最小生成树中
- 最小生成树是形成的树中所有边的边权之和最小，不一定每一条边的边权最小，这也是为什么不能用最小生成树求最短路径的原因
- 横跨两个组件Partition的边所有边中，边权最小的边肯定在最小生成树中，这意味着对于某一个结点，与该结点相连的所有边中，边权最小的边肯定在最小生成树中，如下图，若A的边权最小，则A肯定是在最小生成树中，这是普里姆Prim算法的核心
- 对于V个结点的图，最小生成树有V-1条边
- 所有边权均不相同的无向图最小生成树是唯一的
算法比较
深度优先和广度优先也可以生成树，但是不是最小
适用场景
- 网络设计
- 电话网络Telephone networks
- 电气网络Electrical networks
- 计算机网络Computer networks
- 以太网自动配置Ethernet autoconfig
- 道路网Road networks
- 瓶颈路径Bottleneck paths
- 纠错码Error correcting codes
- 脸部验证Face verification
- 聚类分析Cluster analysis
- 图像配准Image registration