圖論在演算法中具有舉足輕重的地位，只有學好圖才能游刃有余，本文章將介紹圖論中一些基礎演算法，可以說總結的十分全面，文章結尾也會分析各演算法的差異,清晰易懂，并附上代碼模板.

圖論（最短路、生成樹）

一、拓撲排序
二、Djikstra演算法
- - 1. 樸素演算法
  - 2. 優先佇列優化
三、Bellan-ford演算法
四、Floyd演算法
五、Spfa演算法
- - 1.求最短路
  - 2.判斷負環
六、Prim演算法求最小生成樹
七、Kruskal演算法求最小生成樹
八、一點問題：
- - 1、prim 和 dijkstra 的區別與聯系：
  - 2、spfa 和 dijkstra 的區別與聯系：
  - 3、求負環的常用方法：
總結:

一、拓撲排序

什么是拓撲序？
若一個由圖中所有點構成的序列 A 滿足：對于圖中的每條邊 (x,y)，x 在 A 中都出現在 y 之前，則稱 A 是該圖的一個拓撲序列，

演算法思想：放在前面的點的入度一定更小（起點為入度為0），每次將入度為0的點放入佇列中去更新其相連的點，使其相連的點入度-1，

條件：有向無環圖. 注：不能存在自環

bool st[N];
int top[N];
int d[N];

bool topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++)   if(!d[i])   q.push(i);
    
    int k = 0;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[t] = 1;
        top[k++] = t;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j = e[i];
            
            if(!st[j]){
                d[j]--;
                
                if(!d[j])   q.push(j);
            }
        }
    }

    return k==n;
}

二、Djikstra演算法

演算法思想：Dijkastra,每次找出不再集合中的距離源點距離最小的點去更新其他點. dist陣列保存到源點的距離，

適用于有向圖可存在重邊和自環但不能存在負權

1. 樸素演算法

// 樸素
int Dijkastra1(){
    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;
            }
        }
        
        st[t] = 1;
        
        for(int j=h[t];j!=-1;j=ne[j]){
            int k = e[j];
            
            dist[k] = min(dist[k],dist[t]+w[j]);
        }
           
    }
    
    if(dist[n]==0x3f3f3f3f)   return -1;
    else    return dist[n];
}

2. 優先佇列優化

typedef pair<int,int> PII;
int Dijkastra2(){
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII> > p;
    dist[1] = 0;
    p.push({0,1});
    
    while(!p.empty()){
        PII t = p.top();
        p.pop();
        
        if(st[t.second])    continue;
        st[t.second] = 1;
        
        for(int i=h[t.second];i!=-1;i=ne[i]){
            int j = e[i];
            
            if(dist[j]>dist[t.second]+w[i]){
                dist[j] = dist[t.second]+w[i];
                
                p.push({dist[j],j});
            }
        }
    }
    
    if(dist[n]==0x3f3f3f3f)   return -1;
    else    return dist[n];
}

三、Bellan-ford演算法

Bellan-ford有邊數限制：雖演算法效率不高，卻有一定的實際意義，

想象這樣一個背景：你在一號城市，想去n號城市去旅游，但是飛機沒有1號城市從直達n號城市的（只能換乘飛機到達），你想要花費最少到達目的地；但是吧，每換乘一次，你的心情就會變差一回，也就是說最多換乘k次，問最優解是什么？（來自yxc大佬）

Bellman-ford演算法：
可以用于判斷是否存在負權回路
步驟：
       for  k次回圈(最多經過k條邊)
         for  所有邊a,b,w(權重)
           更新：dist[b] = min(dist[b],dist[a]+w)
負權環，指的是一個圖中存在一個環，里面包含的邊的邊權總和<0

int Bellman_ford(){
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    
    for(int i=0;i<k;i++){
        memcpy(backup,dist,sizeof dist);
        
        for(int i=0;i<m;i++){
            int a = edges[i].a,b = edges[i].b,c = edges[i].w;
            
            dist[b] = min(dist[b],backup[a]+c);
        }
    }
    
    if(dist[n] > 0x3f3f3f3f/2) return -1;
    else return dist[n];
}

注：圖中可能存在重邊和自環，邊權可能為負數

四、Floyd演算法

有向圖，圖中可能存在重邊和自環，邊權可能為負數
Floyd演算法用于求解兩點之間的最短路問題.

int d[N][N];

void floyd(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int q=1;q<=n;q++){
                d[j][q] = min(d[j][q],d[j][i]+d[i][q]);
            }
        }
    }
}

五、Spfa演算法

spfa演算法：可以理解為一圈一圈計算

1.求最短路

int dist[N];
bool st[N];
int spfa(){
    queue<pii> q; 
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    
    q.push({0,1});
    st[1] = 1;
    while(!q.empty()){
        pii t = q.front();
        q.pop();
        st[t.second] = 0;
        
        for(int i=h[t.second];i!=-1;i=ne[i]){
            int j = e[i];
            
            if(dist[j]>dist[t.second]+w[i]){                // 此處與迪杰斯特拉演算法不同.         由于dist[] 總是儲存的是當前最小值
                dist[j] = dist[t.second] + w[i];
                
                if(!st[j]){
                    st[j] = 1;
                    q.push({dist[j],j});
                }
            }
        }
    }
    
    if(dist[n]==0x3f3f3f3f)  return -1;
    else return dist[n];
}

2.判斷負環

bool spfa() {
    memset(dist, 0x3f, sizeof dist);
    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] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}

六、Prim演算法求最小生成樹

無向圖；圖中可能存在重邊和自環；邊權可能為負數，

演算法思想：更新到集合的最短距離dist

int state[N],pre[N],st[N],dist[N];
int res;

void prim(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    
    for(int i=1;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] = 1;
        res += dist[t];
        
        for(int j=1;j<=n;j++){
            if(!st[j] && dist[j]>g[j][t]){
                dist[j] = g[j][t];
            }
        }
    }
}

七、Kruskal演算法求最小生成樹

演算法思想：借助并查集優化演算法

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;
const int M = 2*N;         // 邊的數量

struct edge{
    int a;
    int b;
    int w;
    
    bool operator <(const edge &x) const
    {
        return w<x.w;
    }
}egs[M];

int n,m;
int pre[N];

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

int kreskal(){
    int res = 0,cnt = 0;
    
    for(int i=0;i<m;i++){
        int a = egs[i].a, b = egs[i].b, w = egs[i].w;
        
        if(find(a)!=find(b)){
            pre[find(a)] = pre[find(b)];
            cnt ++;
            res += w;
        }
    }
    
    if(cnt==n-1)    return res;
    else    return 0x3f3f3f3f;
}

int main()
{
    scanf("%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=n;i++)   pre[i] = i;
    
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        
        egs[i] = {a,b,c};
    }
    
    sort(egs,egs+m);
    int t = kreskal();
    
    if(t==0x3f3f3f3f)   cout << "impossible" << endl;
    else    cout << t << endl;
    
    return 0;
}

八、一點問題：

1、prim 和 dijkstra 的區別與聯系：

prim 為更新到集合的最短距離dist; 而dijkastra 為更新到源點的最短距離dist，即更新方式不同
.兩者均可以使用優先佇列優化.不過在優化時，prim最好采用kruskal優化.

2、spfa 和 dijkstra 的區別與聯系：

st陣列的作用不同，可以將一個點反復設為0和1
SPFA演算法中使用的是佇列，目的只是記錄一下當前發生過更新的點；而dijkstra演算法使用的是優先佇列，目的是取出不在集合中的距離源點最近的點

3、求負環的常用方法：

求負環的常用方法，基于SPFA，一般都用方法 2：
方法 1：統計每個點入隊的次數，如果某個點入隊n次，則說明存在負環
方法 2：統計當前每個點的最短路中所包含的邊數，如果某點的最短路所包含的邊數大于等于n，則也說明存在負環

總結:

學會不是目的，重要的是能夠熟悉演算法思想，理解到代碼中的細節，這樣才能在做題程序中游刃有余，

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/305248.html

標籤：其他

上一篇：練習（三）

下一篇：檔案操作詳解（建議收藏）

圖論最短路及生成樹(Prim,Djikstra,Spfa,Bellan-ford,kruskal,topsort)

圖論（最短路、生成樹）

一、拓撲排序

二、Djikstra演算法

1. 樸素演算法

2. 優先佇列優化

三、Bellan-ford演算法

四、Floyd演算法

五、Spfa演算法

1.求最短路

2.判斷負環

六、Prim演算法求最小生成樹

七、Kruskal演算法求最小生成樹

八、一點問題：

1、prim 和 dijkstra 的區別與聯系：

2、spfa 和 dijkstra 的區別與聯系：

3、求負環的常用方法：

總結: