图的算法整理总结

从自己写的图的相关题目中做下总结，总体而言需要总结整理的是图的建图方法和迪杰斯特拉算法的相关原理等。

建图

1. 根据输入用邻接表建图

这种建图的方法和在树章节中常用的建图方法相同，可以配合使用优化过的迪杰斯特拉算法，对于这种方法要记住的是add函数。

2. 根据输入用临界矩阵建图

临界矩阵建图是非常方便的，但是由于数组空间的存储问题，邻接矩阵的数组不能够开的太大。一般的顶点数目在0-500内都可以考虑使用邻接矩阵，邻接矩阵能够配合朴素迪杰斯特拉算法使用，并且算法的编写较为简单。

3. 根据输入直接定义简单的结构体来记录下每一条边

典型的在k着色问题和拓扑序列的判断问题上，都是使用了这种存储图的方法。这种存储方法是只用结构记录每一条边的起点和终点。使用这种方法的场合在顶点数目非常多，如大于10000时，同时边比较少的时候。同时要判断一下如果常规建图使用的算法和这种方式建图使用的方法时间复杂度差不多的话，就可以使用这种方法。

迪杰斯特拉算法

对于迪杰斯特拉算法使用的时候很重要的一步就是要了解他是怎么选出点来的，以及这个算法正确性的证明能够帮助理解点的选取。
这个算法在更新距离的时候是很好理解的。往往不好理解的地方在于，在选出一个距离最小点的时候还要记录一些满意度、幸福感之类的最大值，这些的记录反而难以理解。在这个更新过程中，很容易联系动态规划的思想，这一步的更新状态，很可能需要通过上一步状态的计算。因此在使用这个算法的时候，在更新状态时，也和写动态规划的相关题目相似，在更新状态时候只考虑当前这步和上一步或者是上两步，而不考虑自开始点的所有情况，如果从开始点考虑，则会把自己弄晕。
由于迪杰斯特拉算法的正确性，在使用迪杰斯特拉算法的时候，在更新状态的时候要想到集合的划分，具体情况如下图：

深度优先遍历

1. 可以通过深度优先遍历并且记录编号的方法来求连通分量的数量，也可以求出每个连通分量中的点数。

拓扑排序

1. 求一个图的拓扑排序，可能要借助邻接表和栈去求。
2. 判断某个序列是不是图的拓扑排序可以利用如下的充分必要条件，某个序列一定是拓扑排序 == 图中所有边的起点在这个排序中的位置都在终点的前面。这个实际上就是拓扑序列的定义。

拓扑序列的代码如下，实际上是bfs的一种变形：

bool topsort(){
    while(!qq.empty()){
        int c = qq.front();
        qq.pop_front();
        for(int i = h[c]; ~i; i = ne[i]){
            int ed = e[i];
            --d[ed];
            if(d[ed] == 0){
                qq.push_back(ed);
            }
        }
        res.push_back(c);
    }
    return res.size() == n;
}

最小生成树

1. 普里姆算法

普里姆算法为选点法，时间复杂度是直接依赖于点数的，一般都使用朴素的普里姆算法，如果在点多的情况下普里姆算法不合适了，可以选用克鲁斯卡尔。
目前来看普里姆算法适用于各种情况，即使有负边、回路、自环都行。

int Prim(){
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for(int i = 0; i < n; ++i){
        int t = -1;
        for(int j = 1; j <= n; ++j){
            if(!st[j] && (t == -1 || dist[t] > dist[j])){
                t = j;
            }
        }
        st[t] = true;
        if(i && (dist[t] == INF)){
            return INF;
        }
        if(i){
            res += dist[t];
        }
        for(int j = 1; j <= n; ++j){
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}

2. 克鲁斯卡尔算法

克鲁斯卡尔算法用代码实现起来非常简单，只需要用到并查集相关的知识。在点多边少的情况下可以选用。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010;
const int M = 200010;

int n, m;
int per[N];
struct edge{
    int a;
    int b;
    int w;
};
edge e[M];

bool cmp(const edge& e1, const edge& e2){
    return e1.w < e2.w;
}

int find(int x){
    if(per[x] == x){
        return x;
    }
    return per[x] = find(per[x]);
}

int main(void){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].w);
    }
    sort(e, e + m, cmp);
    for(int i = 1; i <= n; ++i){
        per[i] = i;
    }
    int res = 0, cnt = 0;
    for(int i = 0; i < m; ++i){
        int x = find(e[i].a);
        int y = find(e[i].b);
        if(x != y){
            per[x] = y;
            res += e[i].w;
            cnt++;
        }
    }
    if(cnt == n - 1){
        printf("%d", res);
    }else{
        printf("impossible");
    }
}