图论

边的存储方式

1、vector储存

const int N = 1e5 + 7; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
int u[M], v[M], w[M];
ll d1[N], d2[N];//d1正向图，d2反向图
struct Node {
    int v;
    ll cost;
    bool operator < (Node b)const {
        return cost > b.cost;
    }
};
vector<Node> e[N];
int n, m;

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read(), w[i] = read();
        e[u[i]].push_back(Node{ v[i], w[i] });
        e[v[i]].push_back(Node{ u[i], w[i] });
    }
    return 0;
}

2、前向星保存

const int N = 5e3 + 7; //节点数
const int M = 5e3 + 7; //路径数
const int INF = 0x3f3f3f3f;
int head[N], tot = 0;//前向星变量
struct Node {
    //int u;
    int v, w, next;
} edge[M << 1];

void add(int u, int v, int w) {
    tot++;
    //edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}

dijkstra算法

单源最短路径（不存在负权边），从任意固定起点，前往另一个终点的最短路径算法。这里的是最小堆优化
时间复杂度

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
int u[M], v[M], w[M];
ll d1[N]; //d1正向图
struct Node {
    int v;
    ll cost;
    bool operator < (Node b)const {
        return cost > b.cost;
    }
};
vector<Node> e[N];
int n, m, st, ed;

void dijkstra(int s, ll d[]) {
    priority_queue<Node>  pq;
    fill(d, d + N, INF);
    d[s] = 0;
    pq.push(Node{ s,0 });
    while (!pq.empty()) {
        Node    x = pq.top();
        pq.pop();
        if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过
        for (auto it : e[x.v]) {
            if (d[it.v] > x.cost + it.cost) {
                d[it.v] = x.cost + it.cost;
                pq.push(Node{ it.v,d[it.v] });
            }
        }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read(), w[i] = read();
        e[u[i]].push_back(Node{ v[i], w[i] });
        e[v[i]].push_back(Node{ u[i], w[i] });
    }
    st = 1;
    dijkstra(st, d1);
    for (int i = 1; i <= n; ++i) {
        printf("%d->%d : %lld\n", st, i, d1[i]);
    }
    return 0;
}

spfa算法

如果边权为负值， 算法不能得到正确的结果，这个时候只能选择 算法，其他边权为正的图不要使用 ，容易被卡。例题
用途一：带负权值的单源最短路径
用途二：负环的判断，是否存在一个环，边权之和为负数

//判断负环
#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 2e3 + 5;
const int INF = 0x3f3f3f3f;
struct Node {
    int v, w;
};
int n, m, w, st, ed;
vector<Node>e[N];
int d[N];
bool vis[N];
queue<int>q;
int times[N];//记录松弛次数

int spfa(int s) {
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(times, 0, sizeof(times));
    while (!q.empty())  q.pop();//多组数据，处理前要全部清空
    q.push(s);
    vis[s] = 1;
    d[s] = 0;
    times[s] = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for (auto it : e[now])
            if (d[it.v] > d[now] + it.w) {
                d[it.v] = d[now] + it.w;
                ++times[it.v];//松弛次数加1
                if (times[it.v] == n) //如果已经有点松弛次数大于n
                    return 0;        //说明有负环,返回，不需要继续遍历
                if (!vis[it.v]) {
                    q.push(it.v);
                    vis[it.v] = 1;
                }
            }
    }
    return 1;//永远没有点松弛次数大于n，说明无负环
}
int main() {
    int T = read();
    while (T--) {
        n = read(), m = read(), w = read();
        for (int i = 1; i <= m; i++) {
            int u = read(), v = read(), w = read();
            e[u].push_back(Node{ v, w });
            e[v].push_back(Node{ u, w });//大于等于0时双向边
        }
        for (int i = 1; i <= w; ++i) {
            int u = read(), v = read(), w = read();
            e[u].push_back(Node{ v,-w });
        }
        st = 1;
        bool flag = spfa(st); //调用函数，起点为1
        if (flag) {  //不存在负环
            puts("NO");
            //输出各点最短路
            for (int i = 1; i <= n; ++i)
                printf("%d->%d : %d\n", st, i, d[i]);
        }
        else   puts("YES");
        for (int j = 1; j <= n; j++)
            e[j].clear();//清空
    }
    return 0;
}

floyd算法

上面给出的都是单源最短路径算法，如果需要知道任意两点之间的最短路径，需要使用floyd算法

// Floyd算法 O(N^3)  任意两点最短路
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 310; //节点数
int dp[N][N]; //表示从i->j的最短路径
int n, m;

void floyd() {
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; ++i)    dp[i][i] = 0;
    //dp初始化为邻接矩阵
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        dp[u][v] = min(dp[u][v], w);
    }
    for (int k = 1; k <= n; ++k) //经过编号不超过k的从i->k的最短路径
        //dp[k,i,j]=min(dp[k-1][i][j],dp[k-1][i][k] + dp[k-1][k][j])，
        //k是阶段，i，j是附加状态，再和背包问题一样利用滚动数组节省第一维
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}

int main() {
    n = read(), m = read();
    floyd();
    //输出
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            printf("%d ", dp[i][j]);
        puts("");
    }
    return 0;
}

最小生成树，kruskal算法和prim算法

算法适用于稠密图，建立一颗最小生成树，而 算法适用于稀疏图建立最小生成树，特别是完全图的最小生成树建立。两种算法都是基于贪心的思想，一个无向图中权值最小的边一定在最小生成树中。

//kruskal 适用于稀疏图  O(n+m*log2(m))
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 6e3 + 7; //节点
const int M = 6e3 + 7; //路径数
int n, m;
struct Edge {
    int u, v, w;
    bool operator <(const Edge tmp) const {
        return w < tmp.w;
    }
}edge[M];
int father[N];
ll ans = 0; //最小生成树的花费和

int find(int root) {
    int son = root;
    while (root != father[root])
        root = father[root];
    while (son != root) { //路径压缩
        int temp = father[son];
        father[son] = root;
        son = temp;
    }
    return root;
}

void kruskal() {
    for (int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v;
        int x = find(u), y = find(v);
        if (x != y) {
            father[x] = y;
            ans += edge[i].w;
        }
    }
}
int main() {
    int T = read();
    while (T--) {
        n = read(), m = read();
        for (int i = 1; i <= n; ++i)
            father[i] = i;
        for (int i = 1; i <= m; ++i)
            edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
        sort(edge + 1, edge + 1 + m);
        kruskal();
    }
    return 0;
}

//无向图最小生成树
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 3e3 + 7;
const int INF = 0x3f3f3f3f;
int e[N][N], vis[N], dis[N];
int n, m;
ll ans;
//prim适合稠密图 O(n^2)，特别是完全图最小生成树的求解
void prim() {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 1; i < n; ++i) {
        int x = 0;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && (x == 0 || dis[j] < dis[x]))
                x = j;
        vis[x] = 1;
        for (int j = 1; j <= n; ++j)//用u点更新  刚刚新拓展的边
            if (!vis[j])    dis[j] = min(dis[j], e[x][j]);
    }
}

int main() {
    n = read(), m = read();
    //构建邻接矩阵
    memset(e, 0x3f, sizeof(e));
    for (int i = 0; i <= n; ++i)    e[i][i] = 0;
    for (int i = 1; i <= m; ++i) {
        int x = read(), y = read(), z = read();
        e[x][y] = e[y][x] = min(e[x][y], z);
    }
    //求最小生成树
    prim();
    for (int i = 2; i <= n; ++i)    ans += dis[i];
    printf("%lld\n", ans);
    return 0;
}

拓扑排序

拓扑排序是用于有向图判断不存在有向环。入队点数小于总节点数，存在环。
而Kruskal跑并查集是判断无向图存在环。并查集连通块父节点不统一，存在环。
实现思路，首先入度为0的节点入队。
再去跑这个队列，遍历全部入度为0的节点，把他们连接的边去掉，就是终点入度-1，如果终点入度为0了，终点入队。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e3 + 7;
int in[N];
int n, m; // 节点数，边数
vector<int>edge[N];

void topsort() {
    queue<int>q; //如果要按字典序，使用最小堆即可
    for (int i = 1; i <= n; i++)  //n  节点的总数
        if (in[i] == 0) q.push(i);  //将入度为0的点入队列
    vector<int>ans;   //ans 为拓扑序列
    while (!q.empty()) {
        int p = q.front(); q.pop(); // 选一个入度为0的点，出队列
        ans.push_back(p);
        for (int i = 0; i < edge[p].size(); i++) {
            int y = edge[p][i];
            in[y]--;
            if (in[y] == 0)
                q.push(y);
        }
    }
    if (ans.size() == n) {
        for (int i = 0; i < ans.size(); i++)
            printf("%d ", ans[i]);
        printf("\n");
    }
    else printf("No Answer!\n");   //  ans 中的长度与n不相等，就说明无拓扑序列

}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        edge[u].push_back(v);
        ++in[v];
    }
    topsort();
    return 0;
}