图论算法

最短路

能用dijkstra的就别用spfa

Dijkstra 算法

题解

朴素用邻接矩阵存储 // 稠密图 点少线多

1.循环 n 次

2.找到一个 t 用来代表当前所有点到目前点的最短距离

3.用 t 来更新到这个点的最短距离

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 550;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
void dijkstra()
{
    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 ;
        for(int j = 1 ;j <= n ; j ++)
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        st[t] = true;
    }
}
int main(void)
{
    memset(g,0x3f,sizeof g);
    cin >> n >> m ;
    while(m --)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }
    dijkstra();
    if(dist[n] == 0x3f3f3f3f) cout << -1 << endl;
    else cout << dist[n] << endl;
    return 0;
}

优化版的dijkstr 算法

稀疏图 用邻接矩阵来存储

用堆进行优化 每次取最短值的时候 取堆顶元素

相当于是省略了朴素版dijkstra 的找到距离当前点最短距离这一步；；

代替上边的第一二步

然后更新所有堆的距离

用一个 pair 数组来存储到起点的距离和当前点的编号

用邻接表遍历所有到达的点 并对其进行判断 如果小于 并且该值并未被使用过 即 st 为 false 可以进行更新

就把该值和距离推进 heap 数组中

这里 与 spfa 算法进行个区分

• dijsktra 算法一般在取得编号后就进行判断 是否进行 continue 环节

• spfa 算法 则在 for 循环和 if 循环 之后判断该值是否使用过

• dijkstra保证了每个点只会被使用一次，而spfa则一个点可能被多次使用

​ SPFA可以处理负权边，但是不能处理有负权回路的图；而Dijkstra不能处理带有负权边和负权回路的图，因为Dijkstra算法在计算最短路径时，不会因为负边的出现而更新已经计算过(收录过)的顶点的路径长度； ​ 总结一下：Bellman-ford可以处理任意带负权边和负权环的图，SPFA可以处理带负权边的图，Dijkstra只能处理带正权边的图；当然，从时间复杂度的效率来讲，是反过来的，hh

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue <PII,vector<PII>,greater<PII> >heap;
    dist[1] = 0;
    heap.push({0,1});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        int s = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
int main(void)
{
    cin >> n >> m ;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c ;
        add(a,b,c);
    }
    dijkstra();
    if(dist[n] == 0x3f3f3f3f) cout << -1 << endl;
    else cout << dist[n] << endl;
    return 0;
}

Bellman_ford 算法

用于处理存在负权边的环节 并且存在 判断至少在几条边实现

利用结构体来存储

第一层 for 循环代表最短几条边

接下来对所有的边进行遍历，用 struct 来对每条边取最短的路径

为了避免出 行比对

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 550,M = 10010;

struct Edge
{
    int a,b,c;
}edges[M];
int n,m,k;
int dist[N];
int last[N];
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for(int i = 0 ; i < k ;i ++)
    {
        memcpy(last,dist,sizeof dist);
        for(int j = 0 ; j< m ; j ++)
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}
int main(void)
{
    cin >> n >> m >> k;
    for(int i = 0;i<m;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        edges[i] = {x,y,z};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    return 0;
}

Spfa 算法

题解

是基于bellman_ford 算法的一种优化

因为bellman 算法是对所有的边都进行了取最短距离

而 Spfa 算法则是利用 队列 来存储每次取得到的 最短距离

并用这个 距离 来更新别的距离

bellman 算法 保留了所有到这个点的前一个点的最短距离，但这样的话 无疑会有一些边是未曾用过的

而 spfa 算法就是只记录了会被更新的节点 并 用这个点来更新别的点

用 for 循环 来遍历所有与当前点有接触的所有点

然后用队列将该点存下来 在每次遍历队列中的点 以此为延续不断连接所有可能会遇到的点

即该点用到了 就会 继续更新它后面的点

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

关于为什么

每次只会讲修改过的边加入进去

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 +10;
int h[N],w[N],e[N],ne[N],idx;
int dist[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++;
}
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int>q;
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = 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]) // 这里只会存放已经被更新过的边 ，， 如果被更新了 且不再队列中才会被继续添加
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}
int main(void)
{
    int n,m;
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m --)
    {
        int a,b,c;
        cin >> a>> b >> c;
        add(a,b,c);
    }
    spfa();
    if(dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << dist[n] << endl;
    return 0;
}

Foyld 算法

用 邻接表来存储 但是 为什么这样 初始化

因为 g 数组中存储的就是点到点的距离，所以当 i == j 的时候 距离为 0 ，所以初始化为 0；

k i j

g[i][j] = min(g[i][j] , g[i][k] + g[k][j]);

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210,INF = 1e9;
int g[N][N];
int n,m,q;
void Floyd()
{
    for(int k = 1 ;k <= n ;k ++)
        for(int i = 1 ;i <= n ; i ++)
            for(int j = 1; j <= n ;j ++)
            g[i][j] = min(g[i][j] , g[i][k] + g[k][j]);
}
int main(void)
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n ; i ++)
        for(int j = 1; j <= n ; j ++)
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
    while(m --)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b] , c);
    }
    Floyd();
    while(q -- )
    {
        int x,y;
        cin >> x >> y;
        if(g[x][y] > INF / 2) cout <<"impossible" << endl;
        else cout << g[x][y] << endl;
    }
    return 0;
}

最小生成树

Prim 算法

处理稠密图

主要是利用扩大集合的思想来做的 ，不断找到距离当前集合最近的点，并把他加入

与 dijkstra 算法类似

枚举 n 次

找到距离集合最近的点 t

用 t 来更新其他点到集合的距离

利用 res 记录所有不是第一条边的时候的权重和

当出现不是第一条边并且最近距离也是趋近于正无穷时，直接结束

返回 false

最后使用 g[t] [j] 时，关于为什么使用它的原因是，需要找到当前点距离集合最近的点，又因为 dist 本身保存的就是当前点到第一个点即集合的距离，再加上前面每次循环找到的都是距离上一个点的最近距离，所以说当 dist 不是最近的距离时 最近的距离就是 g ，，因为上面每次的都是取到了距离的最小值

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 550,INF = 0x3f3f3f3f;
const int M = 1e5+10;
int g[N][N];
bool st[N];
int dist[N];
int res;
int n,m;
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;
        }
        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]); // 记录到集合的距离，而不是跟最短路一样到起点的距离
        st[t] = true;
    }
    return res;
}
int main(void)
{
    cin >> n >> m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        cin >> a>> b >> c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    int res = Prim();
    if(res == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << res << endl;
    return 0;
}

Kruskal 算法

处理稀疏图

通过结构体**按照权重来进行排序 ** 排序保证是最小生成树

利用并查集和结构体来存储边和权重

每次如果两点之间没有联系则利用并查集 进行 两两 相加 记录权重和 count

如果 cnt < n-1 则不存在最小生成树，否则输出权值

#include < iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 +10 , M = 200010;
const int INF = 0x3f3f3f3f;
int p[N];
int n,m;
struct Edges
{
    int a,b,w;
    bool operator < (const Edges & W)const
    {
        return w < W.w;
    }
}edges[M];
int find(int x)
{
    if(x != p[x]) p[x] =  find(p[x]);
    else return p[x];
}
int kruskal()
{
    int cnt = 0 , res = 0;
    sort(edges,edges + m);
    for(int i = 1; i <= n ; i ++) p[i] = i;
    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;
}
int main(void)
{
    cin >> n >> m;
    for(int i = 0 ;i < m ; i ++)
    {
        int a,b,c;
         cin >> a >> b >> c;
         edges[i] = {a,b,c};
    }
    int t = kruskal();
    if(t == INF) cout <<"impossible" << endl;
    else cout << t <<endl;
    return 0;
}

二分图

**匈牙利算法 **

判断二分图的最大匹配

根本原理 是遍历每一个点

然后 去找到该点指向的点，再跟着判断 该点是否已经被别的点所匹配或是 被别的点匹配的那个点 是否可以匹配别的点 如果 可以 就会替代上一个匹配的点

就是一个递归的过程

主要就是 match 数组 和 st 数组

for 循环里面每次都会初始化所有的为 false 原因是 让每个人都会进行完美的递归 保证了 最佳答案的出现（把所有妹子清空）即初始化

#include <iostream>
#include <cstring>
using namespace std;
const int N = 550,M = 100010;
int n1,n2,m;
bool st[N];
int h[N],e[M],ne[M];
int idx;
int match[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(void)
{
    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 ++;
    }
    cout << res << endl;
    return 0;
}

染色法判断

是否为二分图

利用染色 1，2 来给点做上标记，并利用 dfs 的过程来进行深度的判断

如果 bool 类型的 dfs 返回 false 的话，代表染色失败，即存在冲突，不满足二分图的性质

如果当前点没有染色，就利用 dfs 把他染成 3 - x 色，如果有颜色 并且相等的话

直接返回 false

#include <iostream>
#include <algorithm>
#include <cstring> 
using namespace std;
const int N = 1e5 + 10,M = 200010;
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a]; 
    h[a] = idx ++;
}
bool dfs(int u,int x)
{
    color[u] = x;
    for(int i = h[u] ; i != -1 ; i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j,3-x)) return false;
        }
        else if(color[j] == x) return false;
    }
    return true;
}
int main(void)
{
    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) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Topsort Dfs Bfs

topsort 拓扑排序

利用入度来进行判断 找到所有入度为 0 的点把其加入队列中

最好利用手动模拟队列 这样会对结果的输出起到简化作用

在循环中，如果存在入度为 1 的情况出现时，也会把该值加入到队列中，因为他同样可以满足拓扑的条件

Dfs 深度优先遍历

dfs 主要是一个利用递归的过程

深度优先遍历

可以处理排列数字等问题

Bfs 宽度优先遍历

宽度优先遍历

bfs 主要利用队列来进行存储，当队列中的元素不为空的时候，会一直继续下去，每次推入满足条件的点，最后找到最短的路径或者是迷宫的出路