图论基础与建图
- 图的定义
图是由若干给定的顶点及连接两顶点的边所构成的图形，顶点用于代表事物，连接两顶点的边用于表示两个事物间的特定关系。 - 建图的概念
建图是指找到合适的方法将图表示出来。
图的存储方法
直接存边
- 存储方式：直接使用一个数组，将边的起点与终点信息存储。
- 代码实现：
#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着色为c
for(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; // 起点到自身的距离为0
bool 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得到更短的距离到v
if(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 算法
最短路算法进阶：
最小生成树（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; // 已加入顶点数加1
res += 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++; // 边计数器加1
g[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++; // 已选边数加1
ans += 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;
}