图论算法

Fish_Chen · 2025-07-06 20:03:04 · 科技·工程

Day 5:恍然发现，集训已经过了\frac 1 3了

由于这两天都学习的是图论算法其实是昨晚打了ABC，所以整合到了今天一天来写。

要学习图论算法，首先要了解什么是图

图分为节点和边，在日常的学习中，我们常简记为G = (V, E)。特别的，如果一个图中任意两个结点都有路径相连，则称其为：连通图（无向） 或 强连通图（有向）。

数据篇：

图的存储：

主要依靠邻接矩阵和邻接表（还有慢慢淡出人们视线的链式前向星）来存储图

邻接矩阵依靠的是使用二维数组来存储，如果某两个点间没有路径，通常使用一个很大的数字来代替(如INT_MAX、0x7fffffffff)。我们便有了如下代码：

int 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;
}

领接矩阵的优点和缺点：

优点：便于存储和使用（较入门）

缺点：费空间，只有题目范围小的时候才能使用或只拿部分分（尤其指点多边少的情况）

邻接表一般使用一个动态数组Vector<edge> e[maxn]来存储，其中edge是一个存储点（v）和边权值(w)的结构体。本质上是链试存图，存储的是点能直接到达的点：

struct 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

算法篇

特此声明:由于算法代码较长，在此不一一展出，有感兴趣的大佬可自行代码或查阅。

拓扑排序

依次输出没有入度的点。

使用条件：有向无环图（DAG）。

算法思路：1、选择一个没有入度的点；2、删除已遍历过的边和点。

最小生成树（MST）

首先我们要清楚：当一个无向连通图有n个点，（n-1）条边的话——它就是树！ 最小生成树算法实现的就是通过删除某些边和点，使最终的图变成一棵边权加起来最小的树。

主要算法有Kruskal(克鲁斯卡尔)和Prim(普利姆)算法。