图论算法

有向图、无向图

有权图、无权图

有向图：度 = 出度 + 入度

完全图：所有点可直接到达其他所有点

环：从一点出发，又可回到该点（只在有向图中讨论）

图的存储

邻接矩阵：

• 矩阵大小：m × m，m 代表点的个数
• 矩阵内容：0 为 i 和 j 不连通，a 为 i 和 j 连通，且权值为 a

邻接表（C语言）：

• 表的大小：m 个二元组(tuple)及m个动态数组。
• 二元组内容：第一个元素为指针地址，指向实际存储“边的内容”的数组首地址；第二个元素为该数组所存储元素的个数。
• 动态数组内容：x个二元组(tuple)。其中第一个元素为可到达的点；第二个元素为权值。

邻接表（STL模板）：

• 表的大小：m 个可动态开辟空间的 vector（二维 vector）。

• vector<vector<tuple>> table(m, vector<tuple>());
  

• 顺序容器的内容：二元组(tuple)。其中第一个元素为可到达的点；第二个元素为权值。

链式前向星：

• 把邻接表中用来存储“边的内容”的各个小数组合一起，组成一个大的存储“边的内容”的大数组，原本的数组首地址改为所存放的最后一条边在该数组中的地址偏移，也就是索引。

最短路径

Floyd算法（弗洛伊德）—— 多源最短路径：

• 思想：遍历并更新所有“经过中转”与“不经过中转”的最小值

• 不变性（单次循环的正确性）：确实能记录“经过 h ”与“不经过 h ”的最小值

• 单调性（问题规模不断缩小）：外循环每运行一次都能压缩一条路径

• 1 -> 3 -> 2 -> 4 可变成 1 -> 3 -> 4 再变成 1 -> 4

• 时间复杂度：O(n^3)

memset(arr, 0x3F, sizeof(arr)); //初始化为极大值

for (int h = 0; h < n; h++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            arr[i][j] = min(arr[i][j], arr[i][h] + arr[h][j]);
        }
    }
}

Dijkstra算法（迪科斯彻）—— 单源最短路径：

• 边的权值不能是负数，因为Dijkstra算法认为“只要结果被更新过就没必要再搜索该点”（可去除的小边界），“只要队列的值比结果中的大就没必要继续搜索”（终极边界），而如果出现负数的情况则不然。但是如果去除迪科斯彻认为的条件，则该算法会因失去终止边界而一直广搜下去，也就是说此时的算法已经不满足有穷性的条件了，不能称之为算法。
• 未进行堆优化前，每个点的所有边都需要遍历，而每个点最多可有n条边，故时间复杂度：O(n^2)
• 进行堆优化后，可能要对所有的边（共m条）都进行堆插入操作，故时间复杂度：O(mlogn)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <vector>
#include <queue>
using namespace std;

struct edge {
    int next_vex, weight;
};

struct node {
    int vex, dis;
    bool operator<(const node &b) const{ //常成员函数，必须加上const
        return this->dis > b.dis; //所有的成员函数都有一个“this指针”的隐含参数（默认是大顶堆）
    }
};

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<edge> > edges(n + 5, vector<edge>()); //防止编号是从1开始的
    for (int i = 0; i < m; i++) {
        int a, b, c;
        //cin >> a >> b >> c;
        scanf("%d%d%d", &a, &b, &c);
        edges[a].push_back((edge){b, c});
        edges[b].push_back((edge){a, c});
    }
    int dis_min[n + 5];
    memset(dis_min, -1, sizeof(dis_min));
    priority_queue<node> que;
    que.push((node){s, 0});
    while (!que.empty()) {
        node now = que.top();
        que.pop();
        if (now.dis > dis_min[now.vex]) continue; //终极边界
        dis_min[now.vex] = now.dis;
        for (int i = 0; i < edges[now.vex].size(); i++) {
            int next_vex = edges[now.vex][i].next_vex;
            int weight = edges[now.vex][i].weight;
            if (dis_min[next_vex] != -1) continue; //堆优化后的小边界
            que.push((node){next_vex, now.dis + weight});
        }
    }
    for (int i = 1; i <= n; i++) {
        //cout << dis_min[i] << endl;
        printf("%d\n", dis_min[i]);
    }
    return 0;
}

可采用OJ上第746的“最短路”题进行测试

Bellman-Ford算法（贝尔曼-福特）—— 单源最短路径：

特点：支持边的权值为负数

用队列装载可到达的点，遍历所有的边（共m条），得到按"当前顺序"遍历时的最小距离，循环以上操作，当最小距离不再更新时停止，最多可能循环n-1次，n为点的个数。

时间复杂度：O(km) - O(nm)，其中k是小常数

最小生成树

Kruskal算法（克鲁斯卡尔）：

将所有的边按权重排序，从小到大取出，若这条边所连接的两个结点均在同一集合中，则丢弃；反之，则合并（即并查集问题）。最后当用于合并的边的数量等于结点的数量-1时即可终止程序。

适用于结点较多，边较稀疏的情况

Prim算法（普里姆）：

将任一结点所有的边都放入优先队列中，并取出其中权重最小的一条，连接新的节点，并把其所有的边也放入优先队列中，重复以上步骤直至把所有的结点都连接完成。

适用于结点较少，边较稠密的情况

拓扑排序

拓扑排序问题只局限于有向图的情况，且不能成环（可用该特性判别是否成环）

输出其中一种拓扑排序的方法：

将所有入度为0的结点放入队列中，取出队列中的结点，同时相应的下一个结点入度-1，若其入度为0，则将其也放入队列中，反之跳过，重复以上操作，直至队列为空。

输出所有可能的拓扑排序的方法（归根结底还是排列组合问题）：

将所有的结点都放入顺序表中进行递归。在递归函数中，若入度为0，则对其进行标记，同时相应的下一个结点入度-1，并进入到下一层递归函数中；最终当所有结点都标记完毕后则输出；向上回溯时再逐个解除标记，同时相应的下一个结点入度+1。