[算法模板] 图论基本算法
文章目录
- 图论算法基础模板
- 树与图的存储
- 1. 邻接矩阵:
- 2. 邻接表:
- 树与图的遍历
- (1)深度优先搜索 (DFS)
- 深度优先遍历 (DFS)
- (2)宽度优先搜索 (BFS)
- 宽度优先遍历 (BFS)
- 拓扑排序
- 朴素Dijkstra算法
- 堆优化版Dijkstra算法
- Bellman-Ford算法
- SPFA算法
- SPFA判断图中是否存在负环
- Floyd算法
- 朴素版Prim算法
- Kruskal算法
- 染色法判别二分图
- 匈牙利算法
图论算法基础模板
- 树是一种特殊的图,因此它们可以使用相同的存储方式。我们这里主要考虑有向图的存储方法。
树与图的存储
树是一种特殊的图,因此它们可以使用相同的存储方式。我们这里主要考虑有向图的存储方法。
1. 邻接矩阵:
在邻接矩阵中,使用二维数组 g[a][b]
来表示边 a->b
。
2. 邻接表:
对于每个点 k
,开一个单链表,存储所有可以从 k
出发到达的点。h[k]
存储这个单链表的头结点。
添加一条边 a->b
时,将 b
添加到以 a
为头结点的链表中。
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
这种存储方式对于表示树和图都是有效的,通过邻接表的形式可以灵活地添加和删除边,适用于各种图论算法的实现。
树与图的遍历
(1)深度优先搜索 (DFS)
深度优先搜索是一种通过递归或栈实现的遍历算法。从起始顶点开始,尽可能深地访问每个顶点,直到到达终点或无法继续深入。
-
算法步骤:
- 从起始顶点开始,将其标记为已访问。
- 对于起始顶点的每个邻接顶点,如果该邻接顶点未被访问,则递归调用 DFS 函数进行访问。
- 重复步骤 2,直到无法继续深入为止。
-
时间复杂度:O(n+m),其中
n
表示点数,m
表示边数。
深度优先遍历 (DFS)
void dfs(int u)
{
st[u] = true; // st[u] 表示点 u 已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2)宽度优先搜索 (BFS)
宽度优先搜索是一种通过队列实现的遍历算法。从起始顶点开始,逐层地访问与其相邻的顶点,确保每个顶点只被访问一次。
- 算法步骤:
- 将起始顶点放入队列,并标记为已访问。
- 从队列中取出一个顶点,并访问其所有未被访问的邻接顶点,将其放入队列并标记为已访问。
- 重复步骤 2,直到队列为空。
- 时间复杂度:O(n+m),其中
n
表示点数,m
表示边数。
宽度优先遍历 (BFS)
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点 j 已经被遍历过
q.push(j);
}
}
}
拓扑排序
拓扑排序是对有向无环图进行排序的算法,它确定顶点的线性顺序,使得对于图中的每一对有向边 (u, v)
,顶点 u
都排在顶点 v
的前面。
-
算法步骤:
- 计算每个顶点的入度,即指向该顶点的边的数量。
- 将所有入度为 0 的顶点加入拓扑序列,并将与这些顶点相邻的边的入度减 1。
- 重复步骤 2,直到所有顶点都加入拓扑序列或者不存在入度为 0 的顶点为止。
-
时间复杂度:O(n+m),其中
n
表示点数,m
表示边数。
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点 i 的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[++tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[++tt] = j;
}
}
// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}
朴素Dijkstra算法
朴素 Dijkstra 算法是一种贪心算法,用于求解单源最短路径问题。从起始顶点开始,每次选择距离最短的顶点进行扩展,并更新其他顶点的距离。
-
算法步骤:
- 初始化距离数组,将起始顶点到其他顶点的距离初始化为无穷大。
- 将起始顶点的距离设置为 0,并将其加入集合。
- 对于集合中的每个顶点,更新其相邻顶点的距离。
- 重复步骤 3,直到集合为空。
-
时间复杂度:O(n^2+m),其中
n
表示点数,m
表示边数。
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用 t 更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化版Dijkstra算法
堆优化 Dijkstra 算法是一种改进的 Dijkstra 算法,旨在加快寻找当前距离最小的顶点的过程。通过使用优先队列(通常实现为最小堆),算法可以在每次迭代中快速找到下一个最优的顶点,而不是遍历所有顶点进行比较。
-
算法步骤:
- 初始化距离数组, 将所有顶点的距离初始化为无穷大,表示当前距离未知。
- 将起始顶点加入优先队列, 将起始顶点的距离设置为 0,并将其加入优先队列中。
- 从优先队列中取出距离最小的顶点,每次从优先队列中取出距离最小的顶点,这个顶点的距离已经确定为最小值。
- 更新相邻顶点的距离,对于当前顶点的所有相邻顶点,如果通过当前顶点到达它们的路径比已知的距离更短,则更新它们的距离,并将其加入优先队列中。
- 重复步骤 3 和步骤 4: 不断从优先队列中取出距离最小的顶点,并更新其相邻顶点的距离,直到优先队列为空。
-
时间复杂度:O(mlogn),其中
n
表示点数,m
表示边数。
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离,second存储节点编号
while (!heap.empty())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Bellman-Ford算法
Bellman-Ford 算法是一种用于解决单源最短路径问题的算法,能够处理带有负权边的图。通过动态规划的思想,算法不断迭代缩小顶点到达目标顶点的距离估计,直到收敛为止。
-
算法步骤:‘
- 初始化距离数组, 将起始顶点到其他顶点的距离初始化为无穷大,除了起始顶点本身的距离为 0。
- 进行 n-1 次松弛操作,对于每一条边 (u, v),如果通过顶点 u 到达顶点 v的路径比当前已知的路径更短,则更新顶点 v的距离为通过顶点 u 到达 v 的距离。
- 检查负权环, 进行了 n-1 次松弛操作后,再进行一次松弛操作。如果在这一次操作中仍然发生了距离的更新,则说明图中存在负权环。
- 返回最短路径,如果不存在负权环,最终得到的距离数组就是起始顶点到各个顶点的最短路径长度。
-
时间复杂度:O(nm),其中
n
表示点数,m
表示边数。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
SPFA算法
SPFA(Shortest Path Faster Algorithm)是一种单源最短路径算法,用于求解带有负权边但无负权环的图的最短路径。其基本思想是类似于Bellman-Ford算法,但是SPFA通过维护一个队列来减少不必要的松弛操作,从而提高了效率。
算法步骤:
- 将起点加入队列,并标记为已访问。
- 不断从队首取出一个点,对其相邻的未访问点进行松弛操作,更新最短路径。
- 如果某个点的最短路径发生了改变,且该点不在队列中,则将其加入队列,并标记为已访问。
- 重复步骤2和步骤3,直到队列为空。
如果在算法执行过程中,某个点入队次数超过了n次,说明存在负权环。
- 时间复杂度:平均情况下 O(m),最坏情况下 O(nm),其中
n
表示点数,m
表示边数。
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (!q.empty())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在 j,则不需要将 j 重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
SPFA判断图中是否存在负环
- 时间复杂度:O(nm),其中
n
表示点数,m
表示边数。
bool spfa()
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (!q.empty())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到 x 的最短路中包含至少 n 个点(不包括自己),则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
Floyd算法
Floyd算法是一种经典的多源最短路径算法,用于求解图中任意两点之间的最短路径。其核心思想是动态规划,通过中转点的引入逐步优化路径的长度。
算法步骤:
- 初始化任意两点之间的最短路径长度。
- 逐步考虑每个点作为中转点时,更新任意两点之间的最短路径长度。
- 重复步骤2,直到所有点都考虑过。
Floyd算法的核心操作是三重循环,分别遍历所有点对和中转点,通过比较经过中转点和不经过中转点的路径长度来更新最短路径。
- 时间复杂度:O(n^3),其中
n
表示点数。
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
朴素版Prim算法
Prim算法是一种用于求解最小生成树的贪心算法,其基本思想是从一个初始点出发,逐步选取与当前最小生成树连接的最短边所连接的点,直到所有点都被连接为止。
算法步骤:
- 选择一个初始点作为最小生成树的根节点。
- 从已选取的点集合中选取与之相邻的边中权值最小的边所连接的点,加入到最小生成树中。
- 重复步骤2,直到所有点都被加入到最小生成树中。
Prim算法可以通过邻接矩阵或邻接表来实现。邻接矩阵的实现简单直观,但对于稀疏图效率较低,而邻接表适合稀疏图的情况。
- 时间复杂度:O(n^2+m),其中
n
表示点数,m
表示边数。
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == 0x3f3f3f3f) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
Kruskal算法
Kruskal算法是一种用于求解最小生成树的贪心算法,其基本思想是先将所有边按照权值从小到大排序,然后逐步选取权值最小且不构成环的边加入到最小生成树中。
算法步骤:
- 将所有边按照权值从小到大排序。
- 依次考虑每条边,如果该边连接的两个端点不在同一连通块中,则将该边加入到最小生成树中,并将两个端点合并为一个连通块。
- 重复步骤2,直到所有点都被连接为止。
Kruskal算法通常使用并查集来实现,用于判断两个点是否属于同一个连通块,并在加入边时实现快速的合并操作。
- 时间复杂度:O(mlogm),其中
n
表示点数,m
表示边数。
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
染色法判别二分图
染色法是一种用于判别图是否为二分图的常用算法。二分图是一种特殊的图,可以将所有节点分为两个不相交的集合,并且图中的每条边都连接一端点属于其中一个集合,另一端点属于另一个集合。染色法通过遍历图中的节点,并对每个节点进行染色,使得相邻节点的颜色不同,如果成功染色,则说明图是二分图。
算法步骤:
- 从任意一个未染色的节点开始,将其染色为0。
- 遍历该节点的所有相邻节点,如果相邻节点未被染色,则将其染色为与当前节点不同的颜色(比如1)。
- 对相邻节点递归执行步骤2。
- 如果在染色的过程中出现了相邻节点颜色相同的情况,则说明图不是二分图。
染色法的时间复杂度为O(n+m),其中n表示节点数,m表示边数。它的实现比较简单,通常使用递归或队列等方式进行遍历和染色操作。
- 时间复杂度:O(n+m),其中
n
表示点数,m
表示边数。
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c
上一篇:
架构师系列--消息中间件(15)--kafka 业务实践
下一篇:
常春藤四子棋设计模式笔记--命令模式