图论

稀疏图与稠密图

概念：
  有很少条边或弧的图称为稀疏图，反之称为稠密图。 这里稀疏和稠密是模糊的概念，都是相对而言的。目前为止还没有给出一个量化的定义。比方说一个有 100 个顶点、200 条边的图，与 100 个顶点组成的完全图相比，他的边很少，也就是所谓的稀疏了。
用n表示图中顶点数目，用e表示图中边或弧的数目
  稀疏图: e < nlogn
  稠密图: e > nlogn
若图中边或弧上有权，则该图称为网
  稠密图用邻接矩阵存储
  稀疏图用邻接表存储

原因：
  邻接表只存储非零节点，而邻接矩阵则要把所有的节点信息(非零节点与零节点)都存储下来。
  稀疏图的非零节点不多，所以选用邻接表效率高，如果选用稠密图就会造成很多空间的浪费，矩阵中大多数都会是零节点！稠密图的非零界点多，零节点少，选用邻接矩阵是最适合不过！

树与图的dfs

树的重心

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

删除 1 号点，剩余各个连通块中点数的最大值最小为 4 .

思路 ： 统计删除结点中（包括删除的结点 size）的每颗子树中的最大结点数 ， n - size 统计已删除结点的父结点中结点数

//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数
        }
    }

    //n-sum 如图中的n-size值，不包括根节点4；
    res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
    return sum;
}

树与图的bfs

图中点的层次

走迷宫找 1 号点到 n 号点的最短距离，但是可能存在环

void bfs(int u){
    memset(d, -1, sizeof d);
    d[1] = 0;
    q.push(u);
    
    while(q.size()){
        int c = q.front();
        q.pop();
        for(int i = h[c]; ~ i; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[c] + 1;
                q.push(j);
            }
        }
    }
}

最短路问题

Dijkstra

迪杰斯特拉算法采用的是一种贪心的策略。

Dijkstra求最短路 I $(O(n^2))$

void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));//dist 数组的各个元素为无穷大
    dist[1] = 0;//源点到源点的距离为置为 0
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)//遍历 dist 数组，找到没有确定最短路径的节点中距离源点最近的点t
        {
            if (!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        state[t] = 1;//state[i] 置为 1。

         for (int j = 1; j <= n; j++)//遍历 t 所有可以到达的节点 i
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);//更新 dist[j]
        }


    }
}

Dijkstra求最短路 II $(O(mlogn))$

算法的主要耗时的步骤是从dist 数组中选出：没有确定最短路径的节点中距离源点最近的点 t。只是找个最小值而已，没有必要每次遍历一遍dist数组。

在一组数中每次能很快的找到最小值，很容易想到使用小根堆。可以使用库中的小根堆。

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
    heap.push({0, 1});//插入距离和节点编号

    while (heap.size())
    {
        auto t = heap.top();//取距离源点最近的点
        heap.pop();

        int ver = t.second, distance = t.first;//ver:节点编号，distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定，则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});//距离变小，则入堆
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

bellman-ford

松弛的概念:

1. 考虑节点u以及它的邻居v，从起点跑到v有好多跑法，有的跑法经过u，有的不经过。
2. 经过u的跑法的距离就是distu + u到v的距离。
3. 所谓松弛操作，就是看一看distv和distu + u到v的距离哪个大一点。
   如果前者大一点，就说明当前的不是最短路，就要赋值为后者，这就叫做松弛。

Bellman_ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n - 1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

有边数限制的最短路

为什么是dist[n] > 0x3f3f3f3f/2， 而不是dist[n] > 0x3f3f3f3f ?
5号节点距离起点的距离是无穷大，利用5号节点更新n号节点距离起点的距离，将得到$10^9−2$, 虽然小于$10^9$, 但并不存在最短路，(在边数限制在k条的条件下)。

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环 走过k条边
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else return dist[n];
}

spfa

Bellman_ford 算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。

Bellman_ford 算法里最后return -1的判断条件写的是dist[n] > 0x3f3f3f3f/2;而 spfa 算法写的是 dist[n] == 0x3f3f3f3f 其原因在于 Bellman_ford 算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的 n 和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。

Bellman_ford 算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；但是 SPFA 算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用 SPFA 否则会死循环。

由于 SPFA 算法是由 Bellman_ford 算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 O(nm) ，假如题目时间允许可以直接用 SPFA 算法去解 Dijkstra 算法的题目。

求负环一般使用SPFA算法，方法是用一个cnt数组记录每个点到源点的边数，一个点被更新一次就 +1，一旦有点的边数达到了 n 那就证明存在了负环。

spfa求最短路

int spfa(){
    queue<PII> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push({0, 1});
    st[1] = true;
    while(q.size()){
        PII p = q.front();
        q.pop();
        int t = p.se;
        st[t] = false;//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        for(int i = h[t]; i != -1;i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i]; 
                if(!st[j]){//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率
                    st[j] = true;
                    q.push({dist[j],j});
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

spfa判断负环

方法 1：统计每个点入队的次数，如果某个点入队 n 次，则说明存在负环

方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于 n，则也说明存在环

bool spfa(){
    // 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新

    queue<int> q;

    //不仅仅是1了， 因为点1可能到不了有负环的点， 因此把所有点都加入队列
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }

    while(q.size()){
        int t = q.front();
        q.pop();
        st[t]=false;
        for(int i = head[t];i!=-1; i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j] = dist[t]+w[i];
                cnt[j] = cnt[t]+1;
                if(cnt[j]>=n){
                    return true;
                }
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

Floyd

Floyd求最短路

d[i][k] 是 INF 但是 d[k][j]是 -2 因为 i 是到不了 k 的, 所以 k 也是到不了 j 的, 那么 i 就到不了 j .

void floyd() {
    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]);
}

最小生成树问题

Prim

Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

Prim算法求最小生成树

bool prim(){
    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[t] > dist[j]))
                t = j;
        }
        if(dist[t] == 0x3f3f3f3f)return true; //处理独立点，判断是否连通，有无最小生成树
        st[t] = true;
        res += dist[t];
        for (int j = 1; j <= n; j ++ ){
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return false; 
}

Kruskal

Kruskal算法求最小生成树

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

using namespace std;
const int N = 100010;
int p[N];//保存并查集

struct E{
    int a;
    int b;
    int w;
    bool operator < (const &W) const{//通过边长进行排序
        return w < W.w;
    }

}edg[N * 2];
int res = 0;

int n, m;
int cnt = 0;
int find(int a){//并查集找祖宗
    if(p[a] != a) p[a] = find(p[a]);
    return p[a];
}
void kruskal(){
    for(int i = 1; i <= m; i++)//依次尝试加入每条边
    {
        int pa = find(edg[i].a)；// a 点所在的集合
        int pb = find(edg[i].b);// b 点所在的集合
        if(pa != pb){//如果 a b 不在一个集合中
            res += edg[i].w;//a b 之间这条边要
            p[pa] = pb;// 合并a b
            cnt ++; // 保留的边数量+1
        }
    }
}
int main()
{

    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;//初始化并查集
    for(int i = 1; i <= m; i++){//读入每条边
        int a, b , c;
        cin >> a >> b >>c;
        edg[i] = {a, b, c};
    }
    sort(edg + 1, edg + m + 1);//按边长排序
    kruskal();
    if(cnt < n - 1) {//如果保留的边小于点数-1，则不能连通
        cout<< "impossible";
        return 0;
    }
    cout << res;
    return 0;
}

二分图问题

定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。

判定二分图

1. 开始对任意一未染色的顶点染色。
2. 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。
3. 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

   染色法判定二分图

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

using namespace std;

const int N = 100010 * 2;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int color[N];//保存各个点的颜色，0 未染色，1 是红色，2 是黑色
int n, m;//点和边

void add(int a, int b)//邻接表插入点和边
{
    e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}

bool dfs(int u, int c)//深度优先遍历
{
    color[u] = c;//u的点成 c 染色

    //遍历和 u 相邻的点
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int b = e[i];                   
        if(!color[b])//相邻的点没有颜色,则递归处理这个相邻点
        {
            if(!dfs(b, 3 - c)) return false;//（3 - 1 = 2， 如果 u 的颜色是2，则和 u 相邻的染成 1）
         //（3 - 2 = 1， 如果 u 的颜色是1，则和 u 相邻的染成 2）
        }
        else if(color[b] && color[b] != 3 - c)//如果已经染色，判断颜色是否为 3 - c
        {                                     
            return false;//如果不是，说明冲突，返回                   
        }
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表
    cin >> n >> m;
    for(int i = 1; i <= m; i++)//读入边
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for(int i = 1; i <= n; i++)//遍历点
    {
        if(!color[i])//如果没染色
        {
            if(!dfs(i, 1))//染色该点，并递归处理和它相邻的点
            {
                cout << "No" << endl;//出现矛盾，输出NO 
                return 0;
            }

        }
    }
    cout << "Yes" << endl;//全部染色完成，没有矛盾，输出YES
    return 0;
}

匈牙利算法

二分图的最大匹配

一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

//递归找可以匹配的点
bool find(int x){
    // 和各个点尝试能否匹配
    for(int i = h[x]; i != -1; i = ne[i]){
        int b = e[i];
        if(!st[b]){//打标记
            st[b] = 1;
            // 当前尝试点没有被匹配或者和当前尝试点匹配的那个点可以换另一个匹配
            if(match[b] == 0 || find(match[b])){
                // 和当前尝试点匹配在一起
                match[b] = x;
                return true;
            }
        }
    }
    return false;
}