「算法模版」图
存储图
邻接矩阵
邻接表
// 对于每个点k，开一个单链表，存储k所有可以走到的点 // h[k]存储这个单链表的头结点 int h[N], e[N], ne[N], idx; // 添加一条边a->b void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } // 初始化 idx = 0; memset(h, -1, sizeof h);
回溯算法
回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择 : 本层集合中的元素) {
处理节点;
backtracking(路径, 选择列表); // 递归
撤销处理; // 回溯
}
}
图遍历
DFS
int dfs(int u) { st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } }BFS
// 从 s 开始 BFS 遍历图的所有节点，且记录遍历的步数 // 当走到目标节点 target 时，返回步数 int bfs(const Graph& graph, int s, int target) { vector<bool> visited(graph.size(), false); queue<int> q; q.push(s); visited[s] = true; // 记录从 s 开始走到当前节点的步数 int step = 0; while (!q.empty()) { int sz = q.size(); for (int i = 0; i < sz; i++) { int cur = q.front(); // 每次循环中需要处理当前层的所有元素，而不是只处理一个元素。 q.pop(); cout << "visit " << cur << " at step " << step << endl; if (cur == target) return step; // 判断是否到达终点 for (int to : neighborsOf(cur)) { // 将邻居节点加入队列，向四周扩散搜索 if (!visited[to]) { q.push(to); visited[to] = true; } } } step++; } // 如果走到这里，说明在图中没有找到目标节点 return -1; }
岛屿题目
二维矩阵的DFS
// 二叉树遍历框架 void traverse(TreeNode* root) { traverse(root->left); traverse(root->right); } // 二维矩阵遍历框架 void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) { int m = grid.size(), n = grid[0].size(); if (i < 0 || j < 0 || i >= m || j >= n) return; // 超出索引边界 if (visited[i][j]) return; // 已遍历过 (i, j) visited[i][j] = true; // 标记当前位置为已访问 // 向四个方向递归搜索 dfs(grid, i - 1, j, visited); // 上 dfs(grid, i + 1, j, visited); // 下 dfs(grid, i, j - 1, visited); // 左 dfs(grid, i, j + 1, visited); // 右 visited[i][j] = false; // 在回溯时，将 visited[i][j] 恢复为 0，以便其他路径可以重新访问该位置 }使用方向数组遍历
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) { int m = grid.size(), n = grid[0].size(); if (i < 0 || j < 0 || i >= m || j >= n) { // 超出索引边界 return; } if (visited[i][j]) { // 已遍历过 (i, j) return; } // 进入节点 (i, j) visited[i][j] = true; // 递归遍历上下左右的节点 for (auto &d : dirs) { int next_i = i + d[0]; int next_j = j + d[1]; dfs(grid, next_i, next_j, visited); } // 离开节点 (i, j) }
并查集算法
int find(vector<int>& parent, int x) { // 用于查找节点的根，并进行路径压缩
if(parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
void Union(vector<int>& parent, int node1, int node2) { // 用于合并两个集合
parent[find(parent, node1)] = find(parent, node2);
}
Kruskal 算法
将所有边按权重从小到大排序，然后依次选择边，如果这条边不会形成环，就将其加入生成树中。
// 生成所有边与权重
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int weight = abs(x1 - x2) + abs(y1 - y2);
edges.push_back({weight, i, j});
}
}
// 按权重排序
sort(edges.begin(), edges.end(), [](vector<int>& a, vector<int>& b) -> bool {
return a[0] < b[0];
});
UnionFind uf(n);
int minCost = 0;
for(auto& edge: edges) {
int weight = edge[0];
int u = edge[1], v = edge[2];
if(uf.Union(u, v)) minCost += weight;
}
Dijkstra 算法
- 目的：输⼊⼀幅图和⼀个起点 start，计算 start 到其他节点的最短距离
- Dijkstra 将所有节点分成两类：
- 已确定从起点到当前点的最短路长度的节点「已确定节点」
- 未确定从起点到当前点的最短路长度的节点「未确定节点」
每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。
用节点 A「更新」节点 B 的意思是，用起点到节点 A 的最短路长度加上从节点 A 到节点 B 的边的长度，去比较起点到节点 B 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。
即，每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定。
【注】给定的图必须是正边权图，否则「未确定节点」有可能更新当前节点，这也是 Dijkstra 不能处理负权图的原因。
普通的 Dijkstra 算法是通过枚举来寻找「未确定节点」中与起点距离最近的点。在实际实现中，我们可以使用优先队列优化这一过程的时间复杂度。
最大堆：适合稀疏图
class Solution { public: double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) { // 邻接矩阵存储图 vector<vector<pair<double, int>>> graph(n); for (int i = 0; i < edges.size(); i++) { auto& e = edges[i]; graph[e[0]].emplace_back(succProb[i], e[1]); graph[e[1]].emplace_back(succProb[i], e[0]); } priority_queue<pair<double, int>> que; // 最大堆，存可达顶点及概率 vector<double> prob(n, 0); // prob[i]为顶点到i的最大概率 que.emplace(1, start); prob[start] = 1; while (!que.empty()) { auto [pr, node] = que.top(); que.pop(); if (pr < prob[node]) { continue; } for (auto& [prNext, nodeNext] : graph[node]) { // 更新（松弛） if (prob[nodeNext] < prob[node] * prNext) { prob[nodeNext] = prob[node] * prNext; que.emplace(prob[nodeNext], nodeNext); } } } return prob[end]; } };枚举法：适合稠密图
used用于标记节点是否已经被处理过，dist用于存储从源节点 k 到每个节点的最短距离。
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int n, int k) { const int inf = 99999; // inf 表示“无穷大”，用于初始化图中不可达的边 vector<vector<int>> graph(n, vector<int>(n, inf)); // 邻接矩阵，表示图的边权重 for(auto& time: times) { int v = time[0] - 1, u = time[1] - 1; graph[v][u] = time[2]; } vector<int> used(n); // 用于标记节点是否已经被处理过 vector<int> dist(n, inf); // 用于存储从源节点 k 到每个节点的最短距离 dist[k - 1] = 0; for(int i = 0; i < n; i++) { // 确保每个节点都被处理一次 int x = -1; // 记录当前未处理的节点中距离最小的节点 for(int y = 0; y < n; y++) { if(!used[y] && (x == -1 || dist[y] < dist[x])) x = y; } used[x] = true; for(int y = 0; y < n; y++) { // 更新 dist[y] = min(dist[y], dist[x] + graph[x][y]); } } int ans = *max_element(dist.begin(), dist.end()); return ans == inf? -1 : ans; } };