数据结构复习考试（11）

发表于   |  

##最小生成树
最小生成树：任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通). 加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和. 最小代价生成树是其所有生成树中代价最小的生成树。

最小生成树其实是最小权重生成树的简称。

以有线电视电缆的架设为例，若只能沿着街道布线，则以街道为边，而路口为顶点，其中必然有一最小生成树能使布线成本最低。

##性质

  • 最小生成树的边数必然是顶点数减一，|E| = |V| - 1。
  • 最小生成树不可以有循环。
  • 最小生成树不必是唯一的。

##常用算法

  • kruskal算法
  • Prim算法

##思想
贪心法：一次“生成”一条“安全边“

1
2
3
4
5
6
GENERIC-MST-FUNCTION (G,w)
1    T := 空集合
2    while T 还不是生成树
3        do 找出对 T 来说是不会形成环，且权重最低的边 (u, v)
4            T := T U {(u, v)}
5    return T

##kruskal算法

###步骤

  1. 新建图G，G中拥有原图中相同的节点，但没有边
  2. 将原图中所有的边按权值从小到大排序
  3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
  4. 重复3，直至图G中所有的节点都在同一个连通分量中

###模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//基于并查集
class Edge{
public:
    int u, v;       //两个结点
    double len;     //边权
    //bool choose;  //边是否使用过

    Edge(){}
    Edge(int _u, int _v, double _len){
        u = _u;
        v = _v;
        len = _len;
        //choose = false;
    }
};

//比较函数，升序
bool cmp(const Edge &a, const Edge &b){
    if (a.len < b.len){
        return true;
    }else{
        return false;
    }
}

class kruskal{
    vector<Edge> edge;  //边的集合
    vector<int> father; //结点的父亲结点
    int n;              //n points
    int ans;            //the least values of the spanning tree

    void Solve(){
        ///Init///
        edge.clear();
        father.clear();
    
        ///read point///
        (read edge[])
        (initial father[])
    
        ///get edges sorted///
        sort(edge.begin(), edge.end(), cmp);
    
        ///kruskal start///
        int cnt = 0;//number of edges
        ans = 0;
        for (int i = 0; i < edge.size(); i++){
            if (cnt == n-s-1) break;
            //一般地，s为0.
            //如果有s条边在算法开始之前确定是最小生成树的一部分，当cnt=n-s-1时，算法完成。
            if (IsSameFa(edge[i].u, edge[i].v)) continue;
            Union(edge[i].u, edge[i].v);
            edge[i].choose = true;
            ans += edge[i].len;
            cnt++;
        }
    
        ///output///
    }
    
    bool IsSameFa(int x, int y){
        return GetFather(x) == GetFather(y);
    }

    void Union(int x, int y){
        father[GetFather(x)] = GetFather(y);
    }

    int GetFather(int x){
        if (father[x] == x) return x;
        else return father[x] = GetFather(father[x]);
    }

}

###算法分析与适用范围
Kruskal算法需要对图的边进行访问，所以时间复杂度只和边有关系，可以证明其时间复杂度为O（E*logE）。

比较适合求稀疏图的最小生成树。