最短路 , 最短路计数 , 单源多汇 和 多源多汇 最短路 , 差分约束系统 , 次短路 , 最短路树 , Kruskal 重构树

Login to join training plan

图论基础

图论是计算机科学的一个重要分支领域。在计算机科学中，图是由节点和节点之间的边构成的抽象模型。节点通常称为顶点，边通常称为边缘或弧。图是一种非常便捷的抽象数据结构，广泛应用于各个领域。

在图中，节点的度指的是与该节点直接相连的边的数量。有向图中，入度指的是指向该节点的边的数量，出度指的是该节点指向其他节点的边的数量。路径是指依次经过一些顶点和边所形成的序列。两个顶点之间的路径长度就是路径上的边的数量。经过每个顶点的路径称为回路。其中，起点和终点相同的回路称为环。

图的表示

在计算机中，图可以用多种方式来表示，常见的有邻接矩阵和邻接表两种方式。

邻接矩阵

邻接矩阵是图的一种常见表示方式，它使用一个二维数组来表示图。给定一个n个节点的有向图G=(V, E)，邻接矩阵M[G]=(m[i][j])，其中，i和j都是从1到n的整数。如果有一条从节点i到节点j的边，则m[i][j]=1；否则，m[i][j]=0。有些情况下，可能需要对边赋予权值，那么可将m[i][j]改为边的权值。

用邻接矩阵表示图有以下特点：

• 无法表示自环的情况，即一个节点有一条指向本身的边。
• 对于稀疏图，即边数量相对于节点数量较少的图，邻接矩阵会占用过多的空间，并且某些节点间没有边的情况需要额外占用空间。
• 适合表示节点间边数量较多的图。

下面是使用邻接矩阵表示的有向图的示例代码：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;

vector<vector<int>> g(MAXN, vector<int>(MAXN)); // 邻接矩阵存储图
int n, m;                                      // 节点数和边数

void addEdge(int u, int v)
{
    g[u][v] = 1; // 在邻接矩阵中加入边
    // 如果是无向图，则需要再加入一条(v, u)的边
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }

    return 0;
}

邻接表

邻接表是图的另一种常见表示方式，它使用一个数组来存储每个节点的邻居节点列表，数组中的每个元素都是一个链表或向量，表示该节点的邻居节点。使用邻接表表示图的空间复杂度为O(|V|+|E|)，其中，|V|和|E|分别为节点数和边数。

使用邻接表表示图有以下特点：

• 适合表示稀疏图，即边数量相对于节点数量较少的图。
• 对于有向图，每个节点需要分别存储其入度和出度。
• 对于稠密图，访问每个节点的所有邻居可能会更加复杂，因为使用邻接表存储每个节点的邻居节点列表时，每个节点的邻居数量可能会较多。

下面是使用邻接表表示的有向图的示例代码：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;

vector<vector<int>> g(MAXN); // 邻接表存储图
int n, m;                    // 节点数和边数

void addEdge(int u, int v)
{
    g[u].push_back(v); // 在邻接表中加入边
    // 如果是无向图，则需要再加入一条(v, u)的边
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }

    return 0;
}

图的遍历

图的遍历指的是从图的某个节点出发，按照某种方式依次访问其它节点的操作。常见的遍历方式有深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历

深度优先遍历是一种经典的图遍历算法，其基本思想是从某个节点开始深度探索，并在探索过程中一直向下深度优先探索，直至遍历结束或无法继续为止。可以使用递归或非递归的方式实现。

深度优先遍历的步骤：

1.访问当前节点 2.对当前节点的连通未被访问的邻节点进行深度优先遍历

下面是使用递归方式实现的深度优先遍历算法的示例代码：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;

vector<vector<int>> g(MAXN); // 邻接表存储图
vector<bool> visited(MAXN);  // 记录节点是否被访问过
int n, m;                    // 节点数和边数

void dfs(int u)
{
    visited[u] = true;
    cout << u << " ";
    for (auto v : g[u]) { // 遍历邻接点
        if (!visited[v]) {
            dfs(v);
        }
    }
}

void dfs_traversal()
{
    visited.assign(n, false);
    for (int i = 0; i < n; ++i) { // 对每个未访问的节点进行深度优先遍历
        if (!visited[i]) {
            dfs(i);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        // 如果是无向图，则需要再加入一条(v, u)的边
    }

    dfs_traversal();

    return 0;
}

广度优先遍历

广度优先遍历是另一种常见的图遍历算法，其基本思想是从某个节点开始宽度优先探索，并将与该节点直接相连的未访问节点全部入队，重复此过程直至遍历结束或无法继续为止。

广度优先遍历的步骤：

1.访问当前节点 2.对当前节点的所有未被访问的邻节点入队 3.从队首取出一个节点，重复执行步骤1和步骤2，直到队列为空

下面是使用队列实现的广度优先遍历算法的示例代码：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 100;

vector<vector<int>> g(MAXN); // 邻接表存储图
vector<bool> visited(MAXN);  // 记录节点是否被

---

最短路

多源最短路

$\text{Floyd}$ $\Theta(n^3)$

存图方式：邻接矩阵。

单源最短路

$\text{SPFA}$ $\Theta(nm) \sim \Theta(n + m)$

堆优化 $\text{Dijkstra}$ $\Theta(n\log n)$

存图方式：邻接链表

SPFA

设 $f_u$ 表示从起点除法到达点 $u$ 的最短路，让每次 $f_u$ 更新的时候，都从 $u$ 出发，以当前的 $f_u$ 作为前驱来更新最短路。

这是最暴力的思想，松弛操作是 令 $vis_i$ 表示第 $i$ 个点当前在不在队列里。当 $vis_i = 1$ 时，不入队，只更新 $f_u$。

• 判负环：当一条边重复走了多次，代表图中一定出现过环。

---

最短路计数

luogu P1144 最短路计数

queue<int> q;
int f[N], sum[N];

memset(h, -1, sizeof h);
memset(f, 0x3f, sizeof f);

input();

q.push(1);
f[1] = 0, sum[1] = 1;

while (!q.empty())
{
    int u = q.front();

    q.pop();

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (f[v] == f[u] + 1) sum[v] = _add(sum[v], sum[u]);
        if (f[v] != INF) continue;
        f[v] = f[u] + 1, sum[v] = _add(sum[v], sum[u]);
        q.push(v);
    }
}

output();

---

多源单汇 和 多源多汇 最短路

• 多源单汇

  • 无向图无所谓，有向图在读入时建反图；
  • 建超级源点，从这个点出发，向所有的源点建立边权 $0$ 的边，然后再从超级源点跑最短路即可。

• 多源多汇

  • 建超级源点和超级汇点。

---

差分约束系统

把数量关系建图，然后跑最短路或判环。

建图

一般的常见关系：

• $a$ 比 $b$ 多至少 $c$ ：$a \ge b + c\to\ \ b-a \le -c$
• $a$ 比 $b$ 多至多 $c$：$a \le b + c \to\ \ a-b \le c$
• $a$ 与 $b$ 相等：$a = b \to\ \ a-b \le 0 \&\& b-a \le 0$

上式都可以整理成 $a-b \le x$ 或 $a-b \ge x$ 的形式，然后从 $a$ 向 $b$ 建边即可。

图上操作

如果问某个数字最小或最大，跑 最短路 或 最长路。

如果判断整个方案是否可行，可以通过判环来确定：$a-b \ge x$ 判正环，$a-b \le x$ 判负环。

---

次短路

在原有的 Dijkstra 的基础上多加一个变量，用来记录次短路，跟最短路一样地维护，把一个 $vis$ 变成两个 $vis$，然后从每个点都触发两次，当最短路确定地时候触发一次，放次短路确定地时候再出发一次，即可实现次短路问题。

int f[N][2];

priority_queue<int, vector<int>, greater<int> > q;

memset(h, -1, sizeof h);
memset(f, 0x3f, sizeof f);

input();

f[s][0] = 0;
q.push({0, s});

while (!q.empty())
{
    int u = q.top().second, x = q.top().first;
    q.pop();

    if (vis[u] == 2) continue;
    vis[u] ++ ;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i], w = d[i];
        if (x + w < f[v][0])		// 如果比当前的最短路还要小 
        {
            f[v][1] = f[v][0];		// 把当前次短路更新成原来的最短路 
            f[v][0] = x + w;		// 更新现在的最短路 
            q.push({x + w, v});		// 来了一条更短的且没有入堆的边，加入堆中 
        }
        else if (x + w < f[v][1])	// 否则如果当前路径长度比最短路大且比次短路小 
        {
            f[v][1] = x + w;		// 更新次短路 
            q.push({x + w, v});		// 一条新的路径，入堆 
        }
    }
}

output();

---

最短路树

把单源最短路的所有边拿出来可以建成一棵树，这棵树叫做最短路树。

---

Kruskal 重构树

把每一个原图中的点作为一个叶子，再 Kruskal 合并的过程中把连接成功的边建虚点，将两棵子树相连。

最终可以建出来一颗 $2n-1$ 个点的树，叫做 Kruskal 重构树。

性质：层数越深的点代表的权值越小。

若要找两点之间路径的最小的最大边权，只需要找到它们的最近公共祖先。