图的算法: 最小生成树

Posted on Edited on In , Word count in article: 1.1k Reading time ≈ 4 mins.

最小生成树

概述

一个连通图的生成树是最简单的连通子图，它连通了图的所有节点，并且只含有节点数减一条边，即没有环

最小生成树是指，假设原图的每条边都含有权重，它的最小生成树的权重和是所有生成树中权重和最小的那棵

能解决的问题：

  • 如结构所描述的那样，多个节点可以互相连通，但最终需要将图化为生成树，则可以用最小生成树算法解决最优问题

图论基础

图的概念

  • 图是非线性的数据结构，可用于表示诸如网络、社会关系、地图、电路图等
  • 称图中任意一对节点的关系为边，如果所有边不强调方向，则称为无向图，否则为有向图
  • 称一个节点的边数为它的度
  • 若无向图中任意两点有且仅有一条边，则称其为无向完全图；若有向图中任意两点有且仅有两条方向相反的边，则称其为有向完全图
  • 若在图中能沿着边从一个节点找到另一节点，则称两点连通；若无向图中任意两点都连通，则称其为连通图；若有向图中任意两节点互相连通，则称其为强连通图
  • 若两点互相连通且最短路径没有其它节点，则称这两点互为邻接节点

邻接矩阵

最简单的图的存储结构就是邻接矩阵，一个无向图需要存储节点间的关系，即边，且边是双向的，这是多对多的逻辑结构

假设图的总结点数为n，其中两个节点为i和j，用一个邻接矩阵就可以简单表示两者关系：

1
2
3
4
int arcs[n][n] {};
arcs[i][j] = 1; // 数组表示节点i与节点j是否邻接(01).
// 如要存储权重,则应用inf表示不邻接.
// 无向图矩阵是对称矩阵.

在有向图中，需定义行数为边的箭头或边的结尾，以表示方向的信息

通过下标映射，数组表示法能够快速查询两点是否邻接，并取得这条边的权重，但有许多缺点：

  • 节点数量较多时，花费空间巨大
  • 无法得知跨节点是否连通，也难以快速求出路径
  • 无法直接取得节点的度，需要遍历一维数组
1
2
3
4
5
6
7
template <typename Note, typename Weight, bool Dir=false>
struct Graph { // Note表示节点类型,Weight表示权重类型,Dir表示有/无向(默认).
    static W MAX = INT_MAX; // 无穷表示不连通.
    Note* notes; // 一维数组存储节点信息.
    W** edges; // 邻接数组存储边信息.
    map<Note, int> Map; // 为了通过节点地址而不是整型下标来访问图, 需要构建映射.
};

邻接表

邻接表使用链表而不是数组来存储边的信息，将边和权重压缩成边节点，将一个数据节点的所有边用边链表表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename Weight>
struct Edge {
    // 不需要无穷,因为不会存储不邻接节点.
    Weight w;
    int connect; // 这条边的终点下标.
    Edge<Weight>* next;
};
template <typename Note, typename Weight, bool Dir=false>
struct Graph {
    Note* notes; // 存储数据节点.
    Edge<Weight>* edges; // 存储边链表的头结点.
    map<Note, int> Map; // 为了通过节点地址而不是整型下标来访问图, 需要构建映射.
};

有向图需要维护两个边链表，分别表示出/入方向的边

最小生成树实现

Prim算法

首先初始化最小生成树，它只有一个节点，基于贪心，每轮外层循环中，通过内层循环遍历所有以这棵树中节点为起点、以未加入节点为终点的边，取最小，并将终点拉入最小生成树，过程中外层一共循环n-1次，可以顺便维护最小路径值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Graph Prim(const Graph& _g) { // 伪代码.
    Edge* tmp, head;
    Graph ans {_g[0]};
    for ( i= 0 : _g.size()-1 ) {
        head = _g.edge(i); // 取得生成树第i节点的边链表.
        tmp = head;
        for ( j= i : 0 ) {
            for (head : end) {
                if (ans.find(head.connect) == -1) // 终点未加入生成树.
                    tmp = tmp->w < head->w ? tmp : head;
            }
            head = _g.edge(j);
        }
        ans.addNote(_g[tmp->connect]);
    }
}