图论简介
如果你正在学习 C++ 并接触算法,图论是一个绕不开的话题。它用数学语言描述了现实世界中复杂的连接关系。
什么是图?
图由顶点(Vertex)和边(Edge)组成。点代表实体,线代表关系。
- 社交网络的好友关系
- 地图上的地点与道路
- 网页之间的超链接
在 C++ 中表示图
计算机处理图主要有两种结构,选择哪种取决于图的密度。
邻接表
适合稀疏图,每个顶点维护一个邻居列表。
#include <vector>
using namespace std;
int n = 5;
vector<vector<int>> graph(n);
// 添加无向边
graph[0].push_back(1);
graph[1].push_back(0);
这种方式空间效率高,查询邻居时直接遍历列表。
邻接矩阵
适合稠密图,用二维数组记录连通性。
#include <vector>
using namespace std;
int n = 5;
vector<vector<bool>> matrix(n, vector<bool>(n, false));
// 连接顶点 0 和 1
matrix[0][1] = true;
matrix[1][0] = true;
if (matrix[0][1]) {
cout << "0 和 1 是相连的" << endl;
}
查询两点是否相连的时间复杂度为 O(1),但空间占用随顶点数平方增长。


