• 图论算法

    图论算法

    复习: 图的基本概念和算法

    复习: 图

    在这里插入图片描述

    图可以表示为一个点集和一个边集: Graph(V,E)

    v - vertex:点
    点的度数(degree)
    入度和出度 – 一个点相连的入边/出边数量

    E- edge:边
    有向和无向
    带权图: 边的权值（长度)

    “连通”、“环”等概念

    复习: 图的存储

    在这里插入图片描述

    复习: 图的深度优先遍历

    在这里插入图片描述

    复习: 图的广度优先遍历

    在这里插入图片描述

    最短路

    单源最短路径问题

    单源最短路径问题( Single Source Shortest Path,SSSP问题）是说:

    • 给定一张有向图G=(V,E)，V是点集，E是边集，V=n，IE|= m
    • 节点以[1,n]之间的连续整数编号
    • (x,y,z)描述一条从x出发，到达y，长度为z的有向边
    • 设1号点为起点

    求长度为n的数组dist，其中dist[i]表示从起点1到节点i的最短路径的长度

    Bellman-Ford算法

    Bellman-Ford算法是基于动态规划和迭代思想的

    1. 扫描所有边(x,y,z)，若dist[y] > dist[x]+z，则用dist[x]+z更新dist[y]
    2. 重复上述步骤，直到没有更新操作发生

    若问题有解（图中没有负环)，Bellman-Ford“扫描所有边并更新”的过程至多执行n-1轮
    原因:一条最短路至多包含n-1条边
    时间复杂度O(nm)

    可以把每一轮看作DP的一个阶段
    第i轮至少已经求出了包含边数不超过i的最短路

    Bellman-Ford算法演示

    只需要一轮的例子?
    需要n-1轮的例子?
    在这里插入图片描述
    一般图上的演示

    在这里插入图片描述

    Dijkstra算法

    Dijkstra算法是基于贪心思想的，只适用于所有边的长度都是非负数的图

    1. 初始化dist[1]=0，其余节点的dist值为正无穷大
    2. 找出一个未被标记的、dist[x]最小的节点x，然后标记节点x
    3. 扫描节点x的所有出边(x,y,z)，若dist[y] > dist[x]＋z，则使用dist[x]＋z更新dist[y]
    4. 重复上述2~3两个步骤，直到所有节点都被标记

    贪心思路:在非负权图上，全局最小的dist值不可能再被其他节点更新
    因此可以不断取dist最小的点（每个点只被取一次)，更新其他点

    用二叉堆维护最小dist值可以做到o(m*log(n))的时间复杂度

    Dijkstra 算法的另一种理解方法:优先队列BFS

    如果边权都是1，求最短路，可以用BFS
    BFS为什么每个点只需要访问一次?因为队列中点对应的路径长度满足“单调性”和“两段性"

    如果边权是任意非负数，怎么保证每个点依然只需要扩展一次?
    优先队列BFS——先扩展最短的

    Dijkstra算法演示

    在这里插入图片描述

    实战

    743.网络延迟时间
    https://leetcode.cn/problems/network-delay-time/
    方法一:Bellman-Ford

    class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> dist( n + 1, 1e9);

        int round = n - 1;
        dist[k] = 0;

        for (int i = 0; i < round; i++ ) {
            bool flag = false;

            for (vector<int>& edge : times) {
                int x = edge[0];
                int y = edge[1];
                int z = edge[2];

                if( dist[x] + z < dist[y]) {
                    dist[y] = dist[x] + z;
                    flag = true;
                }
            }
            if (!flag ) break;

        }

        int ans = 0;
        for (int i = 1; i < dist.size(); i++) {
            ans = max (ans, dist[i]);
        }

        return ans == 1e9 ? -1 : ans;
    }
};

    • 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

    方法二:Dijkstra算法

    class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        ver = vector<vector<int>>(n + 1, vector<int>());
        edge = vector<vector<int>>(n + 1, vector<int>());
        for (vector<int>& t : times) {
            int x = t[0];
            int y = t[1];
            int z = t[2];
            ver[x].push_back(y);
            edge[x].push_back(z);
        }

        dist = vector<int>(n + 1, 1e9);
        dist[k] = 0;
        expand = vector<bool>(n + 1, false);

        // for (int round = 1; round <= n; round++) {
        //     int temp = 1e9, x;
        //     for (int i = 1; i <= n; i++) {
        //         if(!expand[i] && dist[i] < temp) {
        //             temp = dist[i];
        //             x = i;
        //         }
        //     }
        //     expand[x] = true;
        //     for (int i = 0; i < ver[x].size(); i++) {
        //         int y = ver[x][i];
        //         int z = edge[x][i];
        //         if (dist[y] > dist[x] + z) {
        //             dist[y] = dist[x] + z;
        //         }
        //     }
        // }

        q.push({0, k});
        while (!q.empty()) {
            int x = q.top().second;
            q.pop();
            if(expand[x]) continue;
            expand[x] = true;
            for(int i = 0; i < ver[x].size(); i++) {
                int y = ver[x][i];
                int z = edge[x][i];
                if(dist[y] > dist[x] + z) {
                    dist[y] = dist[x] + z;
                    q.push({-dist[y], y});
                }
            }
        }

        int ans = 0;
        for (int i = 1; i < dist.size(); i++) {
            ans = max (ans, dist[i]);
        }

        return ans == 1e9 ? -1 : ans;
    }
private:
    vector<int> dist;
    vector<bool> expand;
    vector<vector<int>> ver;
    vector<vector<int>> edge;

    priority_queue<pair<int, int>> q;
};

    • 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

    Floyd 算法

    Floyd算法可以在O(n)时间内求出图中每一对点之间的最短路径
    本质上是动态规划算法

    dp[k,i,j]表示经过编号不超过k的点为中继，从i到j的最短路

    决策:是否使用k这个中继点
    dp[k,i,j ] = min(dp[k -1,i,j], dp[k - 1,i,k]+dp[k -1,k,j])
    可以省掉第一维，变成
    d[i,j] = min(d[i,j],d[i,k]+ d[k,j]
    初态:d为邻接矩阵（原始图中的边)

    与Bellman-Ford，Dijkstra的比较:O(n3) vs o(n2m) vs o(nmlogn)

    实战

    1334.阈值距离内邻居最少的城市
    https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

    class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {

        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = 1000000000;
        
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            int z = edge[2];
            d[x][y] = d[y][x] = z;
        }

        for (int k = 0; k < n; k++) 
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
        int minNeighbour = 1000000000;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int neighbour = 0;
            for (int j = 0; j < n; j++)
                if (i != j && d[i][j] <= distanceThreshold) neighbour++;
            if (neighbour < minNeighbour ||
                neighbour == minNeighbour && i > ans) {
                    minNeighbour = neighbour;
                    ans = i;
            } 
        }
        return ans;
    }
}

    • 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

    最小生成树

    最小生成树问题

    给定一张边带权的无向图G =(V,E),n = |Vl,m = |EI。

    由V中全部n个顶点和E中n -1条边构成的无向连通子图被称为G的一棵生成树
    边的权值之和最小的生成树被称为无向图G的最小生成树（Minimum Spanning Tree,MST)

    性质:
    任意一棵最小生成树一定包含无向图中权值最小的边

    推论:
    把任何一个生成森林扩展为生成树，一定使用了图中剩余边中权值最小的

    证明方法:树上加一条边形成环＋反证法

    Kruskal 算法

    Kruskal算法总是使用并查集维护无向图的最小生成森林

    1. 建立并查集，每个点各自构成一个集合
    2. 把所有边按照权值从小到大排序，依次扫描每条边(x, y,z)
    3. 若x,y属于同一集合（连通)，则忽略这条边，继续扫描下一条
    4. 否则，合并x,y所在的集合，并把z累加到答案中
    5. 所有边扫描完成后，第4步中处理过的边就构成最小生成树

    时间复杂度为0(m log m)。

    Kruskal 算法演示

    在这里插入图片描述

    实战

    1584.连接所有点的最小费用
    https://leetcode.cn/problems/min-cost-to-connect-all-points/

    经典的“曼哈顿距离最小生成树"

    • Kruskal算法——O(n2logn)
    • Prim算法——O(n2)
    • 树状数组优化建图+ Kruskal——o(nlogn)
    class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {

        int n = points.size();
        vector<vector<int>> edges;
        
        for(int i = 0; i < n; i++) {
            for(int j = i +1; j < n; j++) {
                edges.push_back({i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])});
            }
        }

        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b){
            return a[2] < b[2];
        });

        fa = vector<int>(n, 0);
        for(int i = 0; i < n ; i++) fa[i] = i;

        int ans = 0;


        for(auto edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            from = find(from);
            to = find(to);
            if(from != to){
                ans += weight;
                fa[from] = to;
            }
        }

        return ans;
    }

private:

    int find(int x) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }

    vector<int> fa;

};

    • 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

    推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

  • 相关阅读:
    element-ui vue2 iframe 嵌入外链新解
    [math]判断一个点是否在多边形内的方法
    Kubernetes：（十一）KubeSphere的介绍和安装（华丽的篇章）
    Vue3和Element-Plus
    实现CAS自旋锁
    比 O(nlog(n)) 做得更好——2.改变问题以及排序和填充数组
    机器学习模型监控（Aporia）
    C++ 11
    继承和多态
    SpringCloud Alibaba(三) - GateWay网关
  • 原文地址：https://blog.csdn.net/qq_46118239/article/details/126459977