图论

1. 图的基本概念

(1) 有向图、无向图
(2) 度数（出度、入度）
(3) 简单图：不存在顶点到其自身的边，且同一条边不重复出现
(4) 路径、环、简单路径
(5) 无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边
(6) 有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧
(7) 稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。

2. 图的存储及基本操作

(1) 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度：O(n^2)。无法存重边。
(2) 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：O(n + m)。可存重边。
(3) 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：O(n + m)。可存重边。
(4) 十字链表，适用于稀疏图，可存有向图、无向图。不常用。空间复杂度：O(n + m)。无法存重边
(5) 三元组表，适用于稀疏图，可存有向图，无向图。常用于Bellman-Ford算法、Kruskal算法。空间复杂度：O(m)。可存重边。

3. 图的遍历

(1) 深度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)
(2) 广度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

struct Node {

    int id;
    Node * next;
    Node(int _id) : id(_id), next(NULL) {}
} * head[N]; // head[i]为邻接表头指针

int n, m;
int q[N];
bool st[N];

void add(int a, int b) {

    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int u) {

    st[u] = true;
    printf("%d ", u);

    for (auto p = head[u]; p; p = p->next)
        if (!st[p->id]) dfs(p->id);
}

void bfs() {

    int hh = 0, tt = -1;
    q[++tt] = 1;
    st[1] = true;

    while (hh <= tt) {

        int t = q[hh++];
        printf("%d ", t);

        for (auto p = head[t]; p; p = p->next) {
            int j = p->id;
            if (!st[j]) {
                q[++tt] = j;
                st[j] = true;
            }
        }
    }
}

int main() {

    cin >> n >> m;
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    // for (int i = 1; i <= n; i++)
    //     if (!st[i]) dfs(i);

    bfs();

    return 0;
}

4. 拓扑排序

bfs

#include<iostream>

using namespace std;

const int N = 100010;

struct Node {

    int id;
    Node * next;
    Node(int _id) : id(_id), next(NULL) {}
} * head[N];
// head[N] 是邻接表的头指针数组

int n, m;
int q[N], d[N];

void add(int a, int b) {
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort() {

    int hh = 0, tt = -1;

    // 将所有入度为0的结点入队
    for (int i = 1; i <= n; i++)
        if (!d[i]) q[++tt] = i;

    while (hh <= tt) {

        int t = q[hh++];
        // 删掉队头结点后，若其存在入度为0的“后继”，入队
        for (auto p = head[t]; p; p = p->next)
            if (--d[p->id] == 0) q[++tt] = p->id;
    }

    // tt指向当前队尾元素，等于n-1说明存在拓扑序列
    return tt == n - 1;
}

int main() {

    cin >> n >> m;
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
        d[b]++;
    }

    if (!topsort()) puts("-1");
    else {
        for (int i = 0; i < n; i++)
            printf("%d ", q[i]);
    }

    return 0;
}

dfs

#include<iostream>

using namespace std;

const int N = 100010, M = 100010;

struct Node {
    int id;
    Node * next;
    Node(int _id) : id(_id), next(NULL) {}
} * head[N];

int n, m;
int st[N], q[N], top;

void add(int a, int b) {

    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool dfs(int u) {

    st[u] = 1; // 1表示在栈中

    for (auto p = head[u]; p; p = p->next) {

        int j = p->id;
        // j结点没有被遍历过，但图存在环，返回false
        if (!st[j] && !dfs(j)) return false;
        else if (st[j] == 1) return false;
    }
    // 走到这里即将回溯，说明u结点再无“后继”，此时队列为拓朴序列的逆序
    q[top++] = u;
    st[u] = 2;
    return true;
}

bool top_sort() {

    for (int i = 1; i <= n; i++)
        if (!st[i] && !dfs(i)) return false;

    return true;
}

int main() {

    cin >> n >> m;
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    if (!top_sort()) puts("-1");
    else {
        for (int i = n - 1; i >= 0; i--)
            printf("%d ", q[i]);
    }

    return 0;
}

5. 最小生成树

1> 朴素prim

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N], pre[N];
// 邻接矩阵、结点i到集合的最短距离、结点i的“引荐人”
bool st[N]; // 结点 i 是否在集合中

int prim() {

    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
    int res = 0;

    // 将“把第一个点加入生成树”的操作合并写了
    // 因此i从0开始，并且后面也有关于i == 0的条件判断
    for (int i = 0; i < n; i++) {

        int t = -1; // 这么写是为了：找到第一个集合外的点后，t = j，便于求距离最短的点
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        if (i && dist[t] == INF) return INF;

        // 理解为什么“先算再更新”（权更小的自环）
        if (i) res += dist[t];
        st[t] = true;

        // 结点t加入后，其他点到集合的距离可能会缩短，因此更新
        for (int j = 1; j <= n; j++)
            if (!st[j] && dist[j] > g[t][j]) {
                dist[j] = g[t][j];
                pre[j] = t; // 目前j到集合的最短距、(t, j)为这条边
            }


    }

    return res;
}

void get_path() {

    for (int i = n; i > 1; i--) {
        cout << '(' << pre[i] << ',' << i << ')' << ' ';
    }
}

int main() {

    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while (m--) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);

        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d", t);

    get_path();

    return 0;
}

2> 朴素kruskal

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

struct edge {

    int a, b, w;
    bool operator<(const edge &W)const {
        return w < W.w;
    }
} edges[M];

int n, m;
int p[N];

int find(int x) {

    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {

    cin >> n >> m;
    for (int i = 0; i < m; i++) {

        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    sort(edges, edges + m);

    for (int i = 0; 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;
            cnt++;
            res += w;
        }
    }

    if (cnt < n - 1) puts("impossible");
    else cout << res;

    return 0;
}

6. 最短路径

1> 朴素dijkstra

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N];
bool st[N];

int dijkstra() {

    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i++) {

        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

    }

    if (dist[n] == INF) return -1;

    return dist[n];
}

int main() {

    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

    while (m--) {

        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);

        g[a][b] = min(g[a][b], w);
    }

    cout << dijkstra() << endl;

    return 0;
}