算法图论

最小生成树

字数统计: 1.2k字   |   阅读时长: 6分

$1 Kruskal 算法

算法

1
2
3
4
5
cost = 0
循环 n - 1 次 (选 n - 1 条边): 
    按照 w 从小到大枚举边 edge = (u, v, w)，uv 不连通
    merge(u, v)
    cost += w

时间复杂度 $O(E\log E)$，来自对边的排序。

代码(模板)

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
75
class UnionFindSet
{
public:
    UnionFindSet(int N)
    {
        _father = vector<int>(N + 1, -1);
        _rank = vector<int>(N + 1, 1);
        for(int i = 1; i <= N; ++i)
            _father[i] = i;
    }

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);

        if(x == y) return;
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
            _father[y] = x;
        if(_rank[x] == _rank[y])
            ++_rank[x];
    }

private:
    vector<int> _father;
    vector<int> _rank;

    int _find(int x)
    {
        if(_father[x] == x) return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int minimumCost(int N, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(), Cmp());
        UnionFindSet unionfindset(N);
        int cost = 0;
        int cnt = 0;
        for(const vector<int>& connection: connections)
        {
            int x = connection[0], y = connection[1], w = connection[2];
            if(unionfindset.same(x, y))
                continue;
            cost += w;
            unionfindset.merge(x, y);
            ++cnt;
            if(cnt == N - 1)
                break;
        }
        if(cnt < N - 1)
            return -1;
        return cost;
    }

private:
    struct Cmp
    {
        bool operator() (const vector<int>& edge1, const vector<int>& edge2)
        {
            if(edge1[2] == edge2[2])
                return edge1 < edge2;
            return edge1[2] < edge2[2];
        }
    };
};

切分定理

切分：将图中的顶点分成两部分(对顶点红蓝二着色)，称为一个切分

横切边：一条边对的两个端点颜色不一样，称为横切边

用横切边和切分的概念重新定义二分图：对于一个图，可以找到某个切分，使得图中所有边都是横切边，则 G 为二分图

切分定理： 横切边中的最短边，属于最小生成树

用反证法证明

Kruskal 贪心的正确性

Kruskal 算法每次选择一个最短边，如果这个边没有形成环(两个端点不连通)，相当于是对于一个切分选择了最短的横切边。

Kruskal 可以顺便判定环(相当于用并查集判定环)

$2 Prim

算法

1
2
3
4
5
6
将 0 加入集合 T
while 尚有点没有进入集合 T
    从剩下的点中，选出最短的边 `(u, v, w)`
    其中 u 属于 T，v 不属于 T，即 uv 是横切边
    cost += w
    v 加入 T

时间复杂度：

  • 邻接矩阵: $O(V^{2})$
  • 邻接表 + 二叉堆: $O(E\log E)$
  • 邻接表 + 索引堆: $O(E\log V)$
  • 邻接表 + 斐波那契堆: $O(E + V\log V)$

代码(模板)

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
class Solution {
public:
    int minimumCost(int N, vector<vector<int>>& connections) {
        vector<vector<vector<int> > > g(N + 1);
        for(const vector<int> &connection: connections)
        {
            int x = connection[0], y = connection[1], w = connection[2];
            g[x].push_back(vector<int>({w, y}));
            g[y].push_back(vector<int>({w, x}));
        }
        priority_queue<vector<int> > pq;
        pq.push({0, 1});
        vector<int> visited(N + 1, false);
        visited[0] = true;
        int cost = 0;
        while(!pq.empty())
        {
            vector<int> cur = pq.top();
            pq.pop();
            if(visited[cur[1]])
                continue;
            visited[cur[1]] = true;
            cost += -cur[0];
            for(vector<int> son: g[cur[1]])
            {
                if(visited[son[1]])
                    continue;
                pq.push({-son[0], son[1]});
            }
        }
        for(bool v: visited)
            if(!v)
                return -1;
        return cost;
    }
};

代码(模板)

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
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<vector<int>> adj(n, vector<int>(n, 0));
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                int d = manhattan(points[i][0], points[i][1], points[j][0], points[j][1]);
                adj[i][j] = adj[j][i] = d;
            }
        int cost = 0;
        vector<int> visited(n, false);
        // 选择 visited[i] && !visited[j] 的边 ij 中 adj[i][j] 最小的
        vector<int> d(n, INT_MAX / 2);
        // d[j] := !visited[j] 成立的最小的 adj[i][j]
        d[0] = 0;
        for(int cnt = 1; cnt <= n; ++cnt) // 选出 n 个点
        {
            // 选出使得 d[j] 最小的 j
            // !visited[j] 且使得 adj[i][j] 最小的 j
            int minx = INT_MAX / 2;
            int minx_j = -1;
            for(int j = 0; j < n; ++j)
            {
                if(!visited[j] && d[j] < minx)
                {
                    minx = d[j];
                    minx_j = j;
                }
            }
            cost += minx;
            visited[minx_j] = true;
            // 更新与 minx_j 关联的边
            const int &i = minx_j;
            for(int j = 0; j < n; ++j)
                if(!visited[j] && d[j] > adj[i][j])
                    d[j] = adj[i][j];
        }
        return cost;
    }

private:
    int manhattan(int x1, int y1, int x2, int y2)
    {
        return abs(x1 - x2) + abs(y1 - y2);
    }
};

$3 超级源

超级源

$4 其它

  • Fredman-Tarjan: $O(E+V\logV)$
  • Chazelle: 近似 $O(E)$，例如并查集如果同时使用路径压缩和按秩合并，则可以说近似 $O(1)$
Share