---
url: /algo/at12d4gj/index.md
---
::: warning 警告
本模板为了便于理解，包含了大量的详细注释以及规范的 `std::` 命名空间前缀。在您将代码复制并提交至相关竞赛或评测平台前，请务必根据个人的编程习惯进行调整，重点建议删除冗余注释并精简代码风格。保留明显的模板特征极易被系统的查重算法或 AIGC 监测机制误标为“人工智能生成内容”，从而对您的评审进度或最终成绩产生不利影响。
:::

## 邻接矩阵

使用一个二维数组 `adj` 来存边，其中 `adj[u][v]` 为 1 表示存在 $u$ 到 $v$ 的边，为 0 表示不存在。如果是带边权的图，可以在 `adj[u][v]` 中存储 $u$ 到 $v$ 的边的边权。

```cpp title="adjMatrix.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 初始化 n 行 m 列，所有元素为 0
    int n = 3, m = 4;
    vector<vector<int>> matrix(n, vector<int>(m, 0));

    for (int i = 1; i <= m; ++i)
    {
        int u, v, p;
        cin >> u >> v >> p;
        matrix[u][v] = p; // 从 u 到 v 权值为 p
    }
}
```

## 邻接表

由于邻接表在附带信息存图中很有用处，所以后面的算法模板都以邻接表为例（虽然副社长 Timothyst 最喜欢的是链式前向星存图）。

假设给定下面的这个图：

下面是具体代码实现过程，使用 `class` 封装，简单的添加信息在 `createGraph()` 函数内。如果使用 `class` 建图，参照 `main` 函数。

```cpp title="adjTable.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;

// 竞赛用图的简化实现
class Graph
{
private:
    int n;                              // 顶点数
    vector<vector<pair<int, int>>> adj; // 邻接表 (to, weight)
    vector<bool> directed;              // 标记边是否有向

public:
    // 构造函数：初始化n个顶点
    Graph(int size) : n(size), adj(size), directed(size) {}

    // 添加有向边
    void addDirectedEdge(int u, int v, int w = 1)
    {
        adj[u].push_back({v, w});
        directed[u] = true;
    }

    // 添加无向边
    void addUndirectedEdge(int u, int v, int w = 1)
    {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        directed[u] = false;
        directed[v] = false;
    }

    // 获取邻接表
    const vector<vector<pair<int, int>>> &getAdj() const
    {
        return adj;
    }

    // 获取顶点数
    int getSize() const
    {
        return n;
    }

    // 打印图（调试用）
    void print()
    {
        for (int i = 0; i < n; i++)
        {
            if (!adj[i].empty())
            {
                cout << i << " -> ";
                for (auto [v, w] : adj[i])
                {
                    cout << "(" << v << ", " << w << ") ";
                }
                cout << endl;
            }
        }
    }

    vector<tuple<int, int, int>> sortAdjByWeight()
    {
        vector<tuple<int, int, int>> vtiii;
        for (int i = 0; i < n; i++)
        {
            for (auto j : adj[i])
            {
                tuple<int, int, int> tmp(i, j.first, j.second);
                vtiii.push_back(tmp);
            }
        }
        sort(vtiii.begin(), vtiii.end(),
             [](const tuple<int, int, int> &a, const tuple<int, int, int> &b)
             {
                 return get<2>(a) < get<2>(b);
             });
        return vtiii;
    }
    bool operator==(const Graph &b)
    {
        if (b.getAdj() == adj)
            return true;
        return false;
    }
};

vector<vector<pair<int, int>>> createGraph()
{
    // 创建4个顶点的图（对应A=0, B=1, C=2, D=3）
    int n = 4;
    vector<vector<pair<int, int>>> adj(n);

    // 添加边（按照题目图示）
    // A(0)-B(1) 无向边，权重1
    adj[0].push_back({1, 1});
    adj[1].push_back({0, 1});

    // A(0)->C(2) 有向边，权重4
    adj[0].push_back({2, 4});

    // B(1)->D(3) 有向边，权重2
    adj[1].push_back({3, 2});

    // C(2)->D(3) 有向边，权重3
    adj[2].push_back({3, 3});

    return adj;
}
int main()
{
    Graph g(4); // 4个顶点
    g.addUndirectedEdge(0, 1, 1); // A-B 无向
    g.addDirectedEdge(0, 2, 4);   // A->C 有向
    g.addDirectedEdge(1, 3, 2);   // B->D 有向
    g.addDirectedEdge(2, 3, 3);   // C->D 有向

    g.print();
}
```

## 搜索

::: code-tabs
@tab dfs.cc

```cpp :collapsed-lines
void dfs(int u, const vector<vector<pair<int, int>>> &adj, vector<bool> &visited)
{
    visited[u] = true;
    cout << u << " ";

    for (auto [v, w] : adj[u])
    {
        if (!visited[v])
        {
            dfs(v, adj, visited);
        }
    }
}
```

@tab bfs.cc

```cpp :collapsed-lines
void bfs(int start, const vector<vector<pair<int, int>>> &adj)
{
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (auto [v, w] : adj[u])
        {
            if (!visited[v])
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;
}
```

:::

## Dijkstra 最短路

采用优先队列最短路，复杂度 $O((n+m)\log n)$，但是边权不能为负。

```cpp title="dijkstra.cc" :collapsed-lines
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>> &adj)
{
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u])
            continue;

        for (auto [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}
```

## SPFA 算法

SPFA 可以用来算带有负权值的最短路，但是不能用于负环最短路，如下图所示，$E\rightarrow A$ 权值为 $-20$ 如果 $A\rightarrow C\rightarrow D\rightarrow E\rightarrow A$ 这样循环走，负环上的最短路应当为无穷小。

```cpp title="spfa.cc" :collapsed-lines
vector<int> spfa(int start, const vector<vector<pair<int, int>>> &adj)
{
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> inQueue(n, false);
    vector<int> cnt(n, 0); // 记录入队次数，用于检测负环

    dist[start] = 0;
    queue<int> q;
    q.push(start);
    inQueue[start] = true;
    cnt[start]++;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (auto [v, w] : adj[u])
        {
            if (dist[u] != INT_MAX && dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;

                // 如果v不在队列中，则加入队列
                if (!inQueue[v])
                {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;

                    // 检测负环：如果一个节点入队超过n次，说明存在负环
                    if (cnt[v] > n)
                    {
                        // 存在负环，返回空vector或特殊标记
                        return vector<int>();
                    }
                }
            }
        }
    }

    return dist;
}
```

## 最小生成树

请先学会并查集与图形建立后再解决这个问题。

最小生成树解决的问题就是选择边使其权和最小的生成树，也就是说要满足 2 点：

1. 生成的图是一颗树（不存在环）;
2. 边权总和最小。

```cpp title="prim.cc" :collapsed-lines
Graph prim(Graph g, int &weight)
{
    using tiii = tuple<int, int, int>;
    DSU dsu(g.getSize());
    auto cmp = [](const tiii &a, const tiii &b)
    {
        return get<2>(a) > get<2>(b);
    };
    priority_queue<tiii, vector<tiii>, decltype(cmp)> pq(cmp);
    Graph newg(g.getSize());
    auto adj = g.getAdj();
    // 可以从 1 开始
    int cur = 0;
    for (auto j : adj[cur])
    {
        tiii tmp(cur, j.first, j.second);
        pq.push(tmp);
    }
    while (!pq.empty())
    {
        tiii top = pq.top();
        pq.pop();
        if (!dsu.same(get<0>(top), get<1>(top)))
        {
            dsu.merge(get<0>(top), get<1>(top));
            newg.addUndirectedEdge(get<0>(top), get<1>(top), get<2>(top));
            weight += get<2>(top);
            cur = get<1>(top);
            for (auto j : adj[cur])
            {
                tiii tmp(cur, j.first, j.second);
                pq.push(tmp);
            }
        }
    }
    return newg;
}
```