一些基本概念
- 图
一个图 \(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。
为了更直观，下图展示了邻接表的形式(显然可以看出该邻接表表示的是有向图)：
一般情况下，稠密图使用邻接矩阵，稀疏图使用邻接表。两者之间没有规定必须使用哪种数据结构，因此需要因情形而异。
常见的关于图的算法
深度优先搜索(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算法。