图的优势：灵活建模（有向/无向、加权/非加权）； 缺点：存储O(V^2)（稠密图），遍历需vis标记防环。
- 核心思想：图由顶点（V）和边（E）组成。无向图边无方向，有向图有（弧）。加权图边有权值。
- 分类：简单图（无重边/自环）、连通图（无向可达）、强连通（有向互达）。
- 时间/空间复杂度：存储O(V+E)，遍历O(V+E)，最短路径O(V^2)（Dijkstra）。
- 常见类型：
- 无向图 vs 有向图
- 连通图 vs 非连通图
- 有权图 vs 无权图
- 重要术语：邻接、路径、度（入度/出度）
查询快O(1)，但空间占用大O(n²) 在简单图（无自环的图）中，邻接矩阵的主对角线都为0。 使用一个二维数组（矩阵） 来记录图中各个顶点之间的连接关系。 给定一个顶点数量为𝑛的无向图，则各种操作的实现方式如图所示。
- 添加或删除边：直接在邻接矩阵中修改指定的边即可，使用𝑂(1)时间。而由于是无向图，因此需要同 时更新两个方向的边。
- 添加顶点：在邻接矩阵的尾部添加一行一列，并全部填0即可，使用𝑂(𝑛)时间。
- 删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将(𝑛−1)2个元素 “向左上移动”，从而使用𝑂(𝑛2)时间。
- 初始化：传入𝑛个顶点，初始化长度为𝑛的顶点列表 小的邻接矩阵 adjMat ，使用𝑂(𝑛2)时间。 ![[Pasted image 20251115155458.png]]
// === File: graph_adjacency_matrix.cpp ===
/* 基于邻接矩阵实现的无向图类 */
class GraphAdjMat {
vector<int> vertices; // 顶点列表，元素代表"顶点值"，索引代表"顶点索引"
vector<vector<int>> adjMat; // 邻接矩阵，行列索引对应"顶点索引"
public:
/* 构造方法 */
GraphAdjMat(const vector<int> &vertices, const vector<vector<int>> &edges) {
// 添加顶点
for (int val : vertices) {
addVertex(val);
}
// 添加边
// 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
for (const vector<int> &edge : edges) {
addEdge(edge[0], edge[1]);// edge[0]和edge[1]是顶点索引
}
}
/* 获取顶点数量 */
int size() const {
return vertices.size();
}
/* 添加顶点 */
void addVertex(int val) {
int n = size();
// 向顶点列表中添加新顶点的值
vertices.push_back(val);
// 在邻接矩阵中添加一行
adjMat.emplace_back(vector<int>(n, 0));
// 在邻接矩阵中添加一列
for (vector<int> &row : adjMat) {
row.push_back(0);
}
}
/* 删除顶点 */
void removeVertex(int index) {
if (index >= size()) {
throw out_of_range("顶点不存在");
}
// 在顶点列表中移除索引 index 的顶点
vertices.erase(vertices.begin() + index);
// 在邻接矩阵中删除索引 index 的行
adjMat.erase(adjMat.begin() + index);
// 在邻接矩阵中删除索引 index 的列
for (vector<int> &row : adjMat) {
row.erase(row.begin() + index);
}
}
/* 添加边 */
// 参数 i, j 对应 vertices 元素索引
void addEdge(int i, int j) {
// 索引越界与相等处理
if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
throw out_of_range("顶点不存在");
}
// 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) == (j, i)
adjMat[i][j] = 1;
adjMat[j][i] = 1;
}
/* 删除边 */
// 参数 i, j 对应 vertices 元素索引
void removeEdge(int i, int j) {
// 索引越界与相等处理
if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
throw out_of_range("顶点不存在");
}
adjMat[i][j] = 0;
adjMat[j][i] = 0;
}
/* 打印邻接矩阵 */
void print() {
cout << "顶点列表 = ";
printVector(vertices);
cout << "邻接矩阵 =" << endl;
printVectorMatrix(adjMat);
}
};![[Pasted image 20251115160959.png]]
空间节省O(n+m)，但查询稍慢 邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。 比如当链表较长时，可以将链表转化为AVL树或红黑树，从而将时间效率从𝑂(𝑛)优化至𝑂(log𝑛)；还可 以把链表转换为哈希表，从而将时间复杂度降至𝑂(1)。
- 添加边：在顶点对应链表的末尾添加边即可，使用𝑂(1)时间。因为是无向图，所以需要同时添加两个 方向的边。
- 删除边：在顶点对应链表中查找并删除指定边，使用𝑂(𝑚)时间。在无向图中，需要同时删除两个方 向的边。
- 添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用𝑂(1)时间。
- 删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用𝑂(𝑛+𝑚)时间。
- 初始化：在邻接表中创建𝑛个顶点和2𝑚条边，使用𝑂(𝑛+𝑚)时间。 ![[Pasted image 20251115160730.png]]
- **为了方便添加与删除顶点，以及简化代码，我们使用列表（动态数组）来代替链表。
- 使用哈希表来存储邻接表，key为顶点实例， value 为该顶点的邻接顶点列表（链表）。 另外，我们在邻接表中使用 Vertex 类来表示顶点，这样做的原因是：如果与邻接矩阵一样，用列表索引来区 分不同顶点，那么假设要删除索引为𝑖的顶点，则需遍历整个邻接表，将所有大于𝑖的索引全部减1，效率 很低。而如果每个顶点都是唯一的 Vertex 实例，删除某一顶点之后就无须改动其他顶点了。
// === File: graph_adjacency_list.cpp ===
/* 基于邻接表实现的无向图类 */
class GraphAdjList {
public:
// 邻接表，key：顶点，value：该顶点的所有邻接顶点
unordered_map<Vertex*, vector<Vertex*>> adjList;
/* 在 vector 中删除指定节点 */
void remove(vector<Vertex*> &vec, Vertex* vet) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == vet) {
vec.erase(vec.begin() + i);//从顶点列表中删除指定的顶点
break;
}
}
}
/* 构造方法 */
GraphAdjList(const vector<vector<Vertex*>> &edges) {
// 添加所有顶点和边
for (const vector<Vertex*> &edge : edges) {
addVertex(edge[0]);
addVertex(edge[1]);
addEdge(edge[0], edge[1]);
}
}
/* 获取顶点数量 */
int size() {
return adjList.size();
}
/* 添加边 */
void addEdge(Vertex* vet1, Vertex* vet2) {
if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
throw invalid_argument("不存在顶点");
// 添加边 vet1 - vet2
adjList[vet1].push_back(vet2);
adjList[vet2].push_back(vet1);
}
/* 删除边 */
void removeEdge(Vertex* vet1, Vertex* vet2) {
if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
throw invalid_argument("不存在顶点");
// 删除边 vet1 - vet2
remove(adjList[vet1], vet2);
remove(adjList[vet2], vet1);
}
/* 添加顶点 */
void addVertex(Vertex* vet) {
if (adjList.count(vet))
return;
// 在邻接表中添加一个新链表
adjList[vet] = vector<Vertex*>();
}
/* 删除顶点 */
void removeVertex(Vertex* vet) {
if (!adjList.count(vet))
throw invalid_argument("不存在顶点");
// 在邻接表中删除顶点 vet 对应的链表
adjList.erase(vet);
// 遍历其他顶点的链表，删除所有包含 vet 的边
for (auto &adj : adjList) {
remove(adj.second, vet);
}
}
/* 打印邻接表 */
void print() {
cout << "邻接表 =" << endl;
for (auto &adj : adjList) {
const auto &key = adj.first;
const auto &vec = adj.second;
cout << key->val << ": ";
printVector(vetsToVals(vec));
}
}
};![[Pasted image 20251115161618.png]] ![[Pasted image 20251115161626.png]]
| 存储方式 | 空间 | 查边 | 遍历 | 适用 |
|---|---|---|---|---|
| 矩阵 | O(V^2) | O(1) | O(V^2) | 稠密、小V |
| 表 | O(V+E) | O(deg) | O(V+E) | 稀疏、大E |
层序访问，适合最短路径预备。
// === File: graph_bfs.cpp ===
/* 广度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
vector<Vertex*> graphBFS(GraphAdjList &graph, Vertex* startVet) {
// 顶点遍历序列
vector<Vertex*> res;
// 哈希集合，用于记录已被访问过的顶点
unordered_set<Vertex*> visited = {startVet};// 已访问集合（含起点）
// 队列用于实现 BFS
queue<Vertex*> que;
que.push(startVet);
// 以顶点 vet 为起点，循环直至访问完所有顶点
while (!que.empty()) {
Vertex* vet = que.front();
que.pop(); // 队首顶点出队
res.push_back(vet); // 记录访问顶点
// 遍历该顶点的所有邻接顶点
for (auto adjVet : graph.adjList[vet]) {
if (visited.count(adjVet))
continue; // 跳过已被访问的顶点
que.push(adjVet); // 只入队未访问的顶点
visited.emplace(adjVet); // 标记该顶点已被访问
}
}
// 返回顶点遍历序列
return res;
}- 解释：vis入队时标记，防重复。输出层序。
==广度优先遍历的序列是否唯一？ 不唯一。广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序允许被 任意打乱。==
在BFS中使用
unordered_set作为visited集合是因为：
- ✅ 防止重复访问 - 确保每个顶点只处理一次
- ✅ 高性能 - O(1)的查找和插入
- ✅ 灵活性 - 适用于指针等复杂标识符
- ✅ 简洁性 - 代码清晰易懂
- ✅ 安全性 - 避免无限循环
这是图遍历算法中的标准做法，也是保证算法正确性和效率的关键设计！
访问未访邻接，适合路径枚举。 深度优先遍历是一种优先走到底、无路可走再回头的遍历方式
// === File: graph_dfs.cpp ===
/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList &graph, unordered_set<Vertex*> &visited,
vector<Vertex*> &res, Vertex* vet) {
res.push_back(vet); // 记录访问顶点
visited.emplace(vet); // 标记该顶点已被访问
// 遍历该顶点的所有邻接顶点
for (Vertex* adjVet : graph.adjList[vet]) {
if (visited.count(adjVet))
continue; // 跳过已被访问的顶点
// 递归访问邻接顶点
dfs(graph, visited, res, adjVet);
}
}
/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
vector<Vertex*> graphDFS(GraphAdjList &graph, Vertex* startVet) {
// 顶点遍历序列
vector<Vertex*> res;
// 哈希集合，用于记录已被访问过的顶点
unordered_set<Vertex*> visited;
dfs(graph, visited, res, startVet);
return res;
}笔记重点：非负权用Dijkstra，有负/全源用Floyd。假设无负环。
拓扑排序是对有向无环图(DAG)的所有顶点进行线性排序，使得对于任何从顶点u到顶点v的有向边(u, v)，在排序中u都在v的前面。
vector<int> topologicalSort(int n, vector<vector<int>>& edges) {
// 构建邻接表和入度数组
vector<vector<int>> graph(n);
vector<int> indegree(n, 0);
// 初始化图
for(auto& edge : edges) {
int u = edge[0], v = edge[1];
graph[u].push_back(v); // u → v
indegree[v]++; // v的入度+1
}
// 将所有入度为0的顶点加入队列
queue<int> q;
for(int i = 0; i < n; i++) {
if(indegree[i] == 0) {
q.push(i);
}
}
vector<int> result;
while(!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// 处理u的所有邻居
for(int v : graph[u]) {
indegree[v]--; // 删除边u→v，v入度-1
if(indegree[v] == 0) { // 如果v入度变为0
q.push(v); // 加入队列
}
}
}
// 检查是否有环
if(result.size() != n) {
return {}; // 存在环，无法拓扑排序
}
return result;
}vector<int> topologicalSortDFS(int n, vector<vector<int>>& edges) {
vector<vector<int>> graph(n);
for(auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
}
vector<int> result;
vector<int> visited(n, 0); // 0:未访问, 1:访问中, 2:已访问
for(int i = 0; i < n; i++) {
if(visited[i] == 0) {
if(!dfs(i, graph, visited, result)) {
return {}; // 有环
}
}
}
reverse(result.begin(), result.end());
return result;
}
bool dfs(int u, vector<vector<int>>& graph, vector<int>& visited, vector<int>& result) {
visited[u] = 1; // 标记为访问中
for(int v : graph[u]) {
if(visited[v] == 1) return false; // 发现环
if(visited[v] == 0) {
if(!dfs(v, graph, visited, result)) return false;
}
}
visited[u] = 2; // 标记为已访问
result.push_back(u);
return true;
}-
有向图 - 只能用于有向图
-
无环 - 图中不能有循环依赖
-
线性序 - 结果是顶点的一个线性排列
-
建图 - 构建邻接表和入度数组
-
找起点 - 所有入度为0的顶点入队
-
处理队列 - 出队、记录、更新邻居入度
-
检查环 - 结果数量是否等于顶点总数 拓扑排序是处理依赖关系问题的核心算法：
- ✅ 解决"先决条件"类问题
- ✅ 检测图中是否有环
- ✅ 为任务提供合理的执行顺序
- ✅ 时间复杂度优秀 O(V+E) 掌握拓扑排序对于解决LeetCode中很多图论问题（如207, 210, 329等）都非常有帮助！
https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/98390/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt 讲的很好 字典树（Trie，发音同"try"）是一种专门用于高效存储和检索字符串的树形数据结构。它也被称为前缀树、单词查找树。 ![[Pasted image 20251116144924.png]]
class TrieNode {
public:
vector<TrieNode*> children; // 子节点数组
bool isEnd; // 标记是否为单词结尾
TrieNode() : children(26, nullptr), isEnd(false) {}
};根节点
|
a (26个子节点，只用了a和b)
| \
p b
| \
p (isEnd) a
| \
l (isEnd) n
| \
e (isEnd) a
\
n
\
a (isEnd)void insert(string word) {
TrieNode* node = root;
for(char c : word) {
int index = c - 'a';
if(!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEnd = true; // 标记单词结束
}bool search(string word) {
TrieNode* node = root;
for(char c : word) {
int index = c - 'a';
if(!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEnd; // 必须正好是单词结尾
}bool startsWith(string prefix) {
TrieNode* node = root;
for(char c : prefix) {
int index = c - 'a';
if(!node->children[index]) {
return false;
}
node = node->children[index];
}
return true; // 只要前缀存在就返回true
}class Trie {
private:
struct TrieNode {
vector<TrieNode*> children;
bool isEnd;
TrieNode() : children(26, nullptr), isEnd(false) {}
};
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for(char c : word) {
int index = c - 'a';
if(!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEnd = true;
}
bool search(string word) {
TrieNode* node = root;
for(char c : word) {
int index = c - 'a';
if(!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEnd;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for(char c : prefix) {
int index = c - 'a';
if(!node->children[index]) {
return false;
}
node = node->children[index];
}
return true;
}
};自动补完，拼写检查，IP路由表，单词游戏
贪心：选dist最小未访节点，松弛邻接。笔记用优先队列优化O((V+E)logV)。
#include <queue>
typedef pair<int, int> PII; // dist, 节点
const int INF = 1e9;
int dist[maxv];
bool vis[maxv] = {false};
vector<PII> adj[maxv]; // pair<节点,权>
void dijkstra(int s, int n) {
fill(dist, dist + n, INF);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({0, s});
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}- 解释：vis选最小后标记，松弛更新。测试：节点0-1权1,0-2权3,1-2权1 → dist[2]=2。
动态规划：dist[i][j] = min(直达, 经k)。
int dist[maxv][maxv];
void floyd(int n) {
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] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}- 解释：O(V^3)，初始化dist[i][j]=g[i][j]。用于传递闭包。
无向连通加权图最小权子图（V-1边）。笔记两法：Prim（加点）、Kruskal（加边）。
从点集扩展，选最小边连未入点。
int prim(int n) {
bool vis[maxv] = {false};
int lowcost[maxv], total = 0;
fill(lowcost, lowcost + n, INF);
vis[0] = true;
for (int i = 1; i < n; i++) lowcost[i] = g[0][i]; // 假设矩阵g
for (int i = 1; i < n; i++) {
int minv = INF, u = -1;
for (int j = 0; j < n; j++)
if (!vis[j] && lowcost[j] < minv) { minv = lowcost[j]; u = j; }
if (u == -1) return -1; // 非连通
vis[u] = true; total += minv;
for (int j = 0; j < n; j++)
if (!vis[j] && g[u][j] < lowcost[j]) lowcost[j] = g[u][j];
}
return total;
}笔记需并查集（UF）防环：排序边，<阈值加边并union。
struct Edge { int u, v, w; } edges[maxe];
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int find(int x) { /* UF标准实现 */ }
void kruskal(int m, int n) {
sort(edges, edges + m, cmp);
int total = 0, cnt = 0;
for (int i = 0; i < m; i++) {
int u = find(edges[i].u), v = find(edges[i].v);
if (u != v) {
union(u, v); // 并查
total += edges[i].w;
if (++cnt == n-1) break;
}
}