本文档全面概述了 leetcode-master 仓库中图论的实现。图论是算法和数据结构的一个基础领域，处理对象之间成对关系的建模。本页面涵盖了图的表示、遍历算法以及专门的图算法，包括最短路径、最小生成树和并查集实现。
图论建立在早期主题（如树，参见二叉树）和回溯中使用的递归技术概念之上。它代表了一个高级主题，通常融合了许多以前的算法模式。
在深入研究图算法之前，了解如何在代码中表示图至关重要。该仓库实现了几种常见的表示方法
邻接矩阵是一个二维数组，其中matrix[i][j]表示从顶点i到顶点j的边。这种表示法常用于稠密图。
// Example of adjacency matrix representation
vector<vector<int>> graph(n, vector<int>(n, 0));
// Edge from vertex i to j
graph[i][j] = 1;
邻接列表使用一个列表数组，其中每个条目代表一个顶点，其列表包含所有相邻顶点。这是该仓库中最常见的表示方法。
// Example of adjacency list representation
vector<vector<int>> graph(n);
// Edge from vertex i to j
graph[i].push_back(j);
一个由顶点对表示的边列表，在侧重于边操作时非常有用。
// Example of edge list representation
vector<pair<int, int>> edges;
// Edge from vertex i to j
edges.push_back({i, j});
遍历算法是图操作的基础，允许我们系统地访问每个顶点和边。
深度优先搜索（DFS）在回溯之前尽可能深入地探索一个分支。在该仓库中，DFS 使用递归和迭代两种方法实现。
// Recursive DFS pseudocode
void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
visited[node] = true;
// Process node
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
该仓库中演示的一个关键应用是查找所有可达路径
// Finding all paths from source to target
void dfs(int node, int target, vector<vector<int>>& graph,
vector<int>& path, vector<vector<int>>& result) {
path.push_back(node);
if (node == target) {
result.push_back(path);
} else {
for (int next : graph[node]) {
dfs(next, target, graph, path, result);
}
}
path.pop_back(); // Backtrack
}
广度优先搜索（BFS）逐层遍历图，通常使用队列实现。它对于在无权图中查找最短路径特别有用。
// BFS pseudocode
void bfs(int start, vector<vector<int>>& graph) {
vector<bool> visited(graph.size(), false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
// Process node
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
岛屿问题是一类特殊的图问题，其中图表示为二维网格。这些问题在该仓库中得到了广泛的覆盖，是图遍历算法的绝佳练习。
此问题涉及计算网格中孤立陆地块（岛屿）的数量。DFS 和 BFS 方法都在仓库中得到了演示。
// DFS Solution pseudocode
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1')
return;
grid[i][j] = '2'; // Mark as visited
// Check all 4 directions
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
并查集数据结构对于涉及连通分量和动态连通性的问题至关重要。
该仓库提供了并查集的全面实现，包括路径压缩和按秩合并优化。
// Union-Find implementation pseudocode
class UnionFind {
private:
vector<int> parent;
vector<int> rank;
public:
UnionFind(int size) {
parent.resize(size);
rank.resize(size, 0);
for (int i = 0; i < size; i++)
parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // Path compression
return parent[x];
}
bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
// Union by rank
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
if (rank[rootX] == rank[rootY])
rank[rootX]++;
}
return true;
}
};
并查集特别适用于“查找路径是否存在”和“冗余连接”等问题，这些问题在仓库中都有涉及。
最小生成树（MST）是边的子集，它以最小的总边权重连接所有顶点。该仓库涵盖了两种经典的 MST 算法。
普里姆算法通过从一个顶点开始，并总是添加连接树内顶点和树外顶点的最低权重边来构建 MST。
// Prim's algorithm pseudocode
vector<Edge> primMST(vector<vector<pair<int, int>>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
priority_queue<pair<int, pair<int, int>>> pq; // min-heap for edges
vector<Edge> mst;
visited[0] = true; // Start with vertex 0
// Add all edges from vertex 0
for (auto& edge : graph[0]) {
pq.push({-edge.second, {0, edge.first}}); // Negative weight for min-heap
}
while (!pq.empty() && mst.size() < n - 1) {
auto edge = pq.top();
pq.pop();
int weight = -edge.first;
int u = edge.second.first;
int v = edge.second.second;
if (visited[v]) continue;
visited[v] = true;
mst.push_back({u, v, weight});
// Add all edges from newly added vertex
for (auto& next : graph[v]) {
if (!visited[next.first]) {
pq.push({-next.second, {v, next.first}});
}
}
}
return mst;
}
来源：README.md396
克鲁斯卡尔算法通过按权重排序所有边，并在不形成环的情况下按顺序添加它们（使用并查集）来构建 MST。
// Kruskal's algorithm pseudocode
vector<Edge> kruskalMST(vector<Edge>& edges, int n) {
sort(edges.begin(), edges.end()); // Sort by weight
UnionFind uf(n);
vector<Edge> mst;
for (auto& edge : edges) {
if (uf.find(edge.u) != uf.find(edge.v)) {
uf.unite(edge.u, edge.v);
mst.push_back(edge);
}
if (mst.size() == n - 1) break;
}
return mst;
}
来源：README.md397
查找节点之间的最短路径是图论中的一个基本问题，在现实世界中有很多应用。
用于在非负权重图中查找从单个源点出发的最短路径。
// Dijkstra's algorithm (priority queue optimization) pseudocode
vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (d > dist[node]) continue;
for (auto& edge : graph[node]) {
int neighbor = edge.first;
int weight = edge.second;
if (dist[node] + weight < dist[neighbor]) {
dist[neighbor] = dist[node] + weight;
pq.push({dist[neighbor], neighbor});
}
}
}
return dist;
}
该仓库演示了 Dijkstra 算法的基本版本和优化后的堆版本。
贝尔曼-福特算法处理带有负边权重的图，并且可以检测负环。
// Bellman-Ford algorithm pseudocode
vector<int> bellmanFord(vector<Edge>& edges, int n, int start) {
vector<int> dist(n, INT_MAX);
dist[start] = 0;
// Relax all edges |V|-1 times
for (int i = 0; i < n - 1; i++) {
for (auto& edge : edges) {
if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
dist[edge.v] = dist[edge.u] + edge.weight;
}
}
}
// Check for negative cycles
for (auto& edge : edges) {
if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {
// Negative cycle exists
return {};
}
}
return dist;
}
该仓库还涵盖了 SPFA（最短路径更快算法），它是贝尔曼-福特算法使用队列进行的一种优化。
弗洛伊德-沃沙尔算法查找所有顶点对之间的最短路径。
// Floyd-Warshall algorithm pseudocode
void floydWarshall(vector<vector<int>>& dist) {
int n = dist.size();
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
该仓库还涵盖了一些用于特殊问题的高级图算法。
拓扑排序用于有向无环图（DAG），以线性顺序排列顶点，使得对于每条有向边 (u, v)，顶点 u 都在 v 之前。
// Topological Sort pseudocode using DFS
vector<int> topologicalSort(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
vector<bool> inStack(n, false);
vector<int> result;
function<bool(int)> dfs = [&](int node) {
if (inStack[node]) return false; // Cycle detected
if (visited[node]) return true;
visited[node] = true;
inStack[node] = true;
for (int neighbor : graph[node]) {
if (!dfs(neighbor)) return false;
}
inStack[node] = false;
result.push_back(node);
return true;
};
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (!dfs(i)) return {}; // Cycle detected
}
}
reverse(result.begin(), result.end());
return result;
}
来源：README.md398
A* 是一种启发式搜索算法，它使用启发式函数指导搜索来查找最短路径。
// A* algorithm pseudocode
vector<int> astar(vector<vector<int>>& graph, int start, int goal, function<int(int, int)> heuristic) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
vector<int> gScore(graph.size(), INT_MAX);
vector<int> parent(graph.size(), -1);
gScore[start] = 0;
pq.push({heuristic(start, goal), start});
while (!pq.empty()) {
int node = pq.top().second;
pq.pop();
if (node == goal) {
// Reconstruct path
vector<int> path;
while (node != -1) {
path.push_back(node);
node = parent[node];
}
reverse(path.begin(), path.end());
return path;
}
for (auto& edge : graph[node]) {
int neighbor = edge.first;
int weight = edge.second;
int tentative_gScore = gScore[node] + weight;
if (tentative_gScore < gScore[neighbor]) {
parent[neighbor] = node;
gScore[neighbor] = tentative_gScore;
int fScore = tentative_gScore + heuristic(neighbor, goal);
pq.push({fScore, neighbor});
}
}
}
return {}; // No path found
}
来源：README.md406
该仓库中的图论部分全面覆盖了图算法，从基本的遍历到高级的寻路技术。问题遵循复杂度递增的模式。
这种系统方法有助于建立对图论概念及其应用的扎实理解。
该仓库的图论部分以一个全面的总结结束，将所有概念和算法联系起来，从而更容易理解将哪种算法应用于不同类型的图问题。