圖論（最短路，最小生成樹，并查集）

本文目錄：

tarjan算法（判斷環）

最小生成樹（Kruskal算法）

最小生成樹（Prim算法）

優先隊列實作dijkstra（最短路）

并查集（求環）

floyd(弗洛伊德) （最短路）

判斷環：

tarjan算法

講解：http://www.sohu.com/a/245954819_100201031

tarjan算法，一個關于圖的聯通性的神奇算法。基于DFS（迪法師）算法，深度優先搜尋一張有向圖。！注意！是有向圖。根據樹，堆棧，打标記等種種神（che）奇（dan）方法來完成剖析一個圖的工作。而圖的聯通性，就是任督二脈通不通。。的問題。

了解tarjan算法之前你需要知道：

強連通，強連通圖，強連通分量，解答樹。

強連通(strongly connected)：在一個有向圖G裡，設兩個點 a b 發現，由a有一條路可以走到b，由b又有一條路可以走到a，我們就叫這兩個頂點（a，b）強連通。
強連通圖：如果在一個有向圖G中，每兩個點都強連通，我們就叫這個圖，強連通圖。
強連通分量strongly connected components)：在一個有向圖G中，有一個子圖，這個子圖每2個點都滿足強連通，我們就叫這個子圖叫做強連通分量［分量：把一個向量分解成幾個方向的向量的和，那些方向上的向量就叫做該向量（未分解前的向量）的分量］

tarjan算法，之是以用DFS就是因為它将每一個強連通分量作為搜尋樹上的一個子樹。而這個圖，就是一個完整的搜尋樹。

為了使這顆搜尋樹在遇到強連通分量的節點的時候能順利進行。每個點都有兩個參數。

1，DFN［］作為這個點搜尋的次序編号（時間戳），簡單來說就是第幾個被搜尋到的。％每個點的時間戳都不一樣％。

2，LOW［］作為每個點在這顆樹中的，最小的子樹的根，每次保證最小，like它的父親結點的時間戳這種感覺。如果它自己的LOW［］最小，那這個點就應該從新配置設定，變成這個強連通分量子樹的根節點。

ps：每次找到一個新點，這個點LOW［］＝DFN［］。

而為了存儲整個強連通分量，這裡挑選的容器是，堆棧。每次一個新節點出現，就進站，如果這個點有出度就繼續往下找。直到找到底，每次傳回上來都看一看子節點與這個節點的LOW值，誰小就取誰，保證最小的子樹根。如果找到DFN［］＝＝LOW［］就說明這個節點是這個強連通分量的根節點（畢竟這個LOW［］值是這個強連通分量裡最小的。）最後找到強連通分量的節點後，就将這個棧裡，比此節點後進來的節點全部出棧，它們就組成一個全新的強連通分量。

先來一段僞代碼壓壓驚：

tarjan(u){

　　DFN[u]=Low[u]=++Index // 為節點u設定次序編号和Low初值

　　Stack.push(u)   // 将節點u壓入棧中

　　for each (u, v) in E // 枚舉每一條邊

　　　　if (v is not visted) // 如果節點v未被通路過

　　　　　　　　tarjan(v) // 繼續向下找

　　　　　　　　Low[u] = min(Low[u], Low[v])

　　　　else if (v in S) // 如果節點u還在棧内

　　　　　　　　Low[u] = min(Low[u], DFN[v])

　　if (DFN[u] == Low[u]) // 如果節點u是強連通分量的根

　　repeat v = S.pop  // 将v退棧，為該強連通分量中一個頂點

　　print v

　　until (u== v)

}

鄰接表的建立建議看看這篇部落格：

https://blog.csdn.net/Mr_S_Edward/article/details/82942847

代碼實作：

#include<cstdio>
 #include<algorithm>
 #include<string.h>
 using namespace std;
 struct node {
     int v,next;
 }edge[1001];
  int DFN[1001],LOW[1001];
 int stack[1001],heads[1001],visit[1001],cnt,tot,index;
void add(int x,int y)
{
     edge[++cnt].next=heads[x];
     edge[cnt].v = y;
     heads[x]=cnt;
    return ;
 }
 void tarjan(int x)//代表第幾個點在處理。遞歸的是點。
 {
     DFN[x]=LOW[x]=++tot;// 新進點的初始化。
     stack[++index]=x;//進站
     visit[x]=1;//表示在棧裡
    for(int i=heads[x];i!=-1;i=edge[i].next)
     {
         if(!DFN[edge[i].v]) {//如果沒通路過
            tarjan(edge[i].v);//往下進行延伸，開始遞歸
             LOW[x]=min(LOW[x],LOW[edge[i].v]);//遞歸出來，比較誰是誰的兒子／父親，就是樹的對應關系，涉及到強連通分量子樹最小根的事情。
        }
        else if(visit[edge[i].v ]){  //如果通路過，并且還在棧裡。
             LOW[x]=min(LOW[x],DFN[edge[i].v]);//比較誰是誰的兒子／父親。就是連結對應關系
         }
     }
     if(LOW[x]==DFN[x]) //發現是整個強連通分量子樹裡的最小根。
    {
         do{
            printf("%d ",stack[index]);
             visit[stack[index]]=0;
             index--;
         }while(x!=stack[index+1]);//出棧，并且輸出。
         printf("\n");
     }
     return ;
 }
 int main()
 {
     memset(heads,-1,sizeof(heads));
     int n,m;
     scanf("%d%d",&n,&m);
    int x,y;
     for(int i=1;i<=m;i++)
     {
         scanf("%d%d",&x,&y);
        add(x,y);
     }
    for(int i=1;i<=n;i++)
         if(!DFN[i])  tarjan(i);//當這個點沒有通路過，就從此點開始。防止圖沒走完
    return 0;
 }

洛谷：https://www.luogu.org/problemnew/show/P2921

#include <bits/stdc++.h>
using namespace std;

const int MAXN=100005;
int nexts[MAXN],ans[MAXN],head[MAXN],len[MAXN],color[MAXN];;
int cnt=0,col=0;
struct node{
    int to,next;
}edge[MAXN*2];

void add(int a,int b){
    cnt++;
    edge[cnt].to=b;
    edge[cnt].next=head[a];
    head[a]=cnt;
}

int tot=0,indexs=0,DFN[MAXN],LOW[MAXN],vis[MAXN]={0},stacks[MAXN];

void tarjan(int x){
    DFN[x]=LOW[x]=++tot;
    stacks[++indexs]=x;
    vis[x]=1;
    for(int i=head[x];i!=0;i=edge[i].next){
        if(DFN[edge[i].to]==0){
            tarjan(edge[i].to);
            LOW[x]=min(LOW[x],LOW[edge[i].to]);
        }
        else if(vis[edge[i].to]==1){
            LOW[x]=min(LOW[x],DFN[edge[i].to]);
        }
    }
    if(LOW[x]==DFN[x]){
        col++;
        do{
            color[stacks[indexs]]=col;
            vis[stacks[indexs]]=0;
            indexs--;
        }while(x!=stacks[indexs+1]);
    }
    return;
}

void searchs(int root,int x,int step){
    if(ans[x]!=0){
        ans[root]=ans[x]+step;
        return;
    }
    else searchs(root,nexts[x],step+1);
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&nexts[i]);
        add(i,nexts[i]);
        if(nexts[i]==i) ans[i]=1;
    }
    for(int i=0;i<=n;i++)
        if(DFN[i]==0) tarjan(i);
    for(int i=1;i<=n;i++)
         len[color[i]]++;
    for(int i=1;i<=n;i++)
         if(len[color[i]]!=1) ans[i]=len[color[i]];
    for(int i=1;i<=n;i++)
        if(ans[i]==0) searchs(i,nexts[i],1);
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
}

最小生成樹

生成樹：一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但隻有足以構成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環。
最小生成樹：在連通網的所有生成樹中，所有邊的代價和最小的生成樹，稱為最小生成樹。

圖論（最短路，最小生成樹，并查集）

Kruskal算法（相對最好）

此算法可以稱為“加邊法”，初始最小生成樹邊數為0，每疊代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合裡。

把圖中的所有邊按代價從小到大排序；
把圖中的n個頂點看成獨立的n棵樹組成的森林；
按權值從小到大選擇邊，所選的邊連接配接的兩個頂點ui,vi,應屬于兩顆不同的樹，則成為最小生成樹的一條邊，并将這兩顆樹合并作為一顆樹。
重複(3),直到所有頂點都在一顆樹内或者有n-1條邊為止。

圖論（最短路，最小生成樹，并查集）

Kruskal 模闆

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,sum;
struct node{
 int start,ends,power;//start為起始點，end為終止點，power為權值
}edge[5050];
int pre[5050];

bool cmp(const node&a,const node&b){
  return a.power<b.power;//按照權值排序
}

int Find(int x){  //并查集找祖先
 if(x!=pre[x]){
    pre[x]=Find(pre[x]);
 }
 return pre[x];
}

void Merge(int x,int y,int n){//并查集合并函數，n是用來記錄最短路中應該加入哪個點
  int fx=Find(x);
  int fy=Find(y);
  if(fx!=fy){
    pre[fx]=fy;
    sum+=edge[n].power;
  }
}
int main(){
  while(~scanf("%d %d",&n,&m),n+m){//n是點數,m是邊數
    sum=0;
    int start,ends,power;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&start,&ends,&power);
        edge[i].start=start,edge[i].ends=ends,edge[i].power=power;
    }
    for(int i=1;i<=m;i++){
        pre[i]=i;
    }//并查集初始化
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;i++){
        Merge(edge[i].start,edge[i].ends,i);
    }
    printf("%d\n",sum);
  }
  return 0;
}

Prim

圖來示範Prim算法的過程。

圖論（最短路，最小生成樹，并查集）

我們選擇一個起點，然後在與起點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。假設起點是0節點，與0節點相連且未被選的節點是{1,2,3}，分别對應的權值是{6,1,5}，可見目前最小的權值1，權值最小的節點就是2節點，是以将2節點和0-2的邊添加入生成樹，如圖b所示。

圖論（最短路，最小生成樹，并查集）

接着我們在與已選節點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。目前已選節點是0,2節點，與已選節點相連且未被選的節點有{1,3,4,5}，分别對應的權值是{（6,5），（5,5），6,4,}，可見目前最小的權值4，權值最小的節點就是5節點，是以将5節點和2-5的邊添加入生成樹，如圖c所示。（其實在程式設計時，我們隻需記錄與更新目前較小的那個權值，如與{1,3,4,5}對應的權值我們隻需記錄{5,5,6,4}，當然我們也需利用了另一個數組來加以差別目前權值對應的連接配接點，如目前權值{5,5,6,4}所對應的連接配接點就是{2,0,2,2}）

圖論（最短路，最小生成樹，并查集）

接着我們繼續在與已選節點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。目前已選節點是0,2,5節點，與已選節點相連且未被選的節點有{1,3,4}，分别對應的權值是{（6,5），（2,5,5），（6,6）,}（其實目前我們可隻記錄{5,2,6}，同時記錄其對應的連接配接點分别是{2,5,2}），可見目前最小的權值2，權值最小的節點就是3節點，是以将3節點和5-3的邊添加入生成樹，如圖d所示。

圖論（最短路，最小生成樹，并查集）

接着我們依照上一次的步驟繼續在與已選節點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。如圖e，f所示。最終圖f就是我們通過Prim算法得到的最小生成樹了。

圖論（最短路，最小生成樹，并查集）

算法概念

現在我們給出Prim的嚴謹概念：Prim算法是一種構造性算法。假設G=（V,E）是一個具有n個頂點的帶權連通無向圖，T=（U，TE）是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則由G構造從起始頂點v出發的最小生成樹T的步驟如下：

（1）初始化U={v},以v到其他頂點的所有邊為候選邊；

（2）重複以下步驟（n-1）次，使得其他（n-1）個頂點被加入到U中：

1.從侯選邊中挑選權值最小的邊加入TE，設該邊在V-U中的頂點是k，将k加入U中；

2.考察目前V-U中所有頂點j，修改侯選邊，若邊（k，j）的權值小于原來和頂點j關聯的侯選邊，則用邊（k，j）取代後者作為侯選邊

圖論（最短路，最小生成樹，并查集）

#include<stdio.h>
#include<string.h>
#include <iostream>
#include <bits/stdc++.h>
#define MAX 0x3f3f3f3f
using namespace std;
int logo[1010];//用來标記0和1  表示這個點是否被選擇過
int map1[1010][1010];//鄰接矩陣用來存儲圖的資訊
int dis[1010];//記錄任意一點到這個點的最近距離
int n;//點個數
int prim(){
    int i,j,now;
    int sum=0;
    /*初始化*/
    for(i=1; i<=n; i++){
        dis[i]=MAX;
        logo[i]=0;
    }
    /*標明1為起始點，初始化*/
    for(i=1; i<=n; i++){
        dis[i]=map1[1][i];
    }
    dis[1]=0;
    logo[1]=1;
    /*循環找最小邊，循環n-1次*/
    for(i=1; i<n; i++){
        now=MAX;
        int min1=MAX;
        for(j=1; j<=n; j++){
            if(logo[j]==0&&dis[j]<min1){
                now=j;
                min1=dis[j];
            }
        }
        if(now==MAX)
            break;//防止不成圖
        logo[now]=1;
        sum+=min1;
        for(j=1; j<=n; j++){//添入新點後更新最小距離
            if(logo[j]==0&&dis[j]>map1[now][j])
                dis[j]=map1[now][j];
        }
    }
    if(i<n)
        printf("?\n");
    else
        printf("%d\n",sum);
}
int main(){
    while(scanf("%d %d",&n,&m),n+m){//n是點數，m是邊數
        memset(map1,0x3f3f3f3f,sizeof(map1));//map是鄰接矩陣存儲圖的資訊
        for(int i=0; i<m; i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(c<map1[a][b])//防止重邊
                map1[a][b]=map1[b][a]=c;
        }
        prim();
    }
}

如果是想求最短路的話，隻需要将被調中更新數組部分的兩行代碼改為：

if(logo[j]==0&&dis[j]>map1[now][j]+dis[now])
                dis[j]=map1[now][j]+dis[now];

且此時min1和sum就沒有用了，可以删掉。另外還需注意：其中表示循環的變量，有好幾個都是從1開始的，如果純粹用來計數，從0開始不會有影響，但是其他的不能改，在其他題目中，要參考其題意再決定。

優先隊列實作dijkstra

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 10005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,cnt,s,e;
struct node{
    int to;
    int w;
    int next;
    bool operator<(const node&a)const{
        return a.w<w;
    }
}edge[maxn],Now,Next;
int head[maxn];

void init(){
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,int w){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}

bool vis[maxn];
int dis[maxn];
void dijkstra(int ans){
   memset(dis,inf,sizeof(dis));
   memset(vis,false,sizeof(vis));
   priority_queue<node>Q;
   Now.to=ans;
   dis[ans]=0;
   Q.push(Now);
   while(!Q.empty()){
    Now=Q.top();
    Q.pop();
    int now=Now.to;
    if(vis[now]) continue;
    vis[now]=true;
    for(int i=head[now];i!=-1;i=edge[i].next){
        int u=edge[i].to;
        if(!vis[u]&&dis[u]>dis[now]+edge[i].w){
            dis[u]=dis[now]+edge[i].w;
            Next.to=u;
            Next.w=dis[u];
            Q.push(Next);
            }
        }
    }
    printf("%d\n",dis[n]);
}

int main(){
    while(~scanf("%d %d",&n,&m)){
    if(n==0&&m==0) break;
    init();
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        }
    dijkstra(1);
    }
    return 0;
}

題目：https://www.luogu.org/problemnew/show/P1339

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 20005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,cnt,s,e;
struct node{
    int to;
    int w;
    int next;
    bool operator<(const node&a)const{
        return a.w<w;
    }
}edge[maxn],Now,Next;
int head[maxn];

void init(){
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,int w){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}

bool vis[maxn];
int dis[maxn];
void dijkstra(int ans){
   memset(dis,inf,sizeof(dis));
   memset(vis,false,sizeof(vis));
   priority_queue<node>Q;
   Now.to=ans;
   dis[ans]=0;
   Q.push(Now);
   while(!Q.empty()){
    Now=Q.top();
    Q.pop();
    int now=Now.to;
    if(vis[now]) continue;
    vis[now]=true;
    for(int i=head[now];i!=-1;i=edge[i].next){
        int u=edge[i].to;
        if(!vis[u]&&dis[u]>dis[now]+edge[i].w){
            dis[u]=dis[now]+edge[i].w;
            Next.to=u;
            Next.w=dis[u];
            Q.push(Next);
            }
        }
    }
    printf("%d\n",dis[e]-dis[s]);
}

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&e);
    init();
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        }
    dijkstra(s);
    return 0;
}

并查集：

https://www.luogu.org/problemnew/show/P2661

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int f[200005],d[2000005],n,minn,last;
int fa(int x){
    if(x!=f[x]){
        int last=f[x];
        f[x]=fa(f[x]);
        d[x]+=d[last];
    }
    return f[x];
}
void check(int a,int b){
    int fx=fa(a);
    int fy=fa(b);
    if(fx!=fy){
        f[fx]=fy;
        d[a]=d[b]+1;
    }
    else
    minn=min(minn,d[a]+d[b]+1);
}


int main(){
    int t;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) f[i]=i;
    minn=0x7777777;
    for(int i=1;i<=n;i++){
        scanf("%d",&t);
        check(i,t);
    }
    printf("%d\n",minn);
    return 0;
}

floyd(弗洛伊德) 最短路

整個算法一共隻有五行，三重循環＋一個判斷就能求出圖中任意兩點之間的最短路徑。

這個算法的主要思路，就是通過其他的點進行中轉來求的兩點之間的最短路。因為我們知道，兩點之間有多條路，如果換一條路可以縮短距離的話，就更新最短距離。而它最本質的思想，就是用其他的點進行中轉，進而達到求出最短路的目的。

核心代碼：

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(e[i][j]>e[i][k]+e[k][j])
                 e[i][j]=e[i][k]+e[k][j];

例題：https://www.luogu.org/problemnew/show/P1119

題目背景

BB地區在地震過後，所有村莊都造成了一定的損毀，而這場地震卻沒對公路造成什麼影響。但是在村莊重建好之前，所有與未重建完成的村莊的公路均無法通車。換句話說，隻有連接配接着兩個重建完成的村莊的公路才能通車，隻能到達重建完成的村莊。

題目描述

給出BB地區的村莊數NN，村莊編号從00到N-1N−1，和所有MM條公路的長度，公路是雙向的。并給出第ii個村莊重建完成的時間 ti ，你可以認為是同時開始重建并在第ti天重建完成，并且在當天即可通車。若ti 為0則說明地震未對此地區造成損壞，一開始就可以通車。之後有QQ個詢問(x, y, t)(x,y,t)，對于每個詢問你要回答在第tt天，從村莊xx到村莊y的最短路徑長度為多少。如果無法找到從xx村莊到yy村莊的路徑，經過若幹個已重建完成的村莊，或者村莊xx或村莊yy在第t天仍未重建完成，則需要傳回-1−1。

#include<iostream>
#include<cstdio>
#define N 205
using namespace std;
int n,m;
int a[N];
int f[N][N];//鄰接矩陣存邊
inline void updata(int k){
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(f[i][j]>f[i][k]+f[j][k])
    f[i][j]=f[j][i]=f[i][k]+f[j][k];//用這個新的更新所有前面的 
    return;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
    scanf("%d",a+i);//依次輸入每一個村莊建立完成時需要的時間
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        f[i][j]=1e9;//初始化為保證它不爆炸範圍内的最大值 
    }
    for(int i=0;i<n;i++)
    f[i][i]=0;
    int s1,s2,s3;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&s1,&s2,&s3);
        f[s1][s2]=f[s2][s1]=s3;//初始化邊長 
    }
    int q;
    cin>>q;
    int now=0;
    for(int i=1;i<=q;i++){//處理各詢問 
        scanf("%d%d%d",&s1,&s2,&s3);
        while(a[now]<=s3&&now<n){
            updata(now);//依次更新點，使它可以被用來更新其他的點 
            now++;
        }
        if(a[s1]>s3||a[s2]>s3)cout<<-1<<endl;
        else {
            if(f[s1][s2]==1e9)cout<<-1<<endl;
            else cout<<f[s1][s2]<<endl;
        }
    }
    return 0;
}

圖論（最短路，最小生成樹，并查集）

本文目錄：

判斷環：

最小生成樹

Kruskal 模闆

Prim

優先隊列實作dijkstra

并查集：

floyd(弗洛伊德) 最短路

核心代碼：

題目背景

題目描述

繼續閱讀

【POJ】Find them, Catch them

POJ 1734 Sightseeing trip

POJ_1985_Cow Marathon(樹的直徑)

tarjan算法介紹與分析

HDU 2363 Cycling 二分+ 限制最短路

POJ 3020 Antenna Placement 二分比對

HDU 5876 Sparse Graph

Codeforces Round #319 (Div. 2) B C D

Codeforces Round #369 (Div. 2) [D] Directed RoadsDirected Roads

Codeforces Round #264 (Div. 2) D

HDU 3268 Columbus’s bargain

PAT刷題小結

HDU 4725 The Shortest Path in Nya Graph

HDU 5923 Prediction

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【趨高機器視覺】機器視覺技術原了解析及解決方案