图¶
📖 章节简介¶
本章将介绍C++的图数据结构，包括图的表示、DFS、BFS和最短路径算法。
上图对比了邻接矩阵与邻接表两种表示方式，帮助理解它们在空间复杂度与适用场景上的差别。
📊 图的表示¶
1. 邻接矩阵¶
C++
// 邻接矩阵
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int numVertices;
vector<vector<int>> adjMatrix;
public:
Graph(int vertices) {
numVertices = vertices;
adjMatrix.resize(vertices, vector<int>(vertices, 0));
}
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // 无向图
}
void display() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
bool hasEdge(int u, int v) {
return adjMatrix[u][v] == 1;
}
};
int main() {
Graph graph(4);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
// 显示邻接矩阵
cout << "邻接矩阵：" << endl;
graph.display();
// 检查边
cout << "\n(0,1)有边: " << (graph.hasEdge(0, 1) ? "是" : "否") << endl;
cout << "(1,3)有边: " << (graph.hasEdge(1, 3) ? "是" : "否") << endl;
return 0;
}
2. 邻接表¶
C++
// 邻接表
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class Graph {
private:
int numVertices;
vector<list<int>> adjList;
public:
Graph(int vertices) {
numVertices = vertices;
adjList.resize(vertices);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // 无向图
}
void display() {
for (int i = 0; i < numVertices; i++) {
cout << "顶点" << i << ": ";
for (int neighbor : adjList[i]) {
cout << neighbor << " -> ";
}
cout << "NULL" << endl;
}
}
vector<int> getNeighbors(int vertex) {
return vector<int>(adjList[vertex].begin(), adjList[vertex].end());
}
};
int main() {
Graph graph(4);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
// 显示邻接表
cout << "邻接表：" << endl;
graph.display();
// 获取邻居
cout << "\n顶点2的邻居：";
vector<int> neighbors = graph.getNeighbors(2);
for (int neighbor : neighbors) {
cout << neighbor << " ";
}
return 0;
}
🔍 深度优先搜索（DFS）¶
1. DFS实现¶
C++
// DFS实现
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// ⚠️ 线程安全/可重入性提示：visited 作为成员变量存储遍历状态，
// 使得 DFS/BFS 方法不可重入——不能在多线程中并发调用，也不能在遍历回调中再次调用。
// 更好的做法是将 visited 作为局部变量传入遍历方法。
class Graph {
private:
int numVertices;
vector<vector<int>> adjList;
vector<bool> visited;
public:
Graph(int vertices) {
numVertices = vertices;
adjList.resize(vertices);
visited.resize(vertices, false);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
void DFS(int start) {
fill(visited.begin(), visited.end(), false);
cout << "DFS遍历结果：";
DFSUtil(start);
cout << endl;
}
void DFSUtil(int vertex) {
visited[vertex] = true;
cout << vertex << " ";
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
DFSUtil(neighbor);
}
}
}
void DFSIterative(int start) {
fill(visited.begin(), visited.end(), false);
stack<int> s;
s.push(start);
visited[start] = true;
cout << "DFS迭代遍历结果：";
while (!s.empty()) {
int vertex = s.top();
s.pop();
cout << vertex << " ";
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
s.push(neighbor);
visited[neighbor] = true;
}
}
}
cout << endl;
}
};
int main() {
Graph graph(6);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
// DFS遍历
graph.DFS(0);
// DFS迭代遍历
graph.DFSIterative(0);
return 0;
}
🌊 广度优先搜索（BFS）¶
1. BFS实现¶
C++
// BFS实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
int numVertices;
vector<vector<int>> adjList;
vector<bool> visited;
public:
Graph(int vertices) {
numVertices = vertices;
adjList.resize(vertices);
visited.resize(vertices, false);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
void BFS(int start) {
fill(visited.begin(), visited.end(), false);
queue<int> q;
q.push(start);
visited[start] = true;
cout << "BFS遍历结果：";
while (!q.empty()) {
int vertex = q.front();
q.pop();
cout << vertex << " ";
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
cout << endl;
}
void BFSLevelOrder(int start) {
fill(visited.begin(), visited.end(), false);
queue<int> q;
q.push(start);
visited[start] = true;
cout << "BFS层序遍历结果：" << endl;
int level = 0;
while (!q.empty()) {
int levelSize = q.size();
cout << "第" << level << "层: ";
for (int i = 0; i < levelSize; i++) {
int vertex = q.front();
q.pop();
cout << vertex << " ";
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
cout << endl;
level++;
}
}
};
int main() {
Graph graph(6);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
// BFS遍历
graph.BFS(0);
// BFS层序遍历
graph.BFSLevelOrder(0);
return 0;
}
🛣️ 最短路径¶
1. Dijkstra算法¶
C++
// Dijkstra算法
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class Graph {
private:
int numVertices;
vector<vector<pair<int, int>>> adjList; // (neighbor, weight)
public:
Graph(int vertices) {
numVertices = vertices;
adjList.resize(vertices);
}
void addEdge(int u, int v, int weight) {
adjList[u].push_back({v, weight});
adjList[v].push_back({u, weight}); // 无向图
}
void dijkstra(int start) {
vector<int> distance(numVertices, INT_MAX);
vector<bool> visited(numVertices, false);
vector<int> parent(numVertices, -1);
distance[start] = 0;
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (visited[u]) {
continue;
}
visited[u] = true;
for (auto& edge : adjList[u]) {
int v = edge.first;
int weight = edge.second;
if (!visited[v] && distance[u] != INT_MAX &&
distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
parent[v] = u;
pq.push({distance[v], v});
}
}
}
// 输出最短路径
cout << "顶点\t距离\t路径" << endl;
for (int i = 0; i < numVertices; i++) {
cout << i << "\t" << distance[i] << "\t";
if (distance[i] != INT_MAX) {
// 回溯路径
vector<int> path;
int current = i;
while (current != -1) {
path.push_back(current);
current = parent[current];
}
for (int j = path.size() - 1; j >= 0; j--) {
cout << path[j];
if (j > 0) {
cout << " -> ";
}
}
}
cout << endl;
}
}
};
int main() {
Graph graph(5);
// 添加边
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 7);
graph.addEdge(2, 3, 3);
graph.addEdge(3, 4, 1);
graph.addEdge(4, 3, 2);
// Dijkstra算法
graph.dijkstra(0);
return 0;
}
💡 最佳实践¶
1. 图表示选择¶
C++
// 图表示选择
int main() {
// ✅ 好的做法：根据图的特点选择表示方式
// 稀疏图：使用邻接表
// 稠密图：使用邻接矩阵
// ❌ 不好的做法：不根据情况选择
// 总是使用邻接矩阵（稀疏图浪费空间）
// 总是使用邻接表（稠密图查询慢）
return 0;
}
2. 算法选择¶
C++
// 算法选择
int main() {
// ✅ 好的做法：根据需求选择算法
// 最短路径：Dijkstra算法
// 最小生成树：Prim或Kruskal算法
// 拓扑排序：Kahn算法
// ❌ 不好的做法：不根据需求选择
// 总是使用DFS（BFS可能更合适）
// 总是使用Dijkstra（图无权重时BFS更合适）
return 0;
}
📝 练习题¶
基础题¶
- 什么是图？
- 邻接矩阵和邻接表有什么区别？
- DFS和BFS有什么区别？
进阶题¶
- 实现图的DFS和BFS。
- 实现Dijkstra算法。
- 实现拓扑排序。
实践题¶
- 创建一个简单的社交网络。
- 实现一个路由算法。
- 构建一个迷宫求解器。
📚 推荐阅读¶
🔗 下一章¶
排序算法 - 学习C++的排序算法。