Chapter 19 Graphs (3)
基本题目
1584. 连接所有点的最小费用
Prim 算法：选择距离生成树最近的节点，将他加入生成树，更新剩余节点到生成树的距离。复杂度 $O(n^{2})$ 或 $O((n+m)\log n)$（取决于实现方式）
class Solution {
public:
int dist(const vector<vector<int>>& points, int i, int j) {
return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
}
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
unordered_set<int> connected;
connected.insert(0);
for (int i = 0; i < n; i++) {
if (!connected.count(i)) {
pq.push({dist(points, 0, i), i});
}
}
int result = 0;
while (connected.size() < n) {
auto tmp = pq.top();
pq.pop();
if (connected.count(tmp.second)) continue;
result += tmp.first;
connected.insert(tmp.second);
for (int i = 0; i < n; i++) {
if (!connected.count(i)) {
pq.push({dist(points, tmp.second, i), i});
}
}
}
return result;
}
};
Kruskal 算法：边从小到大遍历，如果边的两个节点不在同一集合，则将其加入边，并更新集合（可使用并查集）。复杂度 $O(m\log m)$
207. 课程表
拓扑排序
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses, 0);
vector<vector<int>> edges(numCourses);
for (const vector<int> &preReq : prerequisites) {
inDegree[preReq[0]]++;
edges[preReq[1]].push_back(preReq[0]);
}
// Find 0-inDegree nodes
int count = 0;
queue<int> coursesToTake;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
coursesToTake.push(i);
}
}
// Pop a 0-inDegree node
while (!coursesToTake.empty()) {
// Take the course
int tmp = coursesToTake.front();
coursesToTake.pop();
count++;
// Remove the prerequisite
for (const int &dst : edges[tmp]) {
if (--inDegree[dst] == 0) {
coursesToTake.push(dst);
}
}
}
return count == numCourses;
}
};
拓扑排序也可以使用 DFS 实现（逆序搜索）
743. 网络延迟时间
Dijkstra 算法
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int, int>>> edges(n + 1);
for (const vector<int> &time : times) {
edges[time[0]].emplace_back(time[2], time[1]);
}
unordered_set<int> received;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.emplace(0, k);
int total = 0;
while (!q.empty() && received.size() < n) {
auto tmp = q.top();
q.pop();
if (received.count(tmp.second)) continue;
total = tmp.first;
received.insert(tmp.second);
for (const auto &[t, dst] : edges[tmp.second]) {
if (!received.count(dst)) {
q.emplace(t + total, dst);
}
}
}
return received.size() == n ? total : -1;
}
};
也可以使用 Bellman-Ford 算法求解（适用权值为负的边，无负权回路）：
- 数组表示到各个终点的距离；
- 初始状态表示经过 0 步到达该终点；
- 每次迭代所有边对应一次松弛（多走一步）。
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int, int>>> edges(n + 1);
for (const vector<int> &time : times) {
edges[time[0]].emplace_back(time[2], time[1]);
}
vector<int> ppg_time(n + 1, INT_MAX / 2);
ppg_time[k] = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= n; j++) {
for (const auto &[t, dst] : edges[j]) {
ppg_time[dst] = min(ppg_time[j] + t, ppg_time[dst]);
}
}
}
int max_time = -1;
for (int i = 1; i <= n; i++) {
max_time = max(max_time, ppg_time[i]);
}
return max_time == INT_MAX / 2 ? -1 : max_time;
}
};
Bellman-Ford 算法可优化为 Queue Improved Bellman-Ford：
- 迭代时将边的目标节点记录进队列，后续更新只考虑队列中的元素；
- 自带终止条件检测：队列为空则无更新。
Bellman-Ford 算法的扩展：
- Bellman-Ford 算法中判断负权回路：多松弛一次/统计入队次数
- 限制路径中的边数：控制总迭代次数/逐级分层迭代
补充：Dijkstra 算法的拓展——A-star 算法
- 调整优先队列中元素的顺序——添加启发式权值函数（例如起点到节点的距离+节点到终点的距离）
- 更接近于人类的思考方式：优先考虑直达终点的路径
1334. 阈值距离内邻居最少的城市
Floyd-Warshall 算法
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
// Initialization
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n, vector<int>(n, INT_MAX / 2)));
for (const vector<int> &edge : edges) {
dp[0][edge[0]][edge[1]] = edge[2];
dp[0][edge[1]][edge[0]] = edge[2];
}
for (int i = 0; i < n; i++) {
dp[0][i][i] = 0;
}
// Floyd-Warshall
for (int k = 1; k <= n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k - 1] + dp[k - 1][k - 1][j]);
}
}
}
// Find city
int minCity = -1, minCount = INT_MAX;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (dp[n][i][j] <= distanceThreshold) {
count++;
}
}
if (count <= minCount) {
minCity = i;
minCount = count;
}
}
return minCity;
}
};
搜索算法总结：
- 邻接表+Dijkstra：$O(n(n+m))$
- 邻接矩阵+Dijkstra：$O(n^2)$
- 堆+Dijkstra：$O(m\log n)$
- Bellman-Ford：$O(nm)$
- SPFA：$O(km−nm)$
拓展题目
210. 课程表 II
拓扑排序
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses, 0);
vector<vector<int>> edges(numCourses);
for (const vector<int> &preReq : prerequisites) {
inDegree[preReq[0]]++;
edges[preReq[1]].push_back(preReq[0]);
}
// Find 0-inDegree nodes
queue<int> coursesToTake;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
coursesToTake.push(i);
}
}
// Pop a 0-inDegree node
vector<int> result;
while (!coursesToTake.empty()) {
// Take the course
int tmp = coursesToTake.front();
coursesToTake.pop();
result.push_back(tmp);
// Remove the prerequisite
for (const int &dst : edges[tmp]) {
if (--inDegree[dst] == 0) {
coursesToTake.push(dst);
}
}
}
return result.size() == numCourses ? result : vector<int>();
}
};