图论算法归纳（Dijkstra+SPFA+Floyd+Prim+Kruskal+二分图）

Dear 丶 2023-02-20 06:12 22阅读 0赞

# 一、Dijkstra邻接矩阵求最短路 #

### 题目链接：[https://www.acwing.com/problem/content/851/][https_www.acwing.com_problem_content_851] ###

### 代码： ###

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

# 二、Dijkstra邻接表求最短路 #

### 题目链接：[https://www.acwing.com/problem/content/852/][https_www.acwing.com_problem_content_852] ###

### 代码： ###

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

# 三、SPFA算法求最短路 #

### 题目链接：[https://www.acwing.com/problem/content/853/][https_www.acwing.com_problem_content_853] ###

### 代码： ###

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    
    using namespace std;
    const int N=100010;
    int h[N],e[N],ne[N],idx,w[N];
    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++;
    }
    
    
    int 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;
                    }
                }
            }
        }
        return dist[n];
    }
    
    int main(){
        cin>>n>>m;
        memset(h,-1,sizeof h);
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
    
        int t=spfa();
        if(t==0x3f3f3f3f)puts("impossible");
        else cout<<t<<endl;
        return 0;
    }

# 四、SPFA判负环 #

### 题目链接：[https://www.acwing.com/problem/content/854/][https_www.acwing.com_problem_content_854] ###

### 代码： ###

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    
    using namespace std;
    const int N=10010;
    int h[N],e[N],ne[N],idx,w[N];
    int dist[N];
    bool st[N];
     int n,m;
     int cnt[N];
    void add(int a,int b,int c){
        e[idx]=b;
      w[idx]=c;
      ne[idx]=h[a];
      h[a]=idx++;
    }
    
    
    int spfa(){
        memset(dist,0x3f,sizeof dist);
        dist[1]=0;
        
        queue<int>q;
        for(int i = 1;i<=n;i++)q.push(i),st[i] = true;
        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];
                    cnt[j] ++;
                    if(cnt[j]>=n)return 1;
                    if(!st[j]){
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
        return 0;
    }
    
    int main(){
        cin>>n>>m;
        memset(h,-1,sizeof h);
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
    
        }
        int t=spfa();
        if(t==1)cout<<"Yes";
        else cout<<"No";
        return 0;
    }

# 五、Floyd算法求多源最短路 #

### 题目链接：[https://www.acwing.com/problem/content/856/][https_www.acwing.com_problem_content_856] ###

### 代码： ###

#include <iostream>
    using namespace std;
    
    const int N = 210, M = 2e+10, INF = 1e9;
    
    int n, m, k, x, y, z;
    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]);
    }
    
    int main() {
        cin >> n >> m >> k;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(i == j) d[i][j] = 0;
                else d[i][j] = INF;
        while(m--) {
            cin >> x >> y >> z;
            d[x][y] = min(d[x][y], z);
            //注意保存最小的边
        }
        floyd();
        while(k--) {
            cin >> x >> y;
            if(d[x][y] > INF/2) puts("impossible");
            //由于有负权边存在所以约大过INF/2也很合理
            else cout << d[x][y] << endl;
        }
        return 0;
    }

# 六、Prim算法求最小生成树 #

### 题目链接：[https://www.acwing.com/problem/content/1142/][https_www.acwing.com_problem_content_1142] ###

### 代码： ###

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 105;
    int n;
    int w[N][N],dist[N];
    bool st[N];
    
    
    int prim(){
        int res = 0;
        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;
            }
            res += dist[t];
            st[t] = true;
            for(int j = 1;j<=n;j++)dist[j] = min(dist[j],w[t][j]);
        }
        return res;
    }
    
    int main(){
        cin>>n;
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                cin>>w[i][j];
        cout<<prim()<<endl;
        
        return 0;
    }

# 七、Kruskal算法求最小生成树 #

### 题目链接：[https://www.acwing.com/problem/content/861/][https_www.acwing.com_problem_content_861] ###

### 代码： ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 1e5+10, M = 2e5+10, INF = 0x3f3f3f3f;
    
    int n, m;
    int p[N];//祖宗节点
    
    struct Edge {
        int u, v, w;
    
        bool operator < (const Edge & T) const {
            return w < T.w;
        }
    
    }edges[M];
    
    int find(int x) {
        //并查集核心
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    
    int kruskal() {
        sort(edges, edges+m);
        for(int i = 1; i <= n; i++) p[i] = i; //初始化并查集
    
        int res = 0, cnt = 0;
        //res 最小生成树中的权重之和
        //cnt 当前加了多少条边
    
        for(int i = 0; i < m; i++) {
            auto t = edges[i];
            t.u = find(t.u), t.v = find(t.v);
            if(t.u != t.v) {
                p[t.u] = t.v;
                res += t.w;
                cnt++;
            }
        }
    
        if(cnt < n - 1) return INF;
        return res;
    }
    
    int main() {
        cin >> n >> m;
        int u, v, w;
    
        for(int i = 0; i < m; i++) {
            cin >> u >> v >> w;
            edges[i] = {u, v, w};
        }
    
        int x = kruskal();
        if(x > INF/2) puts("impossible");
        else cout << x << endl;
    }

# 七、染色法求二分图 #

### 题目链接：[https://www.acwing.com/problem/content/862/][https_www.acwing.com_problem_content_862] ###

### 代码： ###

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1e5+10,M = 2*N;
    int n,m;
    int h[N],e[M],ne[M],idx;
    int st[N];
    void add(int f ,int u){
        ne[idx] = h[f];
        e[idx] = u;
        h[f] = idx++;
    }
    
    
    
    bool bfs(int t){
        queue<pair<int,int>>q;
        q.push({t,1});
        st[t] = 1;
        while(q.size()){
            auto u = q.front();
            q.pop();
            int color = u.second;
            int r = u.first;
            for(int i = h[r];i!=-1;i = ne[i]){
                int j = e[i];
                if(st[j]){
                    if(st[j]==color)return false;
                }else{
                    q.push({j,3-color});
                    st[j] = 3-color;
                }
            }
        }
        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(!st[i]){
                if(!bfs(i)){
                    flag = false;
                    break;
                }
            }
        }
        
        if(flag)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        return 0;
    }

# 未完更新.... #

[https_www.acwing.com_problem_content_851]: https://www.acwing.com/problem/content/851/
[https_www.acwing.com_problem_content_852]: https://www.acwing.com/problem/content/852/
[https_www.acwing.com_problem_content_853]: https://www.acwing.com/problem/content/853/
[https_www.acwing.com_problem_content_854]: https://www.acwing.com/problem/content/854/
[https_www.acwing.com_problem_content_856]: https://www.acwing.com/problem/content/856/
[https_www.acwing.com_problem_content_1142]: https://www.acwing.com/problem/content/1142/
[https_www.acwing.com_problem_content_861]: https://www.acwing.com/problem/content/861/
[https_www.acwing.com_problem_content_862]: https://www.acwing.com/problem/content/862/