【算法模板】图论基础算法

文章目录

图论算法基础模板
- - 树与图的存储
  - - 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)

深度优先搜索是一种通过递归或栈实现的遍历算法。从起始顶点开始，尽可能深地访问每个顶点，直到到达终点或无法继续深入。

算法步骤：
1. 从起始顶点开始，将其标记为已访问。
2. 对于起始顶点的每个邻接顶点，如果该邻接顶点未被访问，则递归调用 DFS 函数进行访问。
3. 重复步骤 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)

宽度优先搜索是一种通过队列实现的遍历算法。从起始顶点开始，逐层地访问与其相邻的顶点，确保每个顶点只被访问一次。

算法步骤：
1. 将起始顶点放入队列，并标记为已访问。
2. 从队列中取出一个顶点，并访问其所有未被访问的邻接顶点，将其放入队列并标记为已访问。
3. 重复步骤 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 的前面。

算法步骤：
1. 计算每个顶点的入度，即指向该顶点的边的数量。
2. 将所有入度为 0 的顶点加入拓扑序列，并将与这些顶点相邻的边的入度减 1。
3. 重复步骤 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 算法是一种贪心算法，用于求解单源最短路径问题。从起始顶点开始，每次选择距离最短的顶点进行扩展，并更新其他顶点的距离。

算法步骤：
1. 初始化距离数组，将起始顶点到其他顶点的距离初始化为无穷大。
2. 将起始顶点的距离设置为 0，并将其加入集合。
3. 对于集合中的每个顶点，更新其相邻顶点的距离。
4. 重复步骤 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 算法，旨在加快寻找当前距离最小的顶点的过程。通过使用优先队列（通常实现为最小堆），算法可以在每次迭代中快速找到下一个最优的顶点，而不是遍历所有顶点进行比较。

算法步骤：
1. 初始化距离数组，将所有顶点的距离初始化为无穷大，表示当前距离未知。
2. 将起始顶点加入优先队列，将起始顶点的距离设置为 0，并将其加入优先队列中。
3. 从优先队列中取出距离最小的顶点，每次从优先队列中取出距离最小的顶点，这个顶点的距离已经确定为最小值。
4. 更新相邻顶点的距离，对于当前顶点的所有相邻顶点，如果通过当前顶点到达它们的路径比已知的距离更短，则更新它们的距离，并将其加入优先队列中。
5. 重复步骤 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 算法是一种用于解决单源最短路径问题的算法，能够处理带有负权边的图。通过动态规划的思想，算法不断迭代缩小顶点到达目标顶点的距离估计，直到收敛为止。

算法步骤：‘
1. 初始化距离数组，将起始顶点到其他顶点的距离初始化为无穷大，除了起始顶点本身的距离为 0。
2. 进行 n-1 次松弛操作，对于每一条边 (u, v)，如果通过顶点 u 到达顶点 v的路径比当前已知的路径更短，则更新顶点 v的距离为通过顶点 u 到达 v 的距离。
3. 检查负权环，进行了 n-1 次松弛操作后，再进行一次松弛操作。如果在这一次操作中仍然发生了距离的更新，则说明图中存在负权环。
4. 返回最短路径，如果不存在负权环，最终得到的距离数组就是起始顶点到各个顶点的最短路径长度。
时间复杂度：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)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

匈牙利算法

匈牙利算法是一种用于求解二分图最大匹配的经典算法。最大匹配是指在一个二分图中，找到尽可能多的边，使得每个节点最多只与一个节点相连。

算法步骤：

初始化一个空的匹配集合。
从左边的未匹配节点开始，依次寻找与其相邻的右边未匹配节点。
如果找到了未匹配的右边节点，则将其加入匹配集合中，并继续尝试匹配其他节点。
如果无法找到未匹配的右边节点，则回溯到之前的匹配状态，并尝试匹配其他左边节点。
重复步骤2到步骤4，直到所有左边节点都尝试过匹配。

匈牙利算法通常使用DFS或BFS进行实现，其中DFS更为常见。其时间复杂度为O(nm)，其中n表示左边节点数，m表示右边节点数。

时间复杂度：O(nm)，其中 n1 表示第一个集合中的点数，n2 表示第二个集合中的点数。

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {