DFS

DFS算法是一一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为O(N)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。

邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O(N),此时，总的时间复杂度为 O(N+E)。

邻接矩阵表示时，查找每个顶点的邻接点所需时间为 O(N)，要查找整个矩阵，故总的时间度为O(N^2) 。

void dfs(int k){
    if(k == n){
        for(int i = 0; i < n; i++){
            printf("%d ", path[i]);
        }
        printf("\n");
    }

    for(int i = 1; i <= n; i++){
        if(!visit[i]){
            path[k] = i;
            visit[i] = 1;
            dfs(k + 1);
            visit[i] = 0;
        }
    }
}

int main(){
    cin >> n;
    memset(visit, 0, sizeof(visit));
    dfs(0);
    return 0;
}

BFS

int bfs(int x, int y){
    queue<PII> q;
    memset(d, -1, sizeof d);
    d[x][y] = 0;
    q.push({x, y});
    while(!q.empty()){
        PII t = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = t.first + dx[i], ny = t.second + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 0 && d[nx][ny] == -1){
                d[nx][ny] = d[t.first][t.second] + 1;
                q.push({nx, ny});
            }
        }
    }
    return d[n - 1][m - 1];
}

树与图的DFS

#include <bits/stdc++.h>

using namespace std; 
typedef unsigned long long ULL;
const int N = 100010, M = 2 * N; //N是点数，M是边数

int n, m, a, b;
int h[N], e[M], ne[M], idx; 
//h[i]是每个点对应的邻接链表 e[i]每条边所指向的点 ne[i]每条边的下一条边 idx表示第几条边
int ans = N;
bool st[N]; //记录每个点是否已被遍历过

//添加边 
int add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//以u为根节点的子树的点数
int dfs(int u){
    st[u] = true;
    int sum = 0;  //记录以当前点为根节点的子树的总点数
    int size = 0; //记录以当前点为重心的所有连通块的点数的最大值

    //遍历当前根节点的所有相邻边
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i]; //遍历每条边所指向的那个点
        if(st[j]) continue;
        int tmp = dfs(j);
        size = max(size, tmp);
        sum += tmp;
    }

    size = max(size, n - sum - 1);
    ans = min(ans, size);
    return sum + 1;
}
int main(){
    cin >> n;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < n - 1; i ++ ){
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;    
}

树与图的BFS

#include <bits/stdc++.h>

using namespace std; 
const int N = 100010;

int n, m, a, b;
int h[N], e[N], ne[N], idx; 
//h[i]是每个点对应的邻接链表 e[i]每条边所指向的点 ne[i]每条边的下一条边 idx表示第几条边
int d[N]; //点到1号的距离 

//添加边 
int add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs(int u){
    memset(d, -1, sizeof d);
    d[u] = 0;
    queue<int> q;
    q.push(u);

    while(!q.empty()){
        int t = q.front();
        q.pop();
        //遍历当前节点的所有相邻边
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i]; //遍历每条边所指向的那个点
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}
int main(){
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < m; i ++ ){
        cin >> a >> b;
        add(a, b);
    }
    printf("%d\n", bfs(1));
    return 0;    
}

拓扑排序

//拓扑 
bool topsort(){
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i++){
        if(d[i] == 0) q[++tt] = i;
    } 

    while(hh <= tt){
        int t = q[hh++];
        //遍历当前节点的所有相邻边
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i]; //遍历每条边所指向的那个点
            d[j] --;
            if(d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}

最短路径

单源点最短路径 Dijkstra

int n, m;
int g[N][N], d[N]; //g存点之间的距离，d存点i到点1的距离
bool vis[N];

int dijkstra(int u){
    memset(d, 0x3f, sizeof(d));
    d[u] = 0;
    //从1到n的最短路必然要算n-1次 
    for(int i = 0; i < n - 1; i++){
        //找到最近的一个点
        int t = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && (t == -1 || d[t] > d[j]))
                t = j;
        }

        //更新把这个点加入集合后的每个点到1的最短路径
        for(int j = 1; j <= n; j++){
            d[j] = min(d[j], d[t] + g[t][j]);
        }
        vis[t] = true;
    } 
    if (d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}

优化Dijkstra

• 当N为1e5或更大时，g[N][N]不能开这么大的空间，所以用邻接表来存图
• 用优先队列简化找最近的点的步骤

  //升序队列，小顶堆
  priority_queue <int,vector<int>,greater<int> > q;
  //降序队列，大顶堆
  priority_queue <int,vector<int>,less<int> >q;

代码如下

int n, m;
int h[N], w[N], e[N], ne[N], idx;
//h[i]是每个点对应的邻接链表 w[i]每个边的权重 e[i]每条边所指向的点 ne[i]每条边的下一条边 idx表示第几条边
int d[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra(int u){
    memset(d, 0x3f, sizeof(d));
    d[u] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; //小顶堆 
    heap.push({0, u}); 
    //priority_queue 是按照pair的第一个进行排序的，所以distance应该放在前面
    while(!heap.empty()){
        //找到最近的一个点
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        //更新把这个点加入集合后的最短路径
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] > d[ver] + w[i]){
                d[j] = d[ver] + w[i];
                heap.push({d[j], j});
            }
        } 
    } 
    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

bellman-ford 贝尔曼搜索算法 BF算法

处理有负权边的图（不能有回路） 时间复杂度O(nm)
可以不用邻接表，用最简单的结构体存，只要保证能遍历到所有边就行。

迭代k次的含义是经过不超过k条边的最短距离
所以有边数限制时可以用这个算法。

在迭代过程中可能发生串联，也就是当前迭代先更新的d值影响之后的d值，导致经过的边数不再是迭代的次数，所以每次要把前一次迭代的d值备份。
C 库函数 void *memcpy(void *str1, const void *str2, size_t n) 从存储区 str2 复制 n 个字节到存储区 str1。

int n, m, k;
int d[N], last[N];
bool st[N];

struct Edge{
    int a, b, w;
}edges[M];

int bf(int u){
    memset(d, 0x3f, sizeof(d));
    d[u] = 0;

    for(int i = 0; i < k; i++){
        memcpy(last, d, sizeof d);
        for (int j = 0; j < m; j++ ){
            auto e = edges[j];
            d[e.b] = min(d[e.b], last[e.a] + e.w);
        } 
    }
    if (d[n] > 0x3f3f3f3f / 2) puts("impossible"); //这里是因为存在负权边，可能会比最大值小导致更新，但实际还是无法到达 
    else printf("%d\n", d[n]);
}

spfa算法

是对bf算法的优化
贝尔曼是遍历每条边进行更新，但其实不是每条边都需要更新
所以用一个队列存d变小的点，只有d变小了，它的出边才有可能需要更新

和dijkstra算法很像，看一下这个底下的评论
https://www.acwing.com/video/283/

void spfa(int u){
    memset(d, 0x3f, sizeof(d));
    d[u] = 0;
    queue<int> q;
    q.push(u); 
    st[u] = true;
    while(!q.empty()){
        //找到最近的一个点
        int t = q.front();
        q.pop();
        st[t] = false; //每个点不一定只被更新一次，即st[j] == true的点可能被再次更新。

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                    //st数组去掉之后不影响算法正确性，但队列中会存储重复元素，效率会下降。
                }
            }
        } 
    } 
    if (d[n] == 0x3f3f3f3f) puts("impossible");
    //spfa只会更新所有能从起点走到的点，所以如果无解，那么起点就走不到终点，那么终点的距离就是0x3f3f3f3f。
    else printf("%d\n", d[n]);
}

也可用spfa判断是否有回路
cnt[i]记录到点i经过的边数，大于n则说明有回路

这题dist判断的逻辑已经完全变了是从负边出现时开始统计的 cnt 表示由第一次出现的负边起点做起点，该负边延伸的最大长度 当负环第一次出现的时候 cnt等于负环上的节点数，该节点数小于等于n， 之后会一直增加到无穷，此处只需要给出最小的判环结束的条件即可 无负环最极限的条件是存在cnt = n-1 即cnt>=n时一定存在负环。

初始时将所有点插入队列中可以按如下方式理解：
在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于视频中的做法了。那么视频中的做法可以找到负环，等价于这次spfa可以找到负环，等价于新图有负环，等价于原图有负环。得证。

bool spfa(){
    queue<int> q;
    //判断负环时不需要求出最短路的具体值，只需判断是否更新次数太多。如果存在负环，那么必然存在某些点的最短路长度是负无穷，那么必然会被更新无限次，所以不赋初值也可以。
    //无向连通图不需要建虚拟源点了，有向图除非强连通，否则不能保证从1号点能到达其他所有点， 应建立虚拟源点。将所有点插入队列是为了处理不连通的问题
    for (int i = 1; i <= n; i ++ ){
        st[i] = true;
        q.push(i);
    }
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[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;
}

y总说过最短路首先要考虑spfa算法，如果卡spfa算法，再考虑其他的。
第一：无向图是特殊的有向图，在有向图加边的时候加两次。
第二：重边在加入时选择最小值，存在负权时可以判断存在负权环。
这样的话可以统一无向图和有向图，还可以处理重边和负权。

Floyed算法

三重循环

int d[N][N]; //存图

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算法

朴素版的一般用于稠密图，堆优化版的不常用

int g[N][N];
int d[N]; //d是点到集合的距离 
bool st[N];

int prim(){
    memset(d, 0x3f, sizeof d);
    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 || d[t] > d[j]))
                t = j;
        }
        if(i && d[t] == INF) return INF;
        if(i) res += d[t];
        st[t] = true;
        //更新点到集合的距离 
        for(int j = 1; j <= n; j++) d[j] = min(d[j], g[t][j]);
    } 

    return res;
}

Kruskal算法

一般用于稀疏图

int p[N];

struct Edge{
    int a, b, w;
}edges[M];

bool cmp(Edge x, Edge y){
    return x.w < y.w;
}

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

int kruskal(){
    sort(edges, edges + m, cmp);
    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b){
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}

二分图

染色法

给定一个图判定是否是二分图
https://blog.csdn.net/qq_26822029/article/details/90382581
二分图当且仅当图中不含奇数环

遍历所有点，如果一个点为染色就用dfs把它相连的所有点都染上***r>同一条边的两个节点不同颜色

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

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;
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (!color[j]){
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }
    return true;
}
int main(){
    cin >> n >> m;    
    memset(h, -1, sizeof h);
    while (m -- ){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i]){
            if (!dfs(i, 1)){
                flag = false;
                break;
            }
        }

    if (flag) puts("Yes");
    else puts("No");


    return 0;
}

匈牙利算法

配对
最坏是O(nm)，实际上时间不会这么长

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int x){
    for (int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            st[j] = true;
            if (match[j] == 0 || find(match[j])){
                match[j] = x;
                return true;
            } 
        }
    }
    return false;
}
int main(){
    cin >> n1 >> n2 >> m;    
    memset(h, -1, sizeof h);
    while (m -- ){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    for(int i = 1; i <= n1; i++){
        memset(st, false, sizeof st);
        if (find(i)) res++ ;
    }
    printf("%d\n", res);
    return 0;
}