GabWiki | GabWiki

树与图

存储

树是一种特殊的图（无环连通图），与图的存储方式相同：对于无向图中的边 $a \to b$ ，存储两条有向边 $a \to b, b \to a$ ，因此我们可以只考虑有向图的存储。

邻接矩阵

$g [a] [b]$ 存储边 $a \to b$ ，使用空间较多，适合存稠密图。

邻接表

链式前向星

加边函数类似于单链表中的插入函数。

JavaC++

Java

// N为点数 M为边数(一般取N的两倍)
// h中每个节点下标都存储着一个链表(头)
int h[N], e[M], ne[M], idx;

// 初始化
idx = 0;
Arrays.fill(h, -1);

// 添加一条a->b的有向边
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// N为点数 M为边数(一般取N的两倍)
// h中每个节点下标都存储着一个链表(头)
int h[N], e[M], ne[M], idx;

// 初始化
idx = 0;
Arrays.fill(h, -1);

// 添加一条a->b的有向边
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

C++

// N为点数 M为边数(一般取N的两倍)
int h[N], e[M], ne[M], idx;

// 初始化
idx = 0;
memset(h, -1, sizeof(h));

// 添加一条a->b的有向边
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// N为点数 M为边数(一般取N的两倍)
int h[N], e[M], ne[M], idx;

// 初始化
idx = 0;
memset(h, -1, sizeof(h));

// 添加一条a->b的有向边
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

遍历

时间复杂度： $O (N + M)$ （ $N$ 表示顶点数， $M$ 表示边数）

深度优先遍历

模板题：树的重心

C++

int h[N], e[M], ne[M], idx;
int vis[N]; // 记录点是否被遍历过

void dfs(int u) {
    vis[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) dfs(v);
    }
}

int h[N], e[M], ne[M], idx;
int vis[N]; // 记录点是否被遍历过

void dfs(int u) {
    vis[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) dfs(v);
    }
}

宽度优先遍历

模板题：图中点的层次

C++

int h[N], e[M], ne[M], idx;
int vis[N]; // 记录点是否被遍历过

void bfs(int u) {
    queue<int> que;
    que.push(u); // 从顶点u开始遍历
	vis[u] = true;
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int v = e[i];
            if (!vis[v]) {
                que.push(v);
                st[v] = true;
            }
        }
    }
}

int h[N], e[M], ne[M], idx;
int vis[N]; // 记录点是否被遍历过

void bfs(int u) {
    queue<int> que;
    que.push(u); // 从顶点u开始遍历
	vis[u] = true;
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int v = e[i];
            if (!vis[v]) {
                que.push(v);
                st[v] = true;
            }
        }
    }
}

拓扑排序

时间复杂度： $O (N + M)$ （ $N$ 表示顶点数， $M$ 表示边数）

模板题：有向图的拓扑序列

C++

int n, m, idx;
int h[N], e[M], ne[M], ind[N]; // ind维护所有顶点的入度
int que[N], hh, tt = -1; // 维护一个队列

bool top_sort() {
    // 把所有入度为0的顶点先入队
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) que[++tt] = i;
    }
    while (hh <= tt) {
        int t = que[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int v = e[i];
            if (--ind[v] == 0) que[++tt] = v;
        }
    }
    // 如果所有点都入队了 说明存在拓扑序列 否则不存在拓扑序列
    return tt == n - 1;
}

if (top_sort()) {
    // 存在拓扑排序 输出拓扑排序
    for (int i = 0; i < n; ++i) printf("%d ", que[i]);
}

int n, m, idx;
int h[N], e[M], ne[M], ind[N]; // ind维护所有顶点的入度
int que[N], hh, tt = -1; // 维护一个队列

bool top_sort() {
    // 把所有入度为0的顶点先入队
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) que[++tt] = i;
    }
    while (hh <= tt) {
        int t = que[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int v = e[i];
            if (--ind[v] == 0) que[++tt] = v;
        }
    }
    // 如果所有点都入队了 说明存在拓扑序列 否则不存在拓扑序列
    return tt == n - 1;
}

if (top_sort()) {
    // 存在拓扑排序 输出拓扑排序
    for (int i = 0; i < n; ++i) printf("%d ", que[i]);
}

最短路算法

单源最短路

朴素 Dijkstra 算法

基于贪心。

时间复杂度： $O (N^{2} + M)$ （ $N$ 表示顶点数， $M$ 表示边数）

一般用在不存在负权边的稠密图^[1]求单源最短路中。

求图中 $s r c \to d e s t$ 的最短路，算法步骤：

变量定义：

使用邻接矩阵( g )存图，n 表示顶点的数量。
维护 dists ，dists[u] 表示从点 $s r c$ 出发到达点 $u$ 的最短距离。
维护 vis ， vis[u] 为 true 时表示 $s r c \to u$ 的距离已经被确定。

初始化：把 dists 中所有数初始化为正无穷（一般用 INF=0x3f3f3f3f 代替）， dists[src] = 0。
循环 $n - 1$ 次：
1. 取出还未确定最短距离( vis[i] == false )的，距离 src 最近的顶点(mn)。
2. 把 mn 置为最短距离已确认的点。
3. 用 mn 更新 src 到其他点的最短距离。
循环结束后若 dists 中存储的 src 到 dest 的距离不为 INF 就说明 src 到点 dest 的最短距离是 dists[dest]。

模板代码：

JavaC++

Java

static final int INF = 0x3f3f3f3f;
int n, m;
int[][] g;
    
// 返回src到dest的最短距离 不存在则返回-1
static int dijkstra(int src, int dest) {
    int[] dists = new int[n + 1];
    boolean[] vis = new boolean[n + 1];
    Arrays.fill(dists, INF);
    dists[src] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = Math.min(dists[j], dists[mn] + g[mn][j]);
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

static final int INF = 0x3f3f3f3f;
int n, m;
int[][] g;
    
// 返回src到dest的最短距离 不存在则返回-1
static int dijkstra(int src, int dest) {
    int[] dists = new int[n + 1];
    boolean[] vis = new boolean[n + 1];
    Arrays.fill(dists, INF);
    dists[src] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = Math.min(dists[j], dists[mn] + g[mn][j]);
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

C++

const int INF = 0x3f3f3f3f;
int n;
int g[N][N], dists[N];
bool vis[N];

int dijkstra(int src, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[src] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = min(dists[j], dists[mn] + g[mn][j]);
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

const int INF = 0x3f3f3f3f;
int n;
int g[N][N], dists[N];
bool vis[N];

int dijkstra(int src, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[src] = 0;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = min(dists[j], dists[mn] + g[mn][j]);
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

堆优化 Dijkstra 算法

基于贪心。

时间复杂度： $O (M \log N)$ （ $N$ 表示顶点数， $M$ 表示边数）

一般用在不存在负权边的稀疏图^[1:1]求单源最短路中。

和朴素 Dijkstra 算法思路一样，但是会把遍历求出最小值的操作优化为小根堆取堆顶，由于是稀疏图，使用邻接表存图。

模板代码：

JavaC++

Java

static final int INF = 0x3f3f3f3f;
int n, m;
int[] h, e, ne, w; // 邻接表存图
int idx;

// 返回src到dest的最短距离 不存在则返回-1
int dijkstra(int src, int dest) {
    int[] dists = new int[n + 1]; // 所有点到src的距离
    // 小根堆 以最短距离为标准排序
    Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    Arrays.fill(dists, INF);
    dists[src] = 0;
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], mn = curr[1];
        for (int i = h[mn]; i != -1; i = ne[i]) {
            int v = e[i];
            if (d + w[i] < dists[v]) {
                dists[v] = d + w[i];
                pq.offer(new int[]{dists[v], v});
            }
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

static final int INF = 0x3f3f3f3f;
int n, m;
int[] h, e, ne, w; // 邻接表存图
int idx;

// 返回src到dest的最短距离 不存在则返回-1
int dijkstra(int src, int dest) {
    int[] dists = new int[n + 1]; // 所有点到src的距离
    // 小根堆 以最短距离为标准排序
    Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    Arrays.fill(dists, INF);
    dists[src] = 0;
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], mn = curr[1];
        for (int i = h[mn]; i != -1; i = ne[i]) {
            int v = e[i];
            if (d + w[i] < dists[v]) {
                dists[v] = d + w[i];
                pq.offer(new int[]{dists[v], v});
            }
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

C++

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
int h[N], e[N], weights[N], ne[N], idx;
int dists[N];

int dijkstra(int src, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[src] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
    heap.push({0, src}); // 优先队列存pair时默认按照first排序 first存储距离 second存储节点编号
    while (!heap.empty()) {
        auto curr = heap.top();
        heap.pop();
        int mn = curr.second;
        if (vis[mn]) continue;
        int dist = curr.first;
        vis[mn] = true;
        for (int i = h[mn]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist + weights[i] < dists[j]) {
                dists[j] = dist + weights[i];
                heap.push({dists[j], j});
            }
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
int h[N], e[N], weights[N], ne[N], idx;
int dists[N];

int dijkstra(int src, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    dists[src] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
    heap.push({0, src}); // 优先队列存pair时默认按照first排序 first存储距离 second存储节点编号
    while (!heap.empty()) {
        auto curr = heap.top();
        heap.pop();
        int mn = curr.second;
        if (vis[mn]) continue;
        int dist = curr.first;
        vis[mn] = true;
        for (int i = h[mn]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist + weights[i] < dists[j]) {
                dists[j] = dist + weights[i];
                heap.push({dists[j], j});
            }
        }
    }
    return dists[dest] == INF ? -1 : dists[dest];
}

Bellman-Ford 算法

基于动态规划。

时间复杂度： $O (N M)$ （ $N$ 表示顶点数， $M$ 表示边数）

一般用在存在负权边的图求单源最短路中。

求图中点 src 到点 dest 的最短路，算法步骤：使用结构体(edges)存图（只要能把所有边存下来用于遍历就行），n 表示顶点的数量。维护 dists 表示从点 src 出发到每个顶点的最短距离。伪代码：

伪代码

for n: // 迭代k次时dists数组表示从src经过不超过k条边走到每个点的最短距离
    for a, b, w in edges:
        dists[b] = min(dists[b], dists[a] + w) // 松弛操作

for n: // 迭代k次时dists数组表示从src经过不超过k条边走到每个点的最短距离
    for a, b, w in edges:
        dists[b] = min(dists[b], dists[a] + w) // 松弛操作

循环之后，所有边的距离一定满足： $d i s t [b] < d i s t [a] + w$ （三角不等式）。

模板代码：

C++

const INF = 0x3f3f3f3f;
struct Edge {
    int a, b, w;
} edges[M];
int dists[N], bak[N];
int n, m, k; // n表示点数 m表示边数

int bellman_ford(int src, int dest, int k) {
    memset(dists, 0x3f, sizeof(dists));
    dists[src] = 0;
    while (k--) {
        memcpy(bak, dists, sizeof(dists)); // 备份上一次的结果 防止更新串联
        for (int i = 0; i < m; ++i) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            dists[b] = min(dists[b], bak[a] + w);
        }
    }
    return dists[dest];
}

int ans = bellman_ford(1, n, k); // 求最短路
if (ans > INF / 2) // 有可能出现最短路不存在但是dists[dest]被更新的情况 所以只要取到的ans比数据范围大就记为不存在最短路
else printf("%d\n", ans);

const INF = 0x3f3f3f3f;
struct Edge {
    int a, b, w;
} edges[M];
int dists[N], bak[N];
int n, m, k; // n表示点数 m表示边数

int bellman_ford(int src, int dest, int k) {
    memset(dists, 0x3f, sizeof(dists));
    dists[src] = 0;
    while (k--) {
        memcpy(bak, dists, sizeof(dists)); // 备份上一次的结果 防止更新串联
        for (int i = 0; i < m; ++i) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            dists[b] = min(dists[b], bak[a] + w);
        }
    }
    return dists[dest];
}

int ans = bellman_ford(1, n, k); // 求最短路
if (ans > INF / 2) // 有可能出现最短路不存在但是dists[dest]被更新的情况 所以只要取到的ans比数据范围大就记为不存在最短路
else printf("%d\n", ans);

SPFA 算法

Bellman-Ford 算法的宽搜优化，基于动态规划。

时间复杂度：一般情况下 $O (M)$ 最坏情况下 $O (N M)$ （ $N$ 表示顶点数， $M$ 表示边数）

一般用在不存在负权回路的图求单源最短路中。

SPFA 算法是优化 Bellman-Ford 算法得到的，Bellman-Ford 算法每次迭代时是枚举所有边来更新，但实际上每次迭代时并不是每一条边都可以用来更新，于是 SPFA 就在这一点上做了优化，它利用BFS来进行每一次的迭代，尽可能地保证每一次迭代都更新最短距离。

求图中点 src 到点 dest 的最短路，算法步骤：

使用邻接表存图，n 表示顶点的数量。维护队列 que 存储所有最短距离变小了的顶点。维护 dists 从点 src 出发到每个顶点的最短距离。维护 has 表示某个点是否在队列中。

初始化：把 dists 中所有数初始化为正无穷（一般用 INF=0x3f3f3f3f 代替）， dists[src] = 0，把起始点放入队列，并标记起始点在队中。
当队列不为空时，循环：
1. 取出队头(u)，标识 u 已不在队中（ has[u] = false ）。
2. 遍历顶点 u 的所有出边：
  - 拿到顶点 v ，尝试用 u 的最短路更新 dists[v]，如果可以更新并且 v 不在队列中，就把 v 入队。
循环结束后如果 dists[dest] 不大于 INF / 2 就说明 src 到 dest 的最短路存在且为 dists[dest]。

模板代码：

JavaC++

Java

static final int INF = 0x3f3f3f3f;
int n, m;
int[] h, e, ne, w;
int idx;

// 返回src到dest的最短距离 不存在则返回INF
static int spfa(int src, int dest) {
    int[] dists = new int[n + 1];
    boolean[] has = new boolean[n + 1];
    Arrays.fill(dists, INF);
    dists[src] = 0;
    Queue<Integer> que = new LinkedList<>();
    que.offer(src);
    has[src] = true;
    while (!que.isEmpty()) {
        int u = que.poll();
        has[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                if (!has[v]) {
                    que.offer(v);
                    has[v] = true;
                }
            }
        }
    }
    return dists[dest];
}

static final int INF = 0x3f3f3f3f;
int n, m;
int[] h, e, ne, w;
int idx;

// 返回src到dest的最短距离 不存在则返回INF
static int spfa(int src, int dest) {
    int[] dists = new int[n + 1];
    boolean[] has = new boolean[n + 1];
    Arrays.fill(dists, INF);
    dists[src] = 0;
    Queue<Integer> que = new LinkedList<>();
    que.offer(src);
    has[src] = true;
    while (!que.isEmpty()) {
        int u = que.poll();
        has[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                if (!has[v]) {
                    que.offer(v);
                    has[v] = true;
                }
            }
        }
    }
    return dists[dest];
}

C++

const int INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dists[N];
bool has[N];

int spfa(int src, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    queue<int> que;
    dists[src] = 0;
    que.push(src);
    has[src] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        has[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                if (!has[v]) {
                    que.push(v);
                    has[v] = true;
                }
            }
        }
    }
    return dists[dest];
}

const int INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dists[N];
bool has[N];

int spfa(int src, int dest) {
    memset(dists, 0x3f, sizeof(dists));
    queue<int> que;
    dists[src] = 0;
    que.push(src);
    has[src] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        has[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                if (!has[v]) {
                    que.push(v);
                    has[v] = true;
                }
            }
        }
    }
    return dists[dest];
}

SPFA 算法判复环

时间复杂度： $O (N M)$ （ $N$ 表示顶点数， $M$ 表示边数）

一般用在图求是否存在负权回路中。

算法步骤与普通 SPFA 算法几乎相同。

原理：如果某条最短路径上经过了 n + 1 个点，由抽屉原理一定有两个点相同，所以存在环。

TIP

把 SPFA 中的队列换成栈一般可以提高算法效率但可能会被特殊数据卡

模板代码：

JavaC++

Java

int n, m;
int[] h, e, ne, w;
int idx;

// 如果图中存在负环返回true 否则返回false
boolean spfa() {
    // 不用初始化dists 因为我们只需能看出短路的变化趋势即可 不需要真的求出最短路
    int[] dists = new int[n + 1];
    boolean[] has = new boolean[n + 1];
    // cnts存储这每个点最短路中经过的点数
    int[] cnts = new int[n + 1];
    Queue<Integer> que = new LinkedList<>();
    // 有些节点的最短路可能并不经过负权回路 为了找出整个图中是否存在负权回路 要把所有顶点全部算上
    for (int u = 1; u <= n; ++u) {
        que.offer(u);
        has[u] = true;
        cnts[u] = 1; // 该点的最短路经过自己
    }
    while (!que.isEmpty()) {
        int u = que.poll();
        has[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                cnts[v] = cnts[u] + 1;
                // 如果从点1到点v的最短路中包含比n多个点 根据抽屉原理 说明存在负权回路
                if (cnts[v] > n) return true;
                if (!has[v]) {
                    que.offer(v);
                    has[v] = true;
                }
            }
        }
    }
    return false;
}

int n, m;
int[] h, e, ne, w;
int idx;

// 如果图中存在负环返回true 否则返回false
boolean spfa() {
    // 不用初始化dists 因为我们只需能看出短路的变化趋势即可 不需要真的求出最短路
    int[] dists = new int[n + 1];
    boolean[] has = new boolean[n + 1];
    // cnts存储这每个点最短路中经过的点数
    int[] cnts = new int[n + 1];
    Queue<Integer> que = new LinkedList<>();
    // 有些节点的最短路可能并不经过负权回路 为了找出整个图中是否存在负权回路 要把所有顶点全部算上
    for (int u = 1; u <= n; ++u) {
        que.offer(u);
        has[u] = true;
        cnts[u] = 1; // 该点的最短路经过自己
    }
    while (!que.isEmpty()) {
        int u = que.poll();
        has[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                cnts[v] = cnts[u] + 1;
                // 如果从点1到点v的最短路中包含比n多个点 根据抽屉原理 说明存在负权回路
                if (cnts[v] > n) return true;
                if (!has[v]) {
                    que.offer(v);
                    has[v] = true;
                }
            }
        }
    }
    return false;
}

C++

int h[N], e[M], w[M], ne[M], idx;
int dists[N], cnts[N];
bool vis[N];

bool spfa() {
    queue<int> que;
    for (int x = 1; x <= n; ++x) {
        que.push(x);
        vis[x] = true;
        cnts[x] = 1;
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                cnts[v] = cnts[u] + 1;
                if (cnts[v] > n) return true;
                if (!vis[v]) {
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return false;
}

int h[N], e[M], w[M], ne[M], idx;
int dists[N], cnts[N];
bool vis[N];

bool spfa() {
    queue<int> que;
    for (int x = 1; x <= n; ++x) {
        que.push(x);
        vis[x] = true;
        cnts[x] = 1;
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dists[u] + w[i] < dists[v]) {
                dists[v] = dists[u] + w[i];
                cnts[v] = cnts[u] + 1;
                if (cnts[v] > n) return true;
                if (!vis[v]) {
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return false;
}

多源汇最短路

Floyd 算法

基于动态规划。

时间复杂度： $O (N^{3})$ （ $N$ 表示顶点数）

一般用在不存在负权回路的图求多源汇最短路中。

使用邻接表存图，n 表示顶点的数量，维护 dists 用于存储任意点到任意点的最短距离。

算法步骤（伪代码）：

伪代码

// 初始化 n表示顶点的数量
for i from 1 to n:
    for j from 1 to n:
        d[i][j] = i == j ? 0 : INF

// Floyd算法
for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

// 初始化 n表示顶点的数量
for i from 1 to n:
    for j from 1 to n:
        d[i][j] = i == j ? 0 : INF

// Floyd算法
for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

模板代码：

JavaC++

Java

static final int INF = 0x3f3f3f3f;
int n; // 顶点数量
int dists[N][N]; // 邻接矩阵存图

// 初始化邻接矩阵(在输入所有边之前)
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (i == j) continue;
        dists[i][j] = INF;
    }
}

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dists[i][j] = Math.min(dists[i][j], dists[i][k] + dists[k][j]);
            }
        }
    }
}

// src->dest的最短路
if (dists[src][dest] > INF / 2) // 不存在最短路
else // ans: dists[src][dest]

static final int INF = 0x3f3f3f3f;
int n; // 顶点数量
int dists[N][N]; // 邻接矩阵存图

// 初始化邻接矩阵(在输入所有边之前)
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (i == j) continue;
        dists[i][j] = INF;
    }
}

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dists[i][j] = Math.min(dists[i][j], dists[i][k] + dists[k][j]);
            }
        }
    }
}

// src->dest的最短路
if (dists[src][dest] > INF / 2) // 不存在最短路
else // ans: dists[src][dest]

C++

const INF = 0x3f3f3f3f;
int n;
int dists[N][N];

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j]);
            }
        }
    }
}

// src->dest的最短路
if (dists[src][dest] > INF / 2) // 不存在最短路
else // ans: dists[src][dest]

const INF = 0x3f3f3f3f;
int n;
int dists[N][N];

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j]);
            }
        }
    }
}

// src->dest的最短路
if (dists[src][dest] > INF / 2) // 不存在最短路
else // ans: dists[src][dest]

最小生成树算法

生成树：生成树 指的是「无向图」中，具有该图的 全部顶点 且 边数最少 的 连通子图。
最小生成树：最小生成树 指的是「加权无向图」中总权重最小的生成树。

朴素 Prim 算法

时间复杂度： $O (N^{2})$ （ $N$ 表示顶点数）

一般用在稠密图^[1:2]求最小生成树中。

与 Dijkstra 算法相似，算法步骤：

使用邻接矩阵(g)存图，n 表示顶点的数量，维护 dists 用于存储集合外的点到集合的最短距离，维护 vis 表示某个点是否已经被放入最小生成树。

初始化：把 dists 中所有数初始化为正无穷。
循环 n 次：
1. 找到集合外距离集合最近的点(mn)。
2. 若该点不是第一个迭代的点且 与集合内所有顶点都不相连 ，说明该图不是一个连通图，不存在最小生成树。
3. 把 mn 放入最小生成树（ vis[mn] = true ）并更新最小生成树的总权值（ res += vis[mn] ）。
4. 用 mn 更新其他点到集合的最短距离。

为什么 Dijkstra 算法外层循环 n-1 次而 Prim 算法要循环 n 次？

——因为 Dijkstra 算法在迭代前先把源点加入了集合，所以它只用迭代 n-1 个点，而 Prim 算法要迭代所有 n 个顶点。

模板代码：

C++

const INF = 0x3f3f3f3f;
int n; // 顶点数量
int g[N][N]; // 邻接矩阵存图
dists[N];
bool vis[N];

// 返回最小生成树的权值和 若不存在则返回INF
int prim() {
    memset(dists, 0x3f, sizeof(dists));
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        if (i) {
            if (dists[mn] == INF) return INF; // 发现不是所有点连通 不存在最小生成树
            res += dists[mn]; // 把mn加入最小生成树 并把dists[mn]累加进权值和
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) dists[j] = min(dists[j], g[j][mn]);
    }
    return res;
}

int ans = prim(); // 若ans==INF 说明该图不存在最小生成树
// 最小生成树的总权重为: ans

const INF = 0x3f3f3f3f;
int n; // 顶点数量
int g[N][N]; // 邻接矩阵存图
dists[N];
bool vis[N];

// 返回最小生成树的权值和 若不存在则返回INF
int prim() {
    memset(dists, 0x3f, sizeof(dists));
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] < dists[mn])) mn = j;
        }
        if (i) {
            if (dists[mn] == INF) return INF; // 发现不是所有点连通 不存在最小生成树
            res += dists[mn]; // 把mn加入最小生成树 并把dists[mn]累加进权值和
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) dists[j] = min(dists[j], g[j][mn]);
    }
    return res;
}

int ans = prim(); // 若ans==INF 说明该图不存在最小生成树
// 最小生成树的总权重为: ans

Kruskal 算法

时间复杂度： $O (M \log M)$ （ $M$ 表示边数）

一般用在稀疏图^[1:3]求最小生成树中。

算法步骤：

将所有边按照权重从小到大排序。
枚举每条边 $u \overset{w}{\leftrightarrow} v$ 。
- 如果 $u, v$ 不连通，将这条边加入集合中。

模板代码：

C++

const int INF = 0x3f3f3f3f;
int m; // 边数
struct Edge {
    int u, v, w;
    
    bool operator<(const Edge& e) {
        return w < e.w;
    }
} edges[M]; // 结构体存储所有边 并按照权值升序排序
int roots[N];

// 并查集操作
int find(int x) {
    return x == roots[x] ? x : (roots[x] = find(roots[x]));
}

void join(int p, int q) {
    roots[find(p)] = find(q);
}

// 返回最小生成树的权值和 若不存在则返回INF
int kruskal() {
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++i) roots[i] = i;
    int cnt = 0, res = 0;
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            join(u, v);
            res += w;
            if (++cnt == n - 1) break;
        }
    }
    return cnt < n - 1 ? INF : res;
}

int ans = kruskal(); // 若ans==INF 说明该图不存在最小生成树
// 最小生成树的总权重为: ans

const int INF = 0x3f3f3f3f;
int m; // 边数
struct Edge {
    int u, v, w;
    
    bool operator<(const Edge& e) {
        return w < e.w;
    }
} edges[M]; // 结构体存储所有边 并按照权值升序排序
int roots[N];

// 并查集操作
int find(int x) {
    return x == roots[x] ? x : (roots[x] = find(roots[x]));
}

void join(int p, int q) {
    roots[find(p)] = find(q);
}

// 返回最小生成树的权值和 若不存在则返回INF
int kruskal() {
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++i) roots[i] = i;
    int cnt = 0, res = 0;
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            join(u, v);
            res += w;
            if (++cnt == n - 1) break;
        }
    }
    return cnt < n - 1 ? INF : res;
}

int ans = kruskal(); // 若ans==INF 说明该图不存在最小生成树
// 最小生成树的总权重为: ans

二分图

定义

二分图（Bipartite graph），又称二部图。

它是：所有顶点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将所有顶点划分成满足以上性质的两个集合。

性质

如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。
二分图不存在长度为奇数的环。
因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。

染色法判定二分图

时间复杂度： $O (N + M)$ （ $N$ 表示顶点数， $M$ 表示边数）

模板代码：

JavaC++

Java

int n, m; // 顶点数 边数
int[] h = new int[N], e = new int[M], ne = new int[M]; // 邻接表存图
int idx;
int[] colors; // 记录每个节点的颜色: 0表示还未被染色  1和2为两种不同的颜色

// 把顶点u染成c色 返回是否有矛盾
boolean dye(int u, int c) {
    colors[u] = c; // 把u染色c色
    // 枚举与u相连的所有顶点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        // 若顶点v没染过色 给它染与u不同的色 如果矛盾就说明不是二分图
        // 若顶点v染过色 看它与u的颜色是否相同来判断是否有矛盾
        if (colors[v] == 0 && !dye(v, 3 - c) || colors[v] == c) return false;
    }
    return true;
}

// 枚举所有顶点
for (int u = 1; u <= n; ++u) {
    if (colors[u] == 0) {
        // 尝试给还未被染色的顶点染色
        if (!dye(u, 1)) // 染色矛盾 该图不是二分图
    }
}
// 枚举能走完就说明该图是二分图

int n, m; // 顶点数 边数
int[] h = new int[N], e = new int[M], ne = new int[M]; // 邻接表存图
int idx;
int[] colors; // 记录每个节点的颜色: 0表示还未被染色  1和2为两种不同的颜色

// 把顶点u染成c色 返回是否有矛盾
boolean dye(int u, int c) {
    colors[u] = c; // 把u染色c色
    // 枚举与u相连的所有顶点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        // 若顶点v没染过色 给它染与u不同的色 如果矛盾就说明不是二分图
        // 若顶点v染过色 看它与u的颜色是否相同来判断是否有矛盾
        if (colors[v] == 0 && !dye(v, 3 - c) || colors[v] == c) return false;
    }
    return true;
}

// 枚举所有顶点
for (int u = 1; u <= n; ++u) {
    if (colors[u] == 0) {
        // 尝试给还未被染色的顶点染色
        if (!dye(u, 1)) // 染色矛盾 该图不是二分图
    }
}
// 枚举能走完就说明该图是二分图

C++

int n, m; // 顶点数 边数
int h[N], e[M], ne[M], idx; // 邻接表存图
int colors[N]; // 记录每个节点的颜色: 0表示还未被染色  1和2为两种不同的颜色

bool dfs(int u, int c) {
    colors[u] = c; // 给u染色
    // 枚举与u相连的所有顶点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        // 若顶点v没染过色 给它染与u不同的色 如果矛盾就说明不是二分图
        // 若顶点v染过色 看它与u的颜色是否相同来判断是否有矛盾
        if (!colors[v] && !dfs(v, 3 - c) || colors[v] == c) return false;
    }
    return true;
}

// 枚举所有顶点
for (int i = 1; i <= n; ++i) {
    if (!colors[i]) {
        // 尝试给还未被染色的顶点染色
        if (!dfs(i, 1)) // 染色矛盾 该图不是二分图
    }
}
// 枚举能走完就说明该图是二分图

int n, m; // 顶点数 边数
int h[N], e[M], ne[M], idx; // 邻接表存图
int colors[N]; // 记录每个节点的颜色: 0表示还未被染色  1和2为两种不同的颜色

bool dfs(int u, int c) {
    colors[u] = c; // 给u染色
    // 枚举与u相连的所有顶点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        // 若顶点v没染过色 给它染与u不同的色 如果矛盾就说明不是二分图
        // 若顶点v染过色 看它与u的颜色是否相同来判断是否有矛盾
        if (!colors[v] && !dfs(v, 3 - c) || colors[v] == c) return false;
    }
    return true;
}

// 枚举所有顶点
for (int i = 1; i <= n; ++i) {
    if (!colors[i]) {
        // 尝试给还未被染色的顶点染色
        if (!dfs(i, 1)) // 染色矛盾 该图不是二分图
    }
}
// 枚举能走完就说明该图是二分图

匈牙利算法求二分图最大匹配

时间复杂度： $O (N M)$ （实际运行时间一般远小于 $O (N M)$ ）（ $N$ 表示顶点数， $M$ 表示边数）

模板代码：

C++

int n1, n2, idx; // n1 n2 分别表示二分图的两部分的顶点数
int matchs[N]; // 记录匹配
bool vis[N]; // 记录在对某个节点的匹配尝试中 另一种颜色的节点是否被被用过

bool find(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) {
            vis[v] = true;
            if (!matchs[v] || find(matchs[v])) {
                matchs[v] = u;
                return true;
            }
        }
    }
    return false;
}

int ans = 0; // 记录最大匹配
for (int i = 1; i <= n1; ++i) {
    memset(vis, false, sizeof(vis)); // 重置vis
    if (find(i)) ++ans;
}

int n1, n2, idx; // n1 n2 分别表示二分图的两部分的顶点数
int matchs[N]; // 记录匹配
bool vis[N]; // 记录在对某个节点的匹配尝试中 另一种颜色的节点是否被被用过

bool find(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) {
            vis[v] = true;
            if (!matchs[v] || find(matchs[v])) {
                matchs[v] = u;
                return true;
            }
        }
    }
    return false;
}

int ans = 0; // 记录最大匹配
for (int i = 1; i <= n1; ++i) {
    memset(vis, false, sizeof(vis)); // 重置vis
    if (find(i)) ++ans;
}

最近公共祖先（LCA）

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

爬山法

时间复杂度：

单次查询： $O (N)$ （ $N$ 指查询点的高度）

模板题：【LCA, 递归】二叉树。

模板代码：

Java

// l[u]: 节点u的左子节点  r[u]: 节点u的右子节点  p[u]: 节点u的父节点
int[] l = new int[N], r = new int[N], p = new int[N];
int[] dep = new int[N]; // dep[u]: 根节点到节点u的距离

// 初始化
Arrays.fill(l, -1);
Arrays.fill(r, -1);

// 预处理到根节点的距离
static void dfs(int u, int d) {
    dep[u] = d;
    if (l[u] != -1) dfs(l[u], d + 1);
    if (r[u] != -1) dfs(r[u], d + 1);
}
dfs(1, 0);
    
static int lca(int a, int b) {
    if (dep[a] > dep[b]) {
        int t = a;
        a = b;
        b = t;
    }
    while (dep[b] != dep[a]) b = p[b];
    while (a != b) {
        a = p[a];
        b = p[b];
    }
    return a;
}
// 求节点a, b的最近公共祖先: lca(a, b)

// l[u]: 节点u的左子节点  r[u]: 节点u的右子节点  p[u]: 节点u的父节点
int[] l = new int[N], r = new int[N], p = new int[N];
int[] dep = new int[N]; // dep[u]: 根节点到节点u的距离

// 初始化
Arrays.fill(l, -1);
Arrays.fill(r, -1);

// 预处理到根节点的距离
static void dfs(int u, int d) {
    dep[u] = d;
    if (l[u] != -1) dfs(l[u], d + 1);
    if (r[u] != -1) dfs(r[u], d + 1);
}
dfs(1, 0);
    
static int lca(int a, int b) {
    if (dep[a] > dep[b]) {
        int t = a;
        a = b;
        b = t;
    }
    while (dep[b] != dep[a]) b = p[b];
    while (a != b) {
        a = p[a];
        b = p[b];
    }
    return a;
}
// 求节点a, b的最近公共祖先: lca(a, b)

倍增法

时间复杂度：

预处理： $O (N \log N)$ （ $N$ 指查询点的高度）
单次查询： $O (\log N)$

模板代码

$N$ 为节点数， $M$ 为树中的边数（由于树中都是无向边, 所以一般取 $2 N$ ）， $K$ 一般取 $⌊ \log_{2} N ⌋ + 1$ 。

JavaC++

Java

// 邻接表存树 无向边加两次
int[] h = new int[N], e = new int[M], ne = new int[M];
int idx, root;
int[] dep = new int[N];
int[][] fa = new int[N][K];

// 预处理
void bfs() {
    Arrays.fill(dep, -1);
    dep[0] = 0; // 哨兵
    dep[root] = 1;
    Queue<Integer> que = new LinkedList<>();
    que.offer(root);
    while (!que.isEmpty()) {
        int u = que.poll();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dep[v] == -1) {
                dep[v] = dep[u] + 1;
                que.offer(v);
                fa[v][0] = u;
                for (int k = 1; k < K; ++k) {
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                }
            }
        }
    }
}

// 求节点a, b的最近公共祖先: lca(a, b)
int lca(int a, int b) {
    if (dep[a] > dep[b]) {
        int t = a;
        a = b;
        b = t;
    }
    for (int k = K - 1; k >= 0; --k) {
        if (dep[fa[b][k]] >= dep[a]) b = fa[b][k];
    }
    if (a == b) return a;
    for (int k = K - 1; k >= 0; --k) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

// 邻接表存树 无向边加两次
int[] h = new int[N], e = new int[M], ne = new int[M];
int idx, root;
int[] dep = new int[N];
int[][] fa = new int[N][K];

// 预处理
void bfs() {
    Arrays.fill(dep, -1);
    dep[0] = 0; // 哨兵
    dep[root] = 1;
    Queue<Integer> que = new LinkedList<>();
    que.offer(root);
    while (!que.isEmpty()) {
        int u = que.poll();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dep[v] == -1) {
                dep[v] = dep[u] + 1;
                que.offer(v);
                fa[v][0] = u;
                for (int k = 1; k < K; ++k) {
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                }
            }
        }
    }
}

// 求节点a, b的最近公共祖先: lca(a, b)
int lca(int a, int b) {
    if (dep[a] > dep[b]) {
        int t = a;
        a = b;
        b = t;
    }
    for (int k = K - 1; k >= 0; --k) {
        if (dep[fa[b][k]] >= dep[a]) b = fa[b][k];
    }
    if (a == b) return a;
    for (int k = K - 1; k >= 0; --k) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

C++

// 邻接表存树 无向边加两次
int root;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N][K];
int que[N], hh, tt = -1;

// 预处理
void bfs(int u) {
    memset(dep, 0x3f, sizeof(dep));
    dep[0] = 0, dep[u] = 1;
    que[++tt] = u;
    while (hh <= tt) {
        u = que[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            // 若v已被访问过则跳过
            if (dep[v] != INF) continue;
            dep[v] = dep[u] + 1;
            fa[v][0] = u;
            for (int k = 1; k < K; ++k) {
                fa[v][k] = fa[fa[v][k - 1]][k - 1]; // 递推
            }
            que[++tt] = v;
        }
    }
}

// 求节点a, b的最近公共祖先: lca(a, b)
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int k = K - 1; k >= 0; --k) {
        if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
    }
    if (a == b) return a;
    for (int k = K - 1; k >= 0; --k) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

// 邻接表存树 无向边加两次
int root;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N][K];
int que[N], hh, tt = -1;

// 预处理
void bfs(int u) {
    memset(dep, 0x3f, sizeof(dep));
    dep[0] = 0, dep[u] = 1;
    que[++tt] = u;
    while (hh <= tt) {
        u = que[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            // 若v已被访问过则跳过
            if (dep[v] != INF) continue;
            dep[v] = dep[u] + 1;
            fa[v][0] = u;
            for (int k = 1; k < K; ++k) {
                fa[v][k] = fa[fa[v][k - 1]][k - 1]; // 递推
            }
            que[++tt] = v;
        }
    }
}

// 求节点a, b的最近公共祖先: lca(a, b)
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int k = K - 1; k >= 0; --k) {
        if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
    }
    if (a == b) return a;
    for (int k = K - 1; k >= 0; --k) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

稠密图与稀疏图一般以 $M$ 与 $N \log N$ 的大小来区分（ $M$ 指边数， $N$ 指点数）。 ↩︎ ↩︎ ↩︎ ↩︎

树与图 ​

存储 ​

邻接矩阵 ​

邻接表 ​

链式前向星 ​

遍历 ​

深度优先遍历 ​

宽度优先遍历 ​

拓扑排序 ​

最短路算法 ​

单源最短路 ​

朴素 Dijkstra 算法 ​

堆优化 Dijkstra 算法 ​

Bellman-Ford 算法 ​

SPFA 算法 ​

SPFA 算法判复环 ​

多源汇最短路 ​

Floyd 算法 ​

最小生成树算法 ​

朴素 Prim 算法 ​

Kruskal 算法 ​

二分图 ​

染色法判定二分图 ​

匈牙利算法求二分图最大匹配 ​

最近公共祖先（LCA） ​

爬山法 ​

倍增法 ​

树与图

存储

邻接矩阵

邻接表

链式前向星

遍历

深度优先遍历

宽度优先遍历

拓扑排序

最短路算法

单源最短路

朴素 Dijkstra 算法

堆优化 Dijkstra 算法

Bellman-Ford 算法

SPFA 算法

SPFA 算法判复环

多源汇最短路

Floyd 算法

最小生成树算法

朴素 Prim 算法

Kruskal 算法

二分图

染色法判定二分图

匈牙利算法求二分图最大匹配

最近公共祖先（LCA）

爬山法

倍增法