• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      Tarjan算法在程序設(shè)計競賽中的應(yīng)用探析

      2023-06-10 12:41:51郭涵濤毛玉萃
      電腦知識與技術(shù) 2023年12期
      關(guān)鍵詞:實例

      郭涵濤 毛玉萃

      關(guān)鍵詞:Tarjan;程序類競賽;實例

      中圖分類號:TP311.52 文獻標識碼:A

      文章編號:1009-3044(2023)12-0029-05

      1 Tarjan 算法簡述[1]

      Tarjan 算法是基于深度優(yōu)先搜索的算法,由著名計算機科學家Robert Tarjan發(fā)明,用于求解圖的連通性問題。Tarjan 算法可以在線性時間內(nèi)求出無向圖的割點與橋,進一步地可以求解無向圖的連通分量;也可以求解有向圖的強連通分量、必經(jīng)點與必經(jīng)邊;該算法是圖論中非常實用且常用的算法之一,能解決強連通分量,雙連通分量,割點和橋,以及求最近公共祖先(LCA) 等問題。

      1.1 Tarjan 問題中的概念介紹

      割點:如果一個節(jié)點X和所有與X關(guān)聯(lián)的邊從圖中刪除后,圖會被分割成兩個或兩個以上不相連的子圖,那么這個分割點就叫作X。

      割邊:如果把圖中的邊e去掉后,圖就會被分割成兩個不相連的子圖,那么這條邊或者叫切邊或者叫割邊。

      時間戳:時間戳是用來標記圖中每個節(jié)點在進行深度優(yōu)先搜索時被訪問的時間順序,用dfn[x]來表示。

      搜索樹:在無向圖中,從某一個節(jié)點x 出發(fā)進行深度優(yōu)先搜索,每一個節(jié)點只訪問一次,所有被訪問過的節(jié)點與邊構(gòu)成一棵樹,稱之為“無向連通圖的搜索樹”。

      追溯值:追溯值用來表示從當前節(jié)點x 作為搜索樹的根節(jié)點出發(fā),能夠訪問到的所有節(jié)點中,時間戳最小的值,用low[x]來表示。所有節(jié)點包含:

      1) 以x為根的搜索樹的所有節(jié)點。

      2) 通過一條非搜索樹上的邊,能夠到達搜索樹的所有節(jié)點。

      1.2 Tarjan 算法的原理[1]

      Tarjan 算法是一種利用深度優(yōu)先搜索實現(xiàn)的圖算法,它能夠?qū)D中的節(jié)點按照強連通分量進行劃分,并將同一強連通分量中的節(jié)點放在一起。在搜索過程中,將未處理的節(jié)點加入一個棧中,并在回溯的過程中檢查棧頂?shù)綏V械墓?jié)點是否構(gòu)成了一個強連通分量。因此,每個強連通分量對應(yīng)于深度優(yōu)先搜索樹中的一棵子樹。

      算法:

      1) 當首次搜索到點u時dfn[u]=low[u]=time;

      2) 每當搜索到一個點,把該點壓入棧頂;

      3) 當u和v有邊相連時:

      當節(jié)點v不在棧中時(即遇到樹枝邊),執(zhí)行dfs(v) 操作,并將low[u]的值更新為min{low(u), low(v)};當節(jié)點v在棧中時(即遇到前向邊或后向邊),將low[u]的值更新為min{low[u], dfn[v]}。

      4) 當一個節(jié)點u的dfn值等于其low值時,意味著它所在的強連通分量已經(jīng)被完全探索并且已經(jīng)被壓入棧中。因此,可以將該節(jié)點及其在棧中之前的所有節(jié)點彈出棧,這樣彈出的節(jié)點構(gòu)成的集合就是一個強連通分量。

      5) 繼續(xù)搜索,直到圖被遍歷完畢。Tarjan算法的時間復(fù)雜度為O(n+m),因為在該算法中,每個節(jié)點僅被遍歷一次,每條邊也僅被遍歷一次。

      1.3 Tarjan 算法的競賽意義

      各類程序設(shè)計競賽里考察Tarjan的題目相比于其他算法題目并不是特別常見,但研究此類算法卻是小組成員學習其他圖論算法的必備條件之一。程序設(shè)計競賽對計算機相關(guān)專業(yè)的學生來說有著很大的幫助,考驗著學生的耐心、專注度、邏輯水平等。

      1.4 Tarjan 算法的C++代碼

      Tarjan算法的用C++實現(xiàn)的代碼如圖1所示。

      2 Tarjan 算法在程序設(shè)計競賽中幾種典型運用

      2.1 割點(割頂)問題[2]

      題目:給定一個包含n 個節(jié)點和m 條無向邊的圖,需要找出使圖不連通的最少節(jié)點集合,這個集合中的每個節(jié)點都是圖的割點。

      輸入:第一行輸入兩個正整數(shù)n,m。

      輸入m 條邊,每條邊用兩個正整數(shù)x 和y 表示,表示節(jié)點x 和節(jié)點y 之間有一條無向邊。輸出:第一行輸出割點個數(shù)。

      第二行按照節(jié)點編號從小到大輸出節(jié)點,用空格隔開。

      樣例輸入:6 7

      1 2

      1 3

      1 4

      2 5

      3 5

      4 5

      5 6 樣例輸出:1

      5

      分析:標準Tarjan割點題,按照定義去求即可,用C++實現(xiàn)的代碼如圖2所示。

      2.2 The Cow Prom S 問題[3]

      題目:有一個n 個點,m 條邊的有向圖,請求出這個圖點數(shù)大于1 的強聯(lián)通分量個數(shù)。

      輸入:第一行為兩個整數(shù)n 和m。

      從第二行到第m+1 行,每行給出兩個整數(shù)a 和b,表示有一條從節(jié)點a 指向節(jié)點b 的有向邊。

      輸出:僅一行,表示點數(shù)大于1 的強聯(lián)通分量個數(shù)。

      樣例輸入:5 4

      2 4

      3 5

      1 2

      4 1

      樣例輸出:1

      分析:要解決Tarjan 強連通分量問題,需要使用Tarjan 算法對圖進行計算,并統(tǒng)計強連通分量的數(shù)量。其主要部分代碼如圖3所示。

      2.3 受歡迎的牛G 問題[4]

      題目:每頭奶牛都夢想成為牛棚里的明星。被所有奶牛喜歡的奶牛就是一頭明星奶牛。每頭奶??偸窍矚g自己的,奶牛之間的“喜歡”是可以傳遞的——如果A 喜歡B,B 喜歡C,那么A 也喜歡C。牛欄里共有N 頭奶牛,給定一些奶牛之間的愛慕關(guān)系,請你算出有多少頭奶??梢援斆餍?。

      輸入:第一行:兩個用空格分開的整數(shù):N 和M。

      接下來M 行:每行兩個用空格分開的整數(shù):A 和B,表示A 喜歡B。

      輸出:一行單獨一個整數(shù),表示明星奶牛的數(shù)量。

      樣例輸入:3 3

      1 2

      2 1

      2 3

      樣例輸出:1

      分析:利用Tarjan 算法對圖進行強連通分量的計算并縮點后,可以得到一張有向無環(huán)圖(DAG),其中每個強連通分量被縮成一個點。在這個DAG 中,最受歡迎的奶??梢员欢x為出度為0的點,也就是那些沒有任何后繼節(jié)點的點。這個強連通分量的奶牛數(shù)量極為最受歡迎的奶牛數(shù)量,同時,如果有兩個及兩個以上的強連通分量則沒有最受歡迎的奶牛。因為這幾個強連通分量的奶牛無法相互傳遞“喜歡”,無法被所有奶牛喜歡。

      其主要代碼如圖4所示。

      2.4 縮點問題[5]

      題目:給定一個n 個點m 條邊有向圖,每個點有一個權(quán)值,求一條路徑,使路徑經(jīng)過的點權(quán)值之和最大。你只需要求出這個權(quán)值和。

      允許多次經(jīng)過一條邊或者一個點,但是,重復(fù)經(jīng)過的點,權(quán)值只計算一次。

      輸入:第一行兩個正整數(shù)n,m。

      第二行n 個整數(shù),其中第i 個數(shù)ai 表示點i 的點權(quán)。

      第三至m+2 行,每行兩個整數(shù)u,v,表示一條u→v 的有向邊。

      輸出:共一行,最大的點權(quán)之和。

      樣例輸入:2 2

      1 1

      1 2

      2 1 樣例輸出:2

      解析:由題意可知,需要找到一條點權(quán)和最大的路徑,且可以重復(fù)走。這樣第一時間就會考慮到出現(xiàn)環(huán)的情況,在題目要求權(quán)值最大的情況下,有環(huán)肯定需要把環(huán)上的點全走一遍。這時候就會用到縮點的技巧。如果不使用縮點,很多算法都無法兼容。使用完縮點之后就可以正常處理。

      因為是有向圖,可以采用拓撲排序+dp來進行順推答案,維護到達點的最大權(quán)值和。其實現(xiàn)的主要部分代碼如圖5所示。

      2.5 Line Graph Matching(2021ICPC 沈陽站)問題[6]

      題目:在圖論這門數(shù)學學科中,一個簡單的無向加權(quán)圖G 的線圖是另一個簡單的有向加權(quán)圖L(G)。線圖L(G)是一種由圖G 轉(zhuǎn)換而來的圖形,它的構(gòu)造方法是:將圖G 中的每個頂點用一條線段表示,線段的長度等于該頂點的度數(shù);然后在L(G) 中,若圖G 中有兩條邊e1 和e2 共享一個頂點v,則在L(G) 中會用一個點來連接頂點e1 和頂點e2。因此,L(G) 表示的是圖G 中每兩條邊之間的鄰接關(guān)系,這種關(guān)系可以通過連接L(G) 中的點來表示。

      具體來說,對于沒有環(huán)或多條邊的無向加權(quán)圖G,其線圖L(G)是一個無向的加權(quán)圖,滿足以下條件:

      L(G)的每個頂點表示G的一條邊;

      如果在圖G中,兩個頂點之間的邊的權(quán)重等于它們對應(yīng)邊的權(quán)重之和,并且這兩個頂點對應(yīng)的邊共享一個公共點,那么這兩個頂點就是相鄰的。

      簡單無向加權(quán)圖中的最大加權(quán)匹配被定義為一組邊,其中沒有兩條邊共享一個公共頂點,并且該集合中的邊的權(quán)重之和被最大化。

      給定一個簡單的無向加權(quán)連通圖G,你的任務(wù)是找到L(G)的最大加權(quán)匹配中的邊的權(quán)重之和。

      輸入:第一行包含兩個整數(shù)n和m,表示頂點數(shù)和給定圖G中的邊數(shù)。

      然后沿著m條線,其中第i條線包含三個整數(shù)u,u 和w,表明圖中的第i條邊是w的權(quán)重,并連接第u個頂點和第v個頂點。保證了圖G是連通的,并且不包含循環(huán)和多條邊。

      輸出:輸出包含單個整數(shù)的行,表示L(G)的最大加權(quán)匹配中的邊的權(quán)重之和。

      樣例輸入:5 6

      1 2 1

      1 3 2

      1 4 3

      4 3 4

      4 5 5

      2 5 6

      樣例輸出:21

      解析:該題有兩種情況,一種情況為邊的數(shù)量為偶數(shù),由深度優(yōu)先搜索樹可以推出,如果一個節(jié)點的子樹有一條邊未匹配,則使用父節(jié)點的邊進行配對,如果子樹完美配對,則繼續(xù)往上遞歸。所以,偶數(shù)條邊一定可以把所有邊進行完美配對。

      另一種情況為邊的數(shù)量為奇數(shù),可以按照上一種情況轉(zhuǎn)換,相當于偶數(shù)條邊去掉了一條邊。

      刪邊之后會有兩種情況,一種為分成兩個聯(lián)通塊(刪的邊為割邊),另一種為偶數(shù)條邊的單個聯(lián)通塊(刪的邊為非割邊)。

      前者又分為兩個奇數(shù)條邊聯(lián)通塊,和兩個偶數(shù)條邊聯(lián)通塊。前者因為會加大損耗,且可以轉(zhuǎn)換成另外兩種情況。

      最后結(jié)果為取兩種情況的最小值(刪掉損失最小的邊),剩下的即為最大的權(quán)重之和。其實現(xiàn)的主要部分代碼如圖6所示。

      3 Tarjan 算法在其他算法中的運用

      拓撲排序:Tarjan算法可以用來對有向無環(huán)圖進行拓撲排序。

      二分圖檢測:Tarjan算法可以用于檢測一個無向圖是否為二分圖。

      最小生成樹:Tarjan算法可以用于Kruskal算法中的最小生成樹算法,以找到圖中的最小生成樹。

      有向無環(huán)圖的最長路徑:通過對有向無環(huán)圖進行拓撲排序,可以使用Tarjan算法來找到有向無環(huán)圖的最長路徑。

      網(wǎng)絡(luò)流算法:Tarjan算法可以用于網(wǎng)絡(luò)流算法中,例如在最大流算法中,它可以用來找到殘量圖中的增廣路徑。

      總之,Tarjan算法是一個非常有用的算法,可以應(yīng)用于多種圖論的算法中,并且在實踐中得到廣泛的應(yīng)用。

      4 Tarjan 算法在工程上的運用

      1) 編譯器中的語法分析:在編譯器中,Tarjan 算法被應(yīng)用于生成語法分析器。語法分析器的任務(wù)是將源代碼轉(zhuǎn)化為一個抽象語法樹,然后進行語義分析和生成代碼。Tarjan算法可以在語法分析器中用于檢測循環(huán)依賴和死鎖等問題。

      2) 數(shù)據(jù)庫中的事務(wù)管理:在數(shù)據(jù)庫管理系統(tǒng)中,Tarjan算法可以用于事務(wù)管理,特別是在分布式數(shù)據(jù)庫中。在這種情況下,Tarjan算法可以用于檢測數(shù)據(jù)庫中的死鎖,以確保事務(wù)的正確執(zhí)行。

      3) 圖形編輯器中的拓撲排序:在圖形編輯器中,Tarjan算法可以用于執(zhí)行拓撲排序,以便在處理有向無環(huán)圖時能夠按照正確的順序處理圖形元素。

      4) 軟件工程中的模塊依賴分析:在軟件工程中,Tarjan算法可以用于模塊依賴分析。模塊依賴分析可以幫助開發(fā)人員識別軟件模塊之間的依賴關(guān)系,以便更好地組織和管理代碼庫。

      5) 網(wǎng)絡(luò)協(xié)議中的路由算法:在網(wǎng)絡(luò)協(xié)議中,Tarjan 算法可以用于路由算法,以幫助網(wǎng)絡(luò)節(jié)點找到最佳的路由路徑。例如,在因特網(wǎng)中,Tarjan算法可以用于實現(xiàn)BGP(Border Gateway Protocol) 協(xié)議,以幫助互聯(lián)網(wǎng)服務(wù)提供商找到最佳的路由路徑。

      總的來說,Tarjan算法是一種非常通用的算法,可以應(yīng)用于多個領(lǐng)域和場景中。

      5 總結(jié)

      Tarjan算法在解決強連通分量問題方面具有重要的地位,它在解決強連通分量問題方面具有重要的地位,還可以應(yīng)用到許多其他的圖算法中。它不僅在理論上有著優(yōu)秀的性能表現(xiàn),而且在實際應(yīng)用中也得到了廣泛的使用和驗證。

      猜你喜歡
      實例
      應(yīng)用GGB研究一類不等式求解實例及拓展
      信用證償付實例剖析
      中國外匯(2019年12期)2019-10-10 07:26:58
      就地瀝青熱再生應(yīng)用實例探討
      Catalan數(shù)及幾種應(yīng)用實例
      商情(2017年42期)2017-12-26 12:34:41
      一起肉鴨球蟲病的診治實例
      完形填空Ⅱ
      完形填空Ⅰ
      國外先進信息技術(shù)應(yīng)用實例
      杭州科技(2014年4期)2014-02-27 15:26:58
      基于實例的純電動汽車動力系統(tǒng)匹配與驗證
      河南科技(2014年1期)2014-02-27 14:04:25
      理想化最速下降法及其逼近實例
      塔城市| 泽州县| 四川省| 漳平市| 平江县| 枣庄市| 融水| 杭州市| 南丹县| 扎赉特旗| 隆尧县| 积石山| 保德县| 于田县| 皮山县| 阿城市| 柯坪县| 铁岭县| 乡宁县| 石景山区| 青海省| 宜良县| 安义县| 前郭尔| 旬阳县| 昭平县| 大洼县| 繁峙县| 遂昌县| 嘉峪关市| 阳高县| 广东省| 靖远县| 邳州市| 社旗县| 临高县| 磐石市| 海门市| 吴川市| 南通市| 西盟|