一些基本概念
- 图
一个图 \(G=(V,E)\) 由顶点集 V 和边集 E 组成。每一条边就是一副顶点对\((u, v)\),其中 \(u,v \in V\)。顶点 u 和顶点 v 邻接当且仅当 \((u,v) \in E\)。有时候边还具有权重。 - 有向图和无向图
如果图的顶点对是有序的,那么该图称为有向图。否则是无向图。 - 自环
如果图含有一条从一个顶点到它自身的边\((v, v)\),那么 \(v,v\) 有时候叫做一个自环。 - 路径
图中的一条路径是一个顶点序列 \(w_1, w_2, w_3, ..., w_N\) 使得 \((w_i, w_i+1) \in E\)。 - 圈(环路)
如果一条路径满足 \(w_1=w_N\) 且长至少为1,这条路径被称之为圈。有向无圈图称为DAG。 - 欧拉环路
经过图中各边一次且恰好一次的环路。 - 哈密顿环路
经过图中各顶点一次且恰好一次的环路。 - 强连通的
如果再一个有向图中从每一个顶点到每个其他顶点都存在一条路径,则称该有向图为强连通的。 - 完全图
每一对顶点间都存在一条边的图。
图的表示法
邻接矩阵
邻接矩阵说白了就是二维数组,比如 \(A[u][v]\),如果 \((u,v) \in E\),则 \(A[u][v]=1\),否则 \(A[u][v]=0\),如果有权重,则 \(A[u][v]=w\),其中 \(w\) 是权重值。
领接表
邻接表是对每一个顶点,我们使用一个表存放所有邻接的顶点。这句话可能说的不明白,但是用 C++ 的数据结构来解释的话就很清楚了,我们可以使用如下代码来代表邻接表:
#include <unordered_map>
#include <vector>
unordered_map<int, vector<int>> edges;
领接表其实就是哈希表,它的键是顶点编号 idx,值是顶点向量 vec,表示与顶点 idx 相邻的顶点集 vec。
为了更直观,下图展示了邻接表的形式(显然可以看出该邻接表表示的是有向图):
![](/i/l/?n=23&i=blog/3062571/202302/3062571-20230211185429639-41653794.png)
一般情况下,稠密图使用邻接矩阵,稀疏图使用邻接表。两者之间没有规定必须使用哪种数据结构,因此需要因情形而异。
常见的关于图的算法
深度优先搜索(DFS)
void DFS(unordered_map<int, vector<int>>& edges, int u,
unordered_set<int>& visited, vector<int>& path) {
if (visited.count(u)) return;
path.push_back(u);
visited.insert(u);
for (auto& v : edges[u]) {
DFS(edges, v, visited, path);
}
}
广度优先搜索(BFS)
树可以通过BFS来访问,同理图也可以。它们的算法思想是一致的:首先访问起始顶点 v 并标记为已访问,然后访问 v 的邻接顶点 u,并将未访问的邻接顶点放入队列;然后从队列取出下一个顶点并按照前面所述规则访问顶点,直到队列没有顶点要访问。参考代码如下:
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
vector<int> BFS(unordered_map<int, vector<int>>& edges, int srcPoint) {
unordered_set<int> visited;
vector<int> res;
queue<int> q;
q.push(srcPoint);
while (!q.empty()) {
int u = q.front();
q.pop();
visited.insert(u);
res.push_back(u);
for (auto& v : edges[u]) {
if (!visited.count(v)) {
q.push(v);
}
}
}
return res;
}
拓扑排序
拓扑排序一般是针对有向无圈图。这个算法涉及到两个概念,一个叫入度,一个叫出度。对顶点 \(v\) 来说,如果没有任意边 \((u, v) \in E\),则入度为0,否则有几条边就是入度为几;相似地,如果没有任意边 \((v, u) \in E\),则出度为0,否则几条边就是出度为几。
如下图所示:
顶点 \(v_3\) 的入度为2,出度为1。
好了,概念说完了,接着说拓扑排序的原理。
拓扑排序主要使用邻接表和 queue 来实现。首先,对每一个顶点计算入度,然后将入度为0的顶点放入到一个初始为空的 queue 里。当 queue 不空时,访问 front 顶点元素 v 并从 queue 删除,然后将与 v 邻接的所有顶点的入度减1,如果某个顶点 u 入度变成0,则将 u 放入到 queue 里。算法执行直到 queue 为空。从这个过程可以看出,拓扑排序实质上就是顶点出队列的顺序。
思想理解了,该 show your code 啦!代码如下:
vector<int> TopoSort(unordered_map<int, vector<int>>& edges, int n) {
vector<int> indeg(n, 0);
for (int i = 0; i < n; i++) {
for (auto& v : edges[i]) {
indeg[v]++;
}
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) q.push(i);
}
vector<int> res;
while (!q.empty()) {
auto u = q.front();
q.pop();
res.push_back(u);
for (auto& v : edges[u]) {
indeg[v]--;
if (indeg[v] == 0) q.push(v);
}
}
return res;
}
最短路径
单源最短路径
问题描述:给定一个权重图 \(G=(V,E)\) 和一个特定顶点 \(s\) 作为输入,找出从 \(s\) 到 G 中每一个其他顶点的最短路径。
对于边的权重值有3种情况:
- 所有边权重都一样,一般这种情况使用广度优先算法(BFS)即可。
- 边的权重不一样并且没有负数权重,一般这种情况使用*Dijkstra**算法。
- 如果边的权重有负数,这种情况使用xx算法。