专栏文章
图论算法
科技·工程参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mioyyi6t
- 此快照首次捕获于
- 2025/12/03 03:26 3 个月前
- 此快照最后确认于
- 2025/12/03 03:26 3 个月前
:恍然发现，集训已经过了了
由于这两天都学习的是图论算法其实是昨晚打了ABC，所以整合到了今天一天来写。
要学习图论算法，首先要了解什么是图
图分为节点和边，在日常的学习中，我们常简记为。特别的，如果一个图中任意两个结点都有路径相连，则称其为：连通图（无向） 或 强连通图（有向）。
数据篇：
图的存储：
主要依靠邻接矩阵和邻接表（还有慢慢淡出人们视线的链式前向星）来存储图
邻接矩阵依靠的是使用二维数组来存储，如果某两个点间没有路径，通常使用一个很大的数字来代替(如INT_MAX、0x7fffffffff)。我们便有了如下代码：
CPPint n, m;
int a[1010][1010];
int main()
{
// 初始化
for(int i = 1;i <= 1000; i++) {
a[i][j] = INT_MAX;
}
cin >> n >> m;
for(int i = 1;i <= m; i++) {
cin >> a[i][j];
// 若是无向图 则加上 a[j][i] = a[i][j] 即可
}
return 0;
}
领接矩阵的优点和缺点：
优点：便于存储和使用（较入门）
缺点：费空间，只有题目范围小的时候才能使用或只拿部分分（尤其指点多边少的情况）
邻接表一般使用一个动态数组来存储，其中是一个存储点（）和边权值()的结构体。本质上是链试存图，存储的是点能直接到达的点：
CPPstruct edge
{
int v, w;
};
vector<edge> e[maxn];
int main()
{
cin >> n >> m;
for(int i = 1;i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
e[a].push_back({b, c});
// 同样 无向图的加上 e[b].push_back({a, c}) 即可
}
return 0;
}
领接表的优点和缺点：
优点：可以处理大数据
缺点：用法较进阶，不易上手
图的存储中，需要特殊处理的是有无重边（有重复的、多余的边） 或 自环（单个结点的起点和终点都是自己）。代码就不在此实现了因为本蒟蒻特别的懒：D
算法篇
特此声明:由于算法代码较长，在此不一一展出，有感兴趣的大佬可自行代码或查阅。
拓扑排序
依次输出没有入度的点。
使用条件：有向无环图（）。
算法思路：1、选择一个没有入度的点；2、删除已遍历过的边和点。
最小生成树（）
首先我们要清楚：当一个无向连通图有个点，条边的话——它就是树！ 最小生成树算法实现的就是通过删除某些边和点，使最终的图变成一棵边权加起来最小的树。
主要算法有(克鲁斯卡尔)和(普利姆)算法。
算法是依次选取最短的边，如果形成环则舍弃，没有形成环就添加，时间复杂度为。
算法是依据随机一个起点，松弛其周围最近的边，再用下一个点继续松弛操作，直到所有的点都被遍历。所有被松弛的边和点即为该图的最小生成树。
最短路径问题
目前来说，最短路径问题较主流的由（迪杰斯特拉）算法、算法、（弗洛伊德）算法。
算法是目前图论中用途最广，适用题目最多（变形最方便），复杂度最稳定的一种算法，核心思想是取一个原点，遍历其与其他结点相连的边，并在后来的遍历中不断更新到其他结点的路径最小值。 同时，它的缺点也很明显：1、无法处理负边负环；2、题目需要满足贪心性质（；3、无法求最长路）。
算法是用途较为广泛，可以处理负边负环，但是时间复杂度不稳定（容易被卡）的一种算法。算法的核心逻辑是通过多层循环并剪枝优化，找到原点与各个结点间路径最小值的一种算法。
算法是逻辑与代码较简单，可以同时求多源最短路，但是时间复杂度较高的一种算法。算法结合动态规划，通过枚举结点与结点之间，比较之间插入另一个中继点与原路径长的关系，从而达到同时求出多源最短路的问题。
结语
今天也恰好是出中考成绩的一天，借用我的教练送给我的一句话：
分数代表过去，积极准备，开始新的挑战！
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...