ACM圖論模闆（更新ing...）

1、最短路算法

Bellman-Ford算法

Dijkstra算法

SPFA算法

Floyd算法

被氣死的WA

2、最小生成樹算法

Prim算法

Kruskal算法

被氣死的WA

1、單源最短路（Bellman-Ford算法）

描述:

思想為連續對每條邊進行松弛操作，在每次松弛時把每條邊都更新一下，若在V-1次松弛後還能更新，則說明圖中有負環。可以求含負權圖及判定負環的最短路算法。

複雜度:

O(VE)

// Bellman-Ford算法
struct edge{ //從頂點from指向頂點to權值為cost的邊
	int from,to,cost;
}es[Max_E]; 
int V,E;
int d[Max_V];

void Bellman_Ford(int s){
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	//int k=0; //用于判定負環 
	while(true){
		bool flag=false;
		for(int i=0;i<E;i++){
			edge e=es[i];
			if(d[e.from]!=inf&&d[e.to]>d[e.from]+e.cost){
				d[e.to]=d[e.from]+e.cost;
				flag=true;
			}
		}
		if(!flag)break;
		//if(V==++k){printf("存在負環\n");return;}
	}
}

備注：

**有向圖中隻要含有一個權值和為負數的有向閉合路徑，稱圖含有負環；無向圖隻要含有一條邊權值為負，就稱含有負環。

2、單源最短路（Dijkstra算法）

描述:

思想為運用貪心政策（沒有負邊），不斷從已經确定最短距離的頂點集合（開始隻有起點s）向外找與該頂點集合距離最近的頂點，加入到該集合并更新與該頂點相連頂點的最短距離。

複雜度:

鄰接表+優先隊列 O(ElogV) // 有負邊的話

// Dijkstra算法
typedef pair<int,int> P;
struct edge{
    int to,cost; //first是最短距離,second是頂點的編号
    edge(int t,int c):to(t),cost(c){};
};
int V,E;
int d[Max_v];
vector<edge>G[Max_v];

void Dijkstra(int s){
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    priority_queue<P,vector<P>,greater<P> >que; //按照first從小到大順序取出
    que.push(P(0,s));
    while(!que.empty()){
        P p=que.top();que.pop();
        int v=p.second;
        if(p.first>d[v])continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

3、單源最短路（SPFA算法）

描述:

隊列優化後的Bellman-Ford算法，減少了備援的松弛操作。優化：在Bellman-Ford算法中，要是某個點的最短路徑估計值更新了，那麼我們必須對所有邊指向的終點再做一次松弛操作；在SPFA算法中，某個點的最短路徑估計值更新，隻有以該點為起點的邊指向的終點需要再做一次松弛操作。

複雜度:

O(kE) 不穩定，最壞＜O(VE)

// SPFA算法
struct edge{
    int to,cost;
    edge(int t,int c):to(t),cost(c){};
};
int V,E;
bool vis[Max_v]; //在隊列标志
int d[Max_v];   
int cnt[Max_v]; //入隊次數
vector<edge>G[Max_v];

bool SPFA(int s){
    memset(vis,0,sizeof(vis));
    memset(d,0x3f,sizeof(d));
    memset(cnt,0,sizeof(cnt));
    vis[s]=1;d[s]=0;cnt[s]=1;
    queue<int>que;
    que.push(s);
    while(!que.empty()){
        int u=que.front();que.pop();
        vis[u]=0;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].to;
            if(d[v]>d[u]+G[u][i].cost){
                d[v]=d[u]+G[u][i].cost;
                if(!vis[v]){
                    vis[v]=1;que.push(v);
                    if(++cnt[v]>V)return false;  //判定負環
                }
            }
        }
    }
    return true;
}

4、多源最短路（Floyd算法）

描述:

運用動态規劃思想的一個經典多源最短路算法。可以處理負權圖的最短路和傳遞閉包，而判斷圖中是否有負圈，隻需要檢查是否存在d[i][i]是負數的頂點i就可以了。遞推方程：d[i][j]=min(d[i][j],d[i][k]+d[k][j])

複雜度:

O(v3)

// Floyd算法
int n,m;
int d[Max_n][Max_n]；
int path[Max_n][Max_n]; //記錄路徑

void init(){ //初始化
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++){
            d[i][j]=inf;
            path[i][j]=j; //path[i][j]=x表示i到j的路徑上(除i外)的第一個點是x
            if(i==j)d[i][j]=0;
    }
}

void getpath(int st,int ed){ //列印路徑
    while(st!=ed) {
        printf("%d->",st);
        st=path[st][ed];
    }
    printf("%d\n",ed);
}

void Floyd(){  //Floyd算法
     for(int k=1;k<=n;k++) 
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) {
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                    path[i][j]=path[i][k];
                }
            }
}

5、被氣死的WA

數組開小越界。
多次循環沒有重新初始化變量，數組及容器。

for(int i=0;i<=N;i++)G[i].clear(); //Vector容器清空
while(!que.empty())que.pop(); //Queue容器清空

6、Prim算法 -----讓一棵小樹長大

描述：

又稱"加點法"，運用貪心思想，從某個頂點出發，不斷向生成樹頂點集合X添加距離X最近的頂點。添加頂點數 < V時，圖不連通。

複雜度：

O(v2)

// Prim算法
// 已求得生成樹的頂點集合記為X
int V,E;
int dist[Max_v]; //從集合X出發的邊到每個頂點的最小權值
bool vis[Max_v]; //頂點i是否在集合X中
int cost[Max_v][Max_v]; //cost[u][v]表示邊e=(u,v)的權值（不存在設為INF）

int Prim()
{
	int ans=0,sum=0; //收入頂點數和最小權重和
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    dist[0]=0;
    while(true)
    {
        int v=-1;
        for(int i=0;i<V;i++) //v=未收錄頂點集合X中dist的最小值
            if(!vis[i]&&dist[i]!=inf&&(v==-1||dist[i]<dist[v]))v=i;
        //dist[i]!=inf是必要的，圖可能不連通
        if(v==-1)break;
        vis[v]=1;  //将頂點v加入X
        ans++;sum+=dist[v];
        for(int i=1;i<=V;i++) //更新v的每個鄰接點dist的值
            if(!vis[i]&&dist[i]>cost[v][i])
                dist[i]=cost[v][i];
    }
    if(ans<V)return -1; //圖不連通
    return sum;
}

7、Kruskal算法 -----将森林合并成樹

描述：

又稱"加邊法"，運用貪心思想，按邊的權值從小到大排序，依次從邊中選擇一條不會産生環路的具有最小權值的邊加入生成樹的邊集合中。添加邊數 < V-1時，圖不連通。

複雜度：

O(ElogE)

// Kruskal算法
struct edge{
    int from,to,cost;
    bool operator<(const edge& e)const{
        return cost<e.cost;
    }
}e[Max_e];
int V,E;
int par[Max_v];  //根節點

int Find(int x){ //查詢樹的根（路徑壓縮）
    if(par[x]==x)return x;
    return par[x]=Find(par[x]);
}

int Kruskal(){
	int ans=0,sum=0; //收入邊數和最小權重和
	for(int i=0;i<V;i++)par[i]=i; //初始化
    sort(e,e+E);
    for(int i=0;i<E;i++){
        int x=Find(e[i].from);
        int y=Find(e[i].to);
        if(x!=y){
            ans++;sum+=e[i].cost;
            par[x]=y;
        }
        if(ans==V-1)break;
    }
    if(ans<V-1)return -1;
    return sum;
}

8、被氣死的WA

頂點集、邊集數組開小越界。
頂點下标是0…n-1，處理資料時:

Prim算法讀入資料： cost[a-1][b-1]=c;cost[b-1][a-1]=c;
Kruskal算法讀入資料： e[i].from=a-1;e[i].to=b-1;e[i].cost=c;
如果不注意，Kruskal算法初始化par數組 for(int i=0;i<V;i++)par[i]=i; 時，多組資料會WA！

66666666666666666666666666