复习: 图的基本概念和算法
复习: 图
图可以表示为一个点集和一个边集: 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算法是基于动态规划和迭代思想的
- 扫描所有边(x,y,z)，若dist[y] > dist[x]+z，则用dist[x]+z更新dist[y]
- 重复上述步骤，直到没有更新操作发生
若问题有解（图中没有负环)，Bellman-Ford“扫描所有边并更新”的过程至多执行n-1轮
原因:一条最短路至多包含n-1条边
时间复杂度O(nm)
可以把每一轮看作DP的一个阶段
第i轮至少已经求出了包含边数不超过i的最短路
Bellman-Ford算法演示
只需要一轮的例子?
需要n-1轮的例子?
一般图上的演示
Dijkstra算法
Dijkstra算法是基于贪心思想的，只适用于所有边的长度都是非负数的图
- 初始化dist[1]=0，其余节点的dist值为正无穷大
- 找出一个未被标记的、dist[x]最小的节点x，然后标记节点x
- 扫描节点x的所有出边(x,y,z)，若dist[y] > dist[x]＋z，则使用dist[x]＋z更新dist[y]
- 重复上述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; } };
方法二: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; };
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.阈值距离内邻居最少的城市
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; } }
最小生成树
最小生成树问题
给定一张边带权的无向图G =(V,E),n = |Vl,m = |EI。
由V中全部n个顶点和E中n -1条边构成的无向连通子图被称为G的一棵生成树
边的权值之和最小的生成树被称为无向图G的最小生成树（Minimum Spanning Tree,MST)
性质:
任意一棵最小生成树一定包含无向图中权值最小的边
推论:
把任何一个生成森林扩展为生成树，一定使用了图中剩余边中权值最小的
证明方法:树上加一条边形成环＋反证法
Kruskal 算法
Kruskal算法总是使用并查集维护无向图的最小生成森林
- 建立并查集，每个点各自构成一个集合
- 把所有边按照权值从小到大排序，依次扫描每条边(x, y,z)
- 若x,y属于同一集合（连通)，则忽略这条边，继续扫描下一条
- 否则，合并x,y所在的集合，并把z累加到答案中
- 所有边扫描完成后，第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; };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
