图论基础算法入门笔记
图论基础与建图
- 图的定义
图是由若干给定的顶点及连接两顶点的边所构成的图形，顶点用于代表事物，连接两顶点的边用于表示两个事物间的特定关系。 - 建图的概念
建图是指找到合适的方法将图表示出来。
图的存储方法
直接存边
- 存储方式：直接使用一个数组，将边的起点与终点信息存储。
- 代码实现：
#include<bits/stdc++.h>
using namespace std;
struct Edge{ int u,v; // 边的起点和终点
};
int n,m; // n为顶点数，m为边数
vector<Edge> e; // 存储边的向量
vector<bool> vis; // 标记顶点是否被访问void dfs(int u) {if(vis[u]) return; // 如果顶点已访问，直接返回vis[u] = true; // 标记顶点为已访问for(int i=1;i<=m;i++) if(e[i].u==u) dfs(e[i].v); // 遍历以u为起点的边，递归访问终点
}
特点：这种存储方法的遍历效率低下，一般用于需要对边权进行排序的 Kruskal 算法。
邻接矩阵
- 存储方式：使用一个二维数组保存边，如果是带权图可以存储边权。
- 代码实现：
#include<bits/stdc++.h>
using namespace std;
int n,m; // n为顶点数，m为边数
vector<bool> vis; // 标记顶点是否被访问
vector<vector<bool>> G; // 邻接矩阵void dfs(int u) {if(vis[u]) return ; // 如果顶点已访问，直接返回vis[u] = true; // 标记顶点为已访问for(int v=1; v<=n;v++) if(G[u][v]) dfs(v); // 遍历与u相连的顶点，递归访问
}int main() {cin>>n>>m; // 输入顶点数和边数for(int i=1;i<=m;i++) {int u,v; // 输入边的起点和终点//int t; // 若为带权图，此处存储权值cin>>u>>v; //cin>>t;G[u][v] = 1; // 如果是带权图则记录权值}
}
特点：邻接矩阵对于稀疏图的效率较低，一般用于稠密图。
邻接表
- 存储方式：通过存储各点的所有出边信息表示图。
- 代码实现：
#include<bits/stdc++.h>
using namespace std;
int n,m; // n为顶点数，m为边数
vector<bool> vis; // 标记顶点是否被访问
vector<vector<int>> G; // 邻接表// 查找是否存在从u到v的边
bool find_edge(int u,int v) { for(int i=0;i<=G[u].size();i++) if(G[u][i]==v) return true; return false;
}void dfs(int u) { if(vis[u]==true) return; // 如果顶点已访问，直接返回vis[u]=true; // 标记顶点为已访问for(int i=0;i<G[u].size();i++) dfs(G[u][i]); // 遍历u的所有出边，递归访问终点
}int main() { cin>>n>>m; // 输入顶点数和边数vis.resize(n+1); // 调整vis的大小G.resize(n+1); // 调整邻接表的大小for(int i=1;i<=m;i++) {int u,v; // 输入边的起点和终点cin>>u>>v; G[u].push_back(v); // 将边添加到邻接表中}return 0;
}二分图判定
- 二分图定义
二分图，又称二部图，是一类结构特殊的图，它的顶点集可以划分为两个互不相交的子集，使得图中的每条边都连接这两个集合之间的一对点，而不会连接同一集合内部的点。 - 图着色问题
把相邻顶点染成不同颜色的问题叫做图着色问题。 - 二分图判定算法
算法思路：通过深度优先搜索对图进行着色，若相邻顶点颜色相同则不是二分图。
简单来说，就是只有2种颜色，依次对层级（深度）进行两种染色，假如是一颗树，他就是二分图，每一层深度颜色交替的染。如果此时第三深度的节点和第一深度的节点有连线，那么很明显颜色一样，此时判断颜色一样，所以不是二分图了（二分图不止有树哦）
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> G; // 邻接表
vector<int> color,vis; // color存储顶点颜色，vis标记顶点是否被访问
int n,m; // n为顶点数，m为边数// 深度优先搜索进行二分图判定
bool dfs(int v,int c) { color[v]=c; // 给顶点v着色为cfor(int i=0;i<G[v].size();i++) {// 如果相邻顶点颜色与v相同，不是二分图if(color[G[v][i]]==c) return false; // 如果相邻顶点未着色，递归着色并判断if(color[G[v][i]]==0&&!dfs(G[v][i],-c)) return true; }return true;
}void solve() { for(int i=0;i<n;i++) {if(color[i]==0) { // 如果顶点未着色if(!dfs(i,1)) { // 从该顶点开始着色判定cout<<"NO"<<endl; // 不是二分图return; }}}cout<<"YES"<<endl; // 是二分图return;
}最短路问题
单源最短路定义
单源最短路是固定一个起点，求它到其他点的最短路问题
Floyd 算法
算法特点：Floyd 可以处理无论有向无向还是边是正是负的图，但最短路必须存在，且不能有负环。
算法核心：（这里k的空间可以不开，因为都是顺次更新，不开没有影响）
for (k = 1; k <= n; k++) {for (x = 1; x <= n; x++) {for (y = 1; y <= n; y++) {// 状态转移方程，f[k][x][y]表示经过前k个顶点，x到y的最短距离f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);//是经过k还是不经过k小f[x][y] = min(f[x][y], f[x][k] + f[k][y]);}}
}Bellman-Ford 算法
算法原理：通过边的松弛操作更新最短距离，公式为dis[i]=min(dis[i],dis[j]+e[j,i])，其中dis[i]是从起点 s 到顶点 i 的最短距离，e[j,i]是 j 到 i 的边权。
算法特点：这种算法不能用于负环。
代码实现：
#include<bits/stdc++.h>
using namespace std;
struct Edge { int u,v,w; // 边的起点、终点和权值
};
vector<Edge> e; // 存储边的向量
int dis[MAX_N],u,v,w; // dis存储最短距离，u、v、w为边的信息
const int INF = 0x3f3f3f; // 表示无穷大// Bellman-Ford算法
bool bellmanford(int n, int s) { memset(dis, 0x3f, (n + 1) * sizeof(int)); // 初始化最短距离为无穷大dis[s] = 0; // 起点到自身的距离为0bool flag = false; // 标志是否发生更新操作for (int i = 1; i <= n; i++) {flag = false;for (int j = 0; j < e.size(); j++) { // 对边进行遍历u = e[j].u, v = e[j].v, w = e[j].w;if (dis[u] == INF) continue; // 如果起点不可达，跳过// 如果通过当前边可以得到更短的距离，更新最短距离if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;flag = true; // 标记发生了更新}}// 没有可以更新的边时就停止算法if (!flag) break;}return flag;
}
SPFA 算法（判负环）
算法核心思想：只有上一次被更新过的节点，其下一次更新的路径才有可能成为最短路，因此用队列维护有意义发生下一次更新的节点。
负环判定：SPFA 也可以用于判断 s 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 s 点可以抵达一个负环。
ps：没有负环建议不要用，容易被卡数据
代码实现：
#include<bits/stdc++.h>
using namespace std;
struct Edge { int v,w; // 边的终点和权值
};
vector<Edge> e[MAX_N]; // 邻接表存储边
int dis[MAX_N],cnt[MAX_N],vis[MAX_N]; // dis存储最短距离，cnt记录路径边数，vis标记是否在队列中
queue<int> q; // 队列用于维护待更新的节点bool spfa(int n,int s) { memset(dis,0x3f,(n+1)*sizeof(int)); // 初始化最短距离为无穷大dis[s] = 0,vis[s]=1; // 起点距离为0，标记为在队列中q.push(s); // 起点入队while(!q.empty()) {int u = q.front(); // 取出队首元素q.pop(); vis[u] = 0; // 标记为不在队列中for(auto ed : e[u]) { // 遍历u的所有出边int v = ed.v, w=ed.w; // 边的终点和权值// 如果可以通过u得到更短的距离到vif(dis[v]>dis[u]+w) {dis[v]=dis[u] + w; // 更新最短距离cnt[v] = cnt[u]+1; // 路径边数加1// 如果路径边数达到n，说明存在负环if(cnt[v]>=n) return false; // 如果v不在队列中，加入队列if(!vis[v]) q.push(v),vis[v] = 1; }}}return true;
}
Dijkstra 算法
Dijkstra 算法#图论-CSDN博客
最短路算法进阶：
分层图最短路（模板）-CSDN博客
最小生成树（MST）
Prim 算法
算法核心思想：加点法，每次选择一个距离最小的节点，用其更新新的边和到其他节点的距离，可使用优先队列进行优化。
代码实现：
#include<bits/stdc++.h>
using namespace std;
struct E { int v, w, x; // v为终点，w为权值，x为下一条边的索引
} e[MAX_M];
int n, m, h[MAX_N], cnte; // n为顶点数，m为边数，h[u]表示以u为起点的第一条边的索引，cnte为边计数器// 添加边
void adde(int u, int v, int w) { e[++cnte] = E{v, w, h[u]}, h[u] = cnte;
} struct S { int u, d; // 顶点和距离
};
bool operator<(const S &x, const S &y) { return x.d > y.d; // 优先队列比较函数，小根堆
}
priority_queue<S> q; // 小根堆优先队列
int dis[MAX_N]; // 存储到各顶点的距离
bool vis[MAX_N]; // 标记顶点是否已加入生成树
int res = 0, cnt = 0; // res为最小生成树的权值和，cnt为已加入的顶点数void Prim() { memset(dis, 0x3f, sizeof(dis)); // 初始化距离为无穷大dis[1] = 0; // 从顶点1开始q.push({1, 0}); // 顶点1入队while (!q.empty()) {if (cnt >= n) break; // 所有顶点已加入，结束int u = q.top().u, d = q.top().d; // 取出距离最小的顶点q.pop(); if (vis[u]) continue; // 如果已加入生成树，跳过vis[u] = true; // 标记为已加入生成树++cnt; // 已加入顶点数加1res += d; // 累加权值for (int i = h[u]; i!=0 ; i = e[i].x) { // 遍历u的所有出边int v = e[i].v, w = e[i].w; // 边的终点和权值// 如果通过u可以得到到v的更短距离if (w < dis[v]) {dis[v] = w; // 更新距离q.push({v, w}); // 将v入队}}}
}
Kruskal 算法
算法核心思想：与 Prim 不同，Kruskal 的基本思想是从小到大加入边
#include <algorithm>
#include <iostream>
using namespace std;
int fa[1010]; // 定义并查集父节点数组，用于维护连通性
int n, m, k; // n为顶点数，m为边数，k为目标连通块数量
struct edge { int u, v, w; // 边的起点、终点和权值
};
int l;
edge g[10010]; // 存储所有边的数组// 添加边到数组
void add(int u, int v, int w) { l++; // 边计数器加1g[l].u = u; // 记录起点g[l].v = v; // 记录终点g[l].w = w; // 记录权值
} // 并查集查找根节点（带路径压缩）
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); // 若x是根节点则返回自身，否则递归查找并压缩路径
} // 合并两个连通块
void Merge(int x, int y) { x = findroot(x); // 找到x的根节点y = findroot(y); // 找到y的根节点fa[x] = y; // 合并两个连通块
} // 边权比较函数，用于排序
bool cmp(edge A, edge B) { return A.w < B.w; // 按边权从小到大排序
} void kruskal() { int tot = 0; // 已选边数计数器int ans = 0; // 最小生成树总权值// 按边权从小到大排序所有边sort(g + 1, g + m + 1, cmp); for (int i = 1; i <= m; i++) { int xr = findroot(g[i].u); // 查找边起点的根节点int yr = findroot(g[i].v); // 查找边终点的根节点if (xr != yr) { // 若两端点不在同一连通块Merge(xr, yr); // 合并连通块tot++; // 已选边数加1ans += g[i].w; // 累加边权// 当连通块数量达到要求时（n-k条边）if (tot >= (n - k)) { cout << ans << '\n'; // 输出总权值return;}}}cout << "No Answer\n"; // 无法形成满足条件的生成树
} int main() { cin >> n >> m >> k; // 输入顶点数、边数、目标连通块数// 初始化并查集，每个节点的父节点为自身for (int i = 1; i <= n; i++) { fa[i] = i;}for (int i = 1; i <= m; i++) { int u, v, w; // 输入边的起点、终点、权值cin >> u >> v >> w;add(u, v, w); // 添加边到数组}kruskal(); // 执行Kruskal算法return 0;
}Tarjan
Tarjan 算法的两种用法-CSDN博客