图

图的存储

1. 邻接矩阵
2. 邻接表-链式前向🌟

图的最短路径问题

1. 单源最短路径

1. dijkstra算法-heap优化，$O(mlog^n)$的时间复杂度，只能处理边权为正数的问题
2. 队列优化的bellman-ford算法，$O(km)$的时间复杂度，处理边权为负数多情况，在网格图中效率低
   说明：这两种算法的证明对于理解算法和记忆很重要

dijkstra算法-heap优化-邻接表

const int N = 1010, M = 1000010;
struct edge {  //将每条边看成一个结构体
    int e, v, next;  //终点， 权值，下一条边
} ed[M];
struct node {
    int now, dis;  //扩展的点序号，距离
    bool operator< (const node &a) const {  //由于堆堆性质，这种方法需要重载小于号
        return this->dis > a.dis;
    }
};
int n, m;
int cnt;  //计数有多少条边
int h[N], mark[N], dist[N];   //h[i]为每个点指向的第一条边，标记是否找到最近距离，记录当前最近距离

void add(int s, int e, int v) {
    ed[cnt].e = e;
    ed[cnt].v = v;
    ed[cnt].next = h[s];
    h[s] = cnt++;  //类似链表点头插法
}

void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<node> hp;

    hp.push({1, 0});
    dist[1] = 0;
    while (!hp.empty()) {
        node t = hp.top();   //堆顶元素是所有扩展的中的最近的点
        hp.pop();
        int now = t.now, dis = t.dis;
        if (mark[now]) continue;  //当前这个点是否已经找到最短距离
        mark[now] = 1;
        for (int i = h[now]; i != -1; i = ed[i].next) {  //对这个点进行扩展，当前这个点是最短距离
            int e = ed[i].e;
            if (dist[e] > dis + ed[i].v) {
                dist[e] = dis + ed[i].v;
                hp.push({e, dist[e]});
            }
        }
    }
}

int main() {
    cin >> m >> n;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < m; i++) {
        int s, e, v;
        cin >> s >> e >> v;
        add(s, e, v);
        add(e, s, v);
    }
    dijkstra();
    cout << dist[n] << endl;
    return 0;
}

队列优化的bellman-ford–spfa–邻接表

const int N = 1010, M = 2000010;

struct edge {
    int e, v, next;
} ed[M];
int hd[N];
int cnt;

int n, m;
int dist[N], q[N], mark[N];  //dist标记每个点到1号点的最短距离
//队列， mark用来标记该点是否在队列中
void add(int s, int e, int v) {
    ed[cnt].e = e;
    ed[cnt].v = v;
    ed[cnt].next = hd[s];
    hd[s] = cnt++;
}

void spfa() {
    memset(dist, 0x3f, sizeof(dist));
    int h = 0, t = 0;
    dist[1] = 0;
    q[t++] = 1, mark[1] = 1;
    while (h != t) {
        int tmp = q[h++];
        mark[tmp] = 0;  //这里需要置为0，否则其他点更新该点时
        //不会将该点入队列
        if (h == n) h = 0;  //循环队列
        for (int i = hd[tmp]; i != -1; i = ed[i].next) {
            int e = ed[i].e, v = ed[i].v;
            if (dist[e] > dist[tmp] + v) {
                dist[e] = dist[tmp] + v;
                if (mark[e] == 0) {  //如果已经在队列中，则不入
                    mark[e] = 1;
                    q[t++] = e;
                    if (t == n) t = 0;
                }
            }
        }
    }
}

int main() {
    memset(hd, -1, sizeof(hd));
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        int s, e, v;
        cin >> s >> e >> v;
        add(s, e, v);
        add(e, s, v);
    }
    spfa();
    cout << dist[n] << endl;

    return 0;
}

多源最短路径

1. floyd算法-$O(n^2)$

const int N = 1010, M = 2000010, INF = 0x3f3f3f3f;
int n, m;
int d[N][N];  //存储两点之间多最短距离

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = (i == j ? 0 : INF);
        }
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = min(c, d[a][b]);
    }

    for (int k = 1; k <= n; k++) {  //中转点
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    cout << d[1][n] << endl;
    return 0;
}

最小生成树

1. kruskal-对边进行选择-适合稀疏图-$O(mlog^m)$
2. prim-对点进行选择-适合稠密图-$O(n^2)$

kruskal-并查集

const int N = 1010, M = 2000010;
struct edge {
    int s, e, v;
    bool operator< (const edge &a) const {
        return this->v < a.v;
    }
}ed[M];
int n, m;
int ans, f[N], res, already = 1;  //res记录生成树的长度总和，already记录了并查集中最终一共有多少点

int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);  //每个点的祖先都是和其祖先的祖先相同
    //最终会造成一群点的祖先都相同，等于一个点，这个点的祖先就是自己
    return f[x];  
}

int kruskal() {
    int res = 0;
    for (int i = 1; i <= n; i++) f[i] = i;  //初始化，开始时，每个节点的祖先都是自己
    sort(ed, ed + m);
    for (int i = 0; i < m; i++) {
        int s = ed[i].s, e = ed[i].e;
        if (find(s) != find(e)) {  //当前这条边的两个节点的祖先不相同
                                   //即不是同一棵生成树上的两个点
            already++;
            res += ed[i].v;
            f[find(s)] = find(e);  //让s的祖先的祖先变成，e的祖先的祖先变成
            //这样与s相连通的所有的点的祖先都成了e点的祖先
            if (already == n) break;
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> ed[i].s >> ed[i].e >> ed[i].v;
    }
    if (already == n) cout << res << endl;
    else cout << "没有最小生成树" << endl;

    return 0;
}

prim-双重暴力-代码简洁

const int N = 1010, M = 2000010;
int n, m;
int dist[N], mark[N], g[N][N]; //dist表示当前点到当前集合到最短边的长度
//mark表示当前带你是否在生成树集合中，g表示两点之间边的长度

int prim() {
    int res = 0;
    for (int i = 1; i <= n; i++) dist[i] = g[i][1];  //dist记录的是点到生成树到最短距离，因此需要初始化
    //memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for (int i = 1; i <= n; i++) {
        int id = -1, min_dist = 0x3f3f3f3f;
        for (int j = 1; j <= n; j++) {  //每次选择一个到生成树距离最短的点
            if (!mark[j] && dist[j] < min_dist) {
                id = j;
                min_dist = dist[j];
            }
        }
        mark[id] = 1;
        res += dist[id];
        for (int j = 1; j <= n; j++) {  //并利用此点更新所有未在生成树中的点点距离
            if (!mark[j]) dist[j] = min(dist[j], g[id][j]);
        }
    }
    return res;
}

int main() {
    //memset(dist, 0x3f, sizeof(dist));
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int s, e, v;
        cin >> s >> e >> v;
        g[s][e] = g[e][s] = min(g[s][e], v);
    }
    cout << prim() << endl;
    return 0;
}