天天看點
傳回

（轉）Tarjan應用

以下轉載自:http://hi.baidu.com/lydrainbowcat/item/f8a5ac223e092b52c28d591c

基本概念： 

1.割點：若删掉某點後，原連通圖分裂為多個子圖，則稱該點為割點。

2.割點集合：在一個無向連通圖中，如果有一個頂點集合，删除這個頂點集合，以及這個集合中所有頂點相關聯的邊以後，原圖變成多個連通塊，就稱這個點集為割點集合。

3.點連通度：最小割點集合中的頂點數。

4.割邊(橋)：删掉它之後，圖必然會分裂為兩個或兩個以上的子圖。

5.割邊集合：如果有一個邊集合，删除這個邊集合以後，原圖變成多個連通塊，就稱這個點集為割邊集合。

6.邊連通度：一個圖的邊連通度的定義為，最小割邊集合中的邊數。

7.縮點：把沒有割邊的連通子圖縮為一個點，此時滿足任意兩點之間都有兩條路徑可達。

注：求塊<>求縮點。縮點後變成一棵k個點k-1條割邊連接配接成的樹。而割點可以存在于多個塊中。

8.雙連通分量：分為點雙連通和邊雙連通。它的标準定義為：點連通度大于1的圖稱為點雙連通圖，邊連通度大于1的圖稱為邊雙連通圖。通俗地講，滿足任意兩點之間，能通過兩條或兩條以上沒有任何重複邊的路到達的圖稱為雙連通圖。無向圖G的極大雙連通子圖稱為雙連通分量。

Tarjan算法的應用論述：

1.求強連通分量、割點、橋、縮點：

對于Tarjan算法中，我們得到了dfn和low兩個數組，

low[u]:=min(low[u],dfn[v])——(u,v)為後向邊，v不是u的子樹；

low[u]:=min(low[u],low[v])——(u,v)為樹枝邊，v為u的子樹；

下邊對其進行讨論：

若low[v]>=dfn[u],則u為割點，節點v的子孫和節點u形成一個塊。因為這說明v的子孫不能夠通過其他邊到達u的祖先，這樣去掉u之後，圖必然分裂為兩個子圖。這樣我們處理點u時，首先遞歸u的子節點v，然後從v回溯至u後，如果發現上述不等式成立，則找到了一個割點u，并且u和v的子樹構成一個塊。

void tarjan(int x)

{

 v[x]=1,dfn[x]=low[x]=++num;

 for(int i=head[x];i;i=next[i])

  if(!v[ver[i]])

  {

   tarjan(ver[i]);

   low[x]=min(low[x],low[ver[i]]);

   if(dfn[x]<=low[ver[i]]) v[x]++;

  }

  else low[x]=min(low[x],dfn[ver[i]]);

 if((x==1&&v[x]>2)||(x>1&&v[x]>1)) v[x]=2; else v[x]=1;//v[x]=2表示該點為割點，注意其中第一個點要特判

}

若low[v]>dfn[u],則(u,v)為割邊。但是實際處理時我們并不這樣判斷，因為有的圖上可能有重邊，這樣不好處理。我們記錄每條邊的标号（一條無向邊拆成的兩條有向邊标号相同），記錄每個點的父親到它的邊的标号，如果邊(u,v)是v的父親邊，就不能用dfn[u]更新low[v]。這樣如果周遊完v的所有子節點後，發現low[v]=dfn[v]，說明u的父親邊(u,v)為割邊。

void tarjan(int x)

{

 vis[x]=1;

 dfn[x]=low[x]=++num;

 for(int i=head[x];i;i=next[i])

  if(!vis[ver[i]])

  {

   p[ver[i]]=edge[i];//記錄父親邊

   tarjan(ver[i]);

   low[x]=min(low[x],low[ver[i]]);

  }

  else if(p[x]!=edge[i])//不是父親邊才更新

   low[x]=min(low[x],dfn[ver[i]]);

 if(p[x]&&low[x]==dfn[x]) f[p[x]]=1;//是割邊

}

 2.求雙連通分量以及構造雙連通分量：

對于點雙連通分支，實際上在求割點的過程中就能順便把每個點雙連通分支求出。建立一個棧，存儲目前雙連通分支，在搜尋圖時，每找到一條樹枝邊或後向邊(非橫叉邊)，就把這條邊加入棧中。如果遇到某時滿足DFS(u)<=Low(v)，說明u是一個割點，同時把邊從棧頂一個個取出，直到遇到了邊(u,v)，取出的這些邊與其關聯的點，組成一個點雙連通分支。割點可以屬于多個點雙連通分支，其餘點和每條邊隻屬于且屬于一個點雙連通分支。

對于邊雙連通分支，求法更為簡單。隻需在求出所有的橋以後，把橋邊删除，原圖變成了多個連通塊，則每個連通塊就是一個邊雙連通分支。橋不屬于任何一個邊雙連通分支，其餘的邊和每個頂點都屬于且隻屬于一個邊雙連通分支。

一個有橋的連通圖，如何把它通過加邊變成邊雙連通圖？方法為首先求出所有的橋，然後删除這些橋邊，剩下的每個連通塊都是一個雙連通子圖。把每個雙連通子圖收縮為一個頂點，再把橋邊加回來，最後的這個圖一定是一棵樹，邊連通度為1。

統計出樹中度為1的節點的個數，即為葉節點的個數，記為leaf。則至少在樹上添加(leaf+1)/2條邊，就能使樹達到邊二連通，是以至少添加的邊數就是(leaf+1)/2。具體方法為，首先把兩個最近公共祖先最遠的兩個葉節點之間連接配接一條邊，這樣可以把這兩個點到祖先的路徑上所有點收縮到一起，因為一個形成的環一定是雙連通的。然後再找兩個最近公共祖先最遠的兩個葉節點，這樣一對一對找完，恰好是(leaf+1)/2次，把所有點收縮到了一起。

3.求最近公共祖先（LCA）

在周遊到u時，先tarjan周遊完u的子樹，則u和u的子樹中的節點的最近公共祖先就是u,并且u和【u的兄弟節點及其子樹】的最近公共祖先就是u的父親。注意到由于我們是按照DFS順序周遊的，我們可用一個color數組标記，正在通路的染色為1，未通路的标記為0，已經通路到即在【u的子樹中的】及【u的已通路的兄弟節點及其子樹中的】染色标記為2，這樣我們可以通過并查集的不斷合并更新，通過getfather實作以上目标。

void tarjan(int x)

{

 fa[x]=x,color[x]=1;

 int i,y;

 for(i=head[x];i;i=next[i])

  if(color[y=ver[i]]==0)

  {

   tarjan(y);

   fa[y]=x;

  }

 for(i=headquery[x];i;i=nextquery[i])

  if(color[y=query[i]]==2) ans[i]=get(y);

 color[x]=2;

}

以下轉自LHQ神犇http://blog.csdn.net/lhq_er/article/details/74942801

　　　　　　　　http://blog.csdn.net/lhq_er/article/details/74911231

簡介

Tarjan作為一位算法大師，發明了許多算法。本篇博文介紹一下Tarjan架構下的求解樹上LCA（最近公共祖先）的離線算法，複雜度O(N+Q)。以及求割點，橋的算法，複雜度O(V+E),即dfs 1次所需的時間。

Tarjan_LCA

Problem:

一棵樹，n個節點，Q組詢問（x，y），求x,y的LCA

思路：

  1. 最暴力的想法，x,y都向上搜尋，因為向上的節點就是x或y的祖先，是以搜到的第一個公共節點就是x和y的LCA，複雜度O(QN)；
  2. 一種簡單的優化方法是把關于x的所有詢問一起處理，這樣x隻需要向上搜尋1次，優化一下常數；
  3. 任何題目的方法歸根結底都是枚舉，我們注意到之前我們是在枚舉詢問，規模為O(Q)，一般Q是O(N^2)級别的，是以我們似乎可以換一下思路，去枚舉一下答案，也就是LCA，這個的規模隻是O(N)。——————————在觀察我們發現u的不同子樹中的節點的LCA是u，這樣，一個想法就形成了。現在讓我們來看一下算法導論中完整版的dfs：

請讀者仔細閱讀這段僞代碼，這幾乎是在全面的前提下最精簡的版本了，少了任何一句話都不行，尤其是其中的“白”“灰”“黑”三種顔色與時間戳的概念，在很多進階算法中是必不可少的，也是很多進階算法創造根源，Tarjan_LCA算法在這個基礎上就很容易了解。

（轉）Tarjan應用

來個例子，本例子中，x1 < x2 < x3 < x4 < x5 < x6 

畫出時間戳可以發現u，v的時間戳不相交，這樣我們可以輕易得出以下定理：

  • 當出現“灰黑灰”時，x為u向上第一個灰點，則path(u,x)上的點和v的LCA為x。 

    簡單來說就是上面的直覺，x下一顆子樹u内節點與另外子樹中節點的LCA均為x 

    這樣的性質讓我們想到了一種資料結構——并查集 

    廢話不多說，上CLRS僞代碼：

LCA(u)
    MAKE_SET(u);
    FIND_SET(u).ancestor=u;
    for each child v of u in T
        LCA(v)
        UNION(u,v)
        FIND_SET(u).ancestor=u
    u.color=BLACK
    for each node v such that (u,v) in P if v.color==BLACK print "The least common ancestor of" u "and" v "is" FIND_SET(v).ancestor

http://www.cnblogs.com/JVxie/p/4854719.html

這個網站有比較詳細的模拟過程，可以看一看加深了解 

http://blog.csdn.net/jarily/article/details/8947928 

再轉一份比較清晰的解釋： 

*算法思想: 

*Tarjan_LCA離線算法; 

*Tarjan算法基于dfs的架構,對于新搜到的一個結點,首先建立由這個結點構成的集合,再對目前結點的每個子樹進行搜尋; 

*每搜尋完一棵子樹,則可确定子樹内的LCA詢問都已解決,其他的LCA詢問的結果必然在這個子樹之外; 

*這時把子樹所形成的集合與目前結點的集合合并,并将目前結點設為這個集合的祖先; 

*之後繼續搜尋下一棵子樹,直到目前結點的所有子樹搜完; 

* 

*這時把目前結點也設為已被檢查過的,同時可以處理有關目前結點的LCA詢問; 

*如果有一個從目前結點到結點v的詢問,且v已經被檢查過; 

*則由于進行的是dfs,目前結點與v的最近公共祖先一定還沒有被檢查; 

*而這個最近公共祖先的包含v的子樹一定已經搜尋過了,那麼這個最近公共祖先一定是v所在集合的祖先; 

* 

*算法步驟: 

*對于每一個結點: 

*(1)建立以u為代表元素的集合; 

*(2)周遊與u相連的結點v,如果沒有被通路過,對于v使用Tarjan_LCA算法,結束後将v的集合并入u的集合; 

*(3)對于與u有關的詢問(u,v),如果v被通路過,則結果就是v所在集合的代表元素;

習題： 

模闆題： 

1.poj 1330 

2.http://acm.zjnu.edu.cn/CLanguage/showproblem?problem_id=1232 交通運輸線

算法介紹

Tarjan_割點

  • 适用範圍：無向圖
  • 功能：給定無向圖G=(V,E)，求出一個點集合V’，包含圖中所有的割點。
  • 時間複雜度：O(N+E)，N為圖中點數,E為圖中邊數。

Tarjan_橋

  • 适用範圍：無向圖
  • 功能：給定無向圖G=(V,E)，求出一個邊集合E’，包含圖中所有的橋。
  • 時間複雜度：O(N+E)，N為圖中點數,E為圖中邊數。

算法講解

一些概念：

  1. 點連通度：去掉最少的點使得圖分為若幹聯通分支。隻有點連通度為1的圖有割點.
  2. 割點：若去掉某個節點将會使圖分為若幹聯通分支，則改點稱為割點。
  3. 邊連通度：去掉最少的邊使得圖分為若幹聯通分支。隻有邊連通度為1的圖有橋。
  4. 橋：若去掉某條邊将會使圖分為若幹聯通分支，則改邊稱為橋。

現實意義：

通信網絡中，用來衡量系統可靠性，連通度越高，可靠性越高。

割點

  1. 暴力求解，依次删除每一個節點v，用DFS（或者BFS）判斷是否連通，再把節點加入圖中。若用鄰接表（adjacency list），需要做V次DFS，時間複雜度為O(V∗(V+E))。 

    這個算法複雜度太高，我們需要去改進它，我們想：能否一遍DFS求解？

  2. Tarjan算法 

    我們不難發現：一個頂點u是割點，當且僅當滿足(1)或(2) 

    (1) u為根節點，且u有多于一個子樹。 

    (2) u為非根節點，u有一個子節點s，且沒有任何從s或s的後代節點指向v的真祖先的後向邊。 

    對于根節點我們可以進行特判，那麼非根節點我們如何處理呢？ 

    思路： 

    我們定義DNF[v]為v結點的入時間戳，即根據dfs序給節點進行編号，定義LOW[v]為v及v的子孫所能達到的最小節點的DFN，那麼判定v是否是節點就很友善了，隻要u有一個兒子v，使得DNF[u]< =LOW[v],則u是割點。

橋：

  1. 思路和求割點一樣，也需要dfn數組和low數組輔助，隻是不用判根，（u，v）是橋當且僅當DFN[u]< low[v]，因為若u有一個子節點v，v及它的子孫所能到達的節點不超過v，及無法到u以上，那麼這條樹邊就是橋了。
  2. 需要注意的是重邊情況，若有兩條邊（1,2），（2,1），那麼都不是橋但是若隻有一條（1,2），則是橋。但是在處理的時候若隻按照（v!=fa)判斷，這兩條邊隻算了一條，我們需要的是不重複計算同一條邊 ，那麼如何判斷是不是同一條邊呢？鍊式前向星為我們提供了一種方法，因為邊存儲時同一條邊的序号是（1,2），（3,4），……這樣下去的，若((i+1)/2==(j+1)/2)則i，j是同一條邊，這樣就判斷出來了。

CODE

割點模闆：

// luogu P3388
#include<bits/stdc++.h>
using namespace std; const int MAXN=

橋模闆（可處理重邊）：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=

轉載于:https://www.cnblogs.com/SXia/p/7152985.html

資料結構與算法
上一篇: 《精通Spring》筆記1.1 Spring Framework1.2 Spring Framework為什麼流行1.3 Spring子產品
下一篇: matlab經驗模态分解代碼_經驗模态分解法

繼續閱讀