Embedded Files
圖形演算法除了深度優先搜尋、廣度優先搜尋與找尋最短路徑外，還有其他演算法，部分需要用到深度優先或廣度優先搜尋演算法的概念，再加上其他圖形演算法的概念來進行解題。以下每個主題都有其適用的情境，與要解決的問題類型，需要仔細了解。
12-1 拓撲排序(Topology Sort)
有時某件工作開始前，一定需要先完成另一樣工作，這樣找尋工作的執行順序，稱作拓撲排序(Topology Sort)，符合條件的拓撲排序結果可能不只一種，若沒有其他限制，找出其中一種即可，也有可能無解，這種問題以圖形表示，則會轉換成有向圖。若A連向B，表示執行工作B時，先要完成工作A才行，如下圖。
何時會無法找到拓撲排序的解答，當有向圖出現循環(cycle)，就無法獲得拓撲排序，如下圖，彼此都需要等對方完成才可以執行。
可以找到拓撲排序解答的圖形，一定是沒有循環的有向圖，這樣的圖稱作有向無環圖(Directed Acyclic Graph：縮寫為DAG)。
拓撲排序(Topology Sort)
找出下圖的拓撲排序為例，進行解說。
12-1-1-拓撲排序
給定最多50個節點以內的有向無環圖(Directed Acyclic Graph)，每個節點編號由0開始編號，且節點編號不會重複，相同起點與終點的邊只有一個，請找出一個可行的拓撲排序，且輸入資料保證至少可以找到一個拓撲排序。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個有向邊，接下來有m行，每個邊輸入兩個節點編號，保證節點編號由0到(n-1)。
輸出說明
請找出一個可行的拓撲排序。
範例輸入
範例輸出
0 2 3 4 1
找出拓撲排序的程式實作想法
使用陣列indeg紀錄每個點輸入邊的個數，找尋陣列indeg中輸入邊個數為0的點，若有這樣的點，則選擇其中一個點進行輸出，並刪除該點所連出去的邊。在陣列indeg中「被刪除邊的另一個端點的節點編號」的數值遞減1，可能有更多點，其連進來的邊數為0，繼續選擇陣列indeg中還未輸出且數值為0的點進行輸出，並刪除該點所連出去的邊，修改陣列indeg的元素數值，直到輸出所有的點為止。
(a)程式碼與解說
(12-1-1-拓撲排序.py)
第1行：宣告G為二維陣列。
第2到3行：宣告indeg與v為51個元素的串列，每個元素值都是0。
第4行：宣告變數cnt初始化為0。
第5到8行：宣告一個Edge類別，由2個元素描述一個邊，這個邊是具有方向性的，分別是s與t ，s為邊的起點，t為邊的終點。
第9到11行：使用input函數輸入兩個整數字串到變數n與m，使用int函式將整數字串變數n與m轉換成整數，再使用變數n與m參考到轉換後的整數，變數n為點的個數，變數m為邊的個數。
第12到18行：使用迴圈執行m次，每次輸入2個資料，表示邊的兩個頂點到變數a與b (第13到15行)。indeg[b]遞增1，表示連結到點b的邊的個數增加1，設定物件e1的s為a、物件e1的t為b (第17行)。將e1加入到G[a]的最後，表示點a可以到點b (第18行)。
第19到31行：使用迴圈變數i，由0到(n-1)，每次遞增1，執行以下動作。
第21到26行：若indeg[i]等於0，表示點i沒有邊連入，且v[i]等於0表示還沒有拜訪過，可以當成下一個輸出的點，設定v[i]為1，表示已經拜訪(第22行)，變數cnt遞增1(第23行)，輸出變數i的值到螢幕上(第24行)。讀取G[i]的每一個元素值到變數item，indeg[item.t]的值遞減1，表示連入點item.t的邊個數少1(第25到26行)。
第27到28行：若cnt等於n，表示已經拜訪過所有點，則中斷迴圈執行。
第29到30行：若變數i等於(n-1)，則設定變數i為-1(第31行遞增1後，讓迴圈從0開始繼續執行。)
第31行：變數i遞增1。
(b)程式執行結果
輸入以下測試資料。
5 7
0 1
0 2
0 3
0 4
2 3
3 4
4 1
執行結果顯示在螢幕如下。
0 2 3 4 1
(c)程式效率分析
執行第20到31行的演算法效率每個邊與點最多拜訪一次，所以演算法效率為O(n+m)，n為點的個數，m為邊的個數。
12-2 尤拉迴路(Euler Circuit)
尤拉迴路(Euler Circuit)是給定一個圖形，判斷是否有可能經過圖形中每一個邊剛好一次，可以由起始點走回到起始點，若可以找出這樣的迴路稱作尤拉迴路(Euler Circuit)。
尤拉路徑(Euler Trail)是給定一個圖形，判斷是否有可能經過圖形中每一個邊剛好一次，可以由起點走到終點，而起點與終點不一定要相同，若可以找出這樣的路徑稱作尤拉路徑(Euler Trail)，很明顯尤拉迴路(Euler Circuit)也是尤拉路徑(Euler Trail)。
對於起點與終點外的任何一個點，有進入該點的邊，就要有可以出去的邊，才可以經由邊進出每個點，可以計算每個節點的進入邊的個數與出去邊的個數，來判定是否有尤拉迴路(Euler Circuit)或尤拉路徑(Euler Trail)，可以歸納出以下結論。
12-2-1-尤拉路徑
給定最多20個節點以內的有向圖，相同起點與終點的有向邊可以重複，請判斷是否可以形成尤拉路徑。
輸入說明
輸入正整數m，表示圖形中有m個有向邊，接下來有m行，每個邊輸入兩個節點名稱。
輸出說明
請找出是否可以形成尤拉路徑。
範例輸入(一)
5
A B
B C
C D
D E
E A
範例輸出(一)
可以找到尤拉路徑
範例輸入(二)
5
A B
B C
C D
E F
F E
範例輸出(二)
無法找到尤拉路徑
找出尤拉路徑的程式實作想法
使用陣列indeg紀錄每個點進入的邊個數，與陣列outdeg紀錄每個點出去的邊個數，根據陣列indeg與outdeg統計所有點中進入的邊與出去的邊個數多1個的節點數到nin，所有點中出去的邊與進入的邊個數多1個的節點數到nout，所有點中進入的邊與出去的邊個數相同的節點數到nequ，經由nin、nout與nequ判斷是否可能有尤拉路徑，最後使用深度優先搜尋判斷圖形是否可以連通，若可以連通則確定有尤拉路徑。
(a)程式碼與解說
(12-2-1-尤拉路徑.py)
第1行：宣告G為二維陣列。
第2行：宣告City為空字典。
第3到5行：宣告v、indeg與outdeg為20個元素的串列，每個元素值都是0。
第6行：宣告變數nout、nin與nequ初始化為0。
第7行：宣告變數success初始化為False。
第8到11行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定City[p]所對應的值為字典City的長度(第9到10行)。回傳字典City以p為鍵值的對應值(第11行)。
第12到17行：定義dfs函式，以x當成輸入參數，設定v[x]為1。若G[x]的長度大於0，使用迴圈變數i存取G[x]的每一個元素，若v[i.t]等於0，表示點i.t未拜訪過，則遞迴呼叫dfs函式，以i.t為傳入參數。
第18到21行：宣告一個Edge類別，由2個元素描述一個邊，這個邊是具有方向性的，分別是s與t ，s為邊的起點，t為邊的終點。
第22行：使用input函數輸入整數字串，接著使用int函式將整數字串轉換成整數，再使用變m參考到轉換後的整數，變數m為邊的個數。
第23到30行：使用迴圈執行m次，每次輸入2個資料，表示邊的兩個頂點，將頂點名稱轉換成編號到變數a與b (第24到26行)。indeg[b]遞增1，表示連入點b的邊的個數增加1 ，outdeg[a]遞增1，表示連出點a的邊的個數增加1(第27到28行)。設定物件e1的s為a、物件e1的t為b (第29行)。將e1加入到G[a]的最後，表示點a可以到點b (第30行)。
第31到41行：迴圈變數i，由0到len(City)-1，每次遞增1，若indeg[i]不等於outdeg[i]，表示點i連入的邊與出去的邊個數不相同，則若indeg[i]-outdeg[i]等於1，表示點i進入的邊比出去的邊多一個，則變數nin增加1(第33到34)；否則若outdeg[i]-indeg[i]等於1，表示點i出去的邊比進來的邊多一個，則變數nout增加1，設定變數 start為變數i的數值(第35到37行)，儲存路徑的起點節點編號到變數 start，否則indeg[i]與outdeg[i]的差距大於等於2，則一定不會有尤拉路徑，使用break中斷迴圈(第38到39行)。
第40到41行：否則，表示indeg[i]與outdeg[i]相等，則變數nequ遞增1。
第42到43行：若nin等於1，且nout等於1，且nequ等於(len(City)-2)，則設定success為True，表示可能有尤拉路徑。
第44到45行：若nin等於0，且nout等於0，且nequ等於len(City)，則設定success為True，表示可能有尤拉迴路。
第46到53行：若success等於True，則若nout等於1，則呼叫dfs函式，以start傳入，進行深度優先搜尋(第47到48行)。若nout等於0，則使用迴圈變數i，由0到len(City)-1，每次遞增1，若outdeg[i]大於0，表示該點可以連結出去，呼叫dfs函式，以i傳入，進行深度優先搜尋，深度搜尋完成後，使用break中斷並跳出迴圈(第53行)。
第54到57行：使用迴圈變數i，由0到len(City)-1，每次遞增1，若v[i]等於0，表示該點還未拜訪，設定success為False(表示圖形無法連通)，使用break中斷並跳出迴圈(第54到57行)。
第58到61行：若success為True，顯示「可以找到尤拉路徑」，否則顯示「無法找到尤拉路徑」。
(b)程式執行結果
輸入以下測試資料。
範例輸入(一)
5
A B
B C
C D
D E
E A
範例輸出(一)
可以找到尤拉路徑
範例輸入(二)
5
A B
B C
C D
E F
F E
範例輸出(二)
無法找到尤拉路徑
(c)程式效率分析
本程式最花時間計算的部分是深度優先搜尋演算法(第12行與第17行)，每個邊與點最多拜訪一次，所以演算法效率為O(n+m)，n為點的個數，m為邊的個數。
12-3 最小生成樹
在無向圖有權重的連通圖中找尋可以連接所有點的邊且不形成循環，且這些邊的權重和最小，可以連通所有點且不形成循環(Cycle)，一定會形成樹，這樣的問題稱作最小生成樹(Minimum Spanning Tree)。
本節介紹Kruskal最小生成樹演算法與Prim最小生成樹演算法，Kruskal演算法由最小的邊出發，找出最小且不形成循環的邊，直到邊的個數為點的個數少1，就找到最小生成樹。Prim演算法由某個點出發，找出該點可以連出去最小權重邊，將此邊的另一個端點加入集合，並更新此邊的另一個端點可以連結其他點的邊是否有更小權重，可以連結的點更新成為更小權重。選取最小權重的邊，繼續更新該邊另一個端點可以連結其他點是否有更小權重，直到已經選取的邊的個數為點的個數少1，就找到最小生成樹。
12-3-1 使用Kruskal演算法找出最小生成樹
以下圖為例，進行Kruskal演算法的解說。
如何判斷選取的邊形成循環？這時需要使用集合的概念，剛開始每一個點都是一個集合，每個集合都只有一個元素，當加入最小生成樹的邊，邊的兩端點節點屬於同一個集合，就會形成循環，該邊不能是最小生成樹的邊。
Step1)將最小邊(3,5)加入最小生成樹，將點3與點5屬於不同的集合，且都是只有一個元素的集合，所以{3}與{5}進行聯集形成一個新集合{3,5}。
Step2)將最小邊(1,2)加入最小生成樹，將點1與點2屬於不同的集合，且都是只有一個元素的集合，所以{1}與{2}進行聯集形成另一個集合{1,2}，目前集合有{3,5}與{1,2}。
Step3)將最小邊(0,2)加入最小生成樹，將點0與點2屬於不同的集合，所以{0}與{1,2}進行聯集形成另一個集合{0,1,2}，目前集合有{3,5}與{0,1,2}。
Step4)將最小邊(0,1)加入最小生成樹，點0與點1都屬於集合{0,1,2}，如果加入邊(0,1)則會形成循環，所以不能加入邊(0,1)，目前集合有{3,5}與{0,1,2}。
Step5)將最小邊(2,3)加入最小生成樹，點2與點3屬於不同的集合，所以{0,1,2}與{3,5}進行聯集形成另一個集合{0,1,2,3,5}，目前集合有{0,1,2,3,5}。
Step6)將最小邊(3,4)加入最小生成樹，點3與點4屬於不同的集合，所以{0,1,2,3,5}與{4}進行聯集形成另一個集合{0,1,2,3,4,5}，目前集合有{0,1,2,3,4,5}，到此完成
最小生成樹。
12-3-1-Kruskal最小生成樹
給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，每個邊的權重為正整數，相同起點與終點的邊只有一個，使用Kruskal演算法找出最小生成樹的邊權重和。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個有向邊，接下來有m行，每個邊有三個數字，前兩個數字為邊的兩端點節點編號，最後一個數字為邊的權重，保證節點編號由0到(n-1)。
輸出說明
輸出最小生成樹的邊權重和。
範例輸入
範例輸出
26
Kruskal最小生成樹的程式實作想法
將所有邊的權重、起點與終點輸入到tuple，將此tuple依照權重由小到大排序，由小到大依序取出每一個邊。使用陣列parent記錄節點的上一層節點編號，有相同根節點的節點編號，表示同一個集合。若取出最小邊的兩端點，由陣列parent來判斷是否在同一個集合內，若有相同的根節點節點編號，表示同一個集合，加入此邊會形成循環，該邊不是最小生成樹的邊；若有不同的根節點節點編號，表示兩端點不在同一個集合內，加入此邊不會形成循環，該邊是最小生成樹的邊，接著更改陣列parent，集合元素個數越多者要放在上面，這樣由陣列parent往上找根節點才能在較少比較次數內完成，程式會有較好的效率。
(a)程式碼與解說
(12-3-1-Kruskal最小生成樹.py)
第1行：匯入heapq函式庫。
第2行：宣告pq為空串列。
第3行：宣告parent為串列，有101個元素，每一個元素都是0。
第4行：宣告num為串列，有101個元素，每一個元素都是1。
第5到8行：定義findParent函式，會不斷地往上一層找，直到最上層(a等於parent[a])為止，當a不等於parent[a]，則設定a為parent[a]，表示往上一層找，直到a等於parent[a]為止。最後回傳變數a。
第9到11行：使用input函數輸入兩個整數字串到變數n與m，使用int函式將整數字串變數n與m轉換成整數，再使用變數n與m參考到轉換後的整數，變數n為點的個數，變數m為邊的個數。
第12到17行：使用迴圈執行m次，每次輸入3個資料，前兩個數字為邊的兩個頂點到變數a與b ，最後一個數字為邊的權重到變數w(第13到16行)。將(w,a,b)加入到堆積pq，堆積pq會將最小w的(w,a,b)放在堆積pq的第一個元素。
第18到19行：使用迴圈變數i，由0到(n-1)，每次遞增1，設定parent[i]為i。
第20行：初始化變數i、result與numEdge為0。
第21到34行：使用迴圈變數i，由0到(m-1)，每次遞增1，且變數numEdge小於變數n，取出堆積pq的第一個元素到變數edge，找出edge[1]的最上層祖先節點編號儲存到變數a；找出edge[2]的最上層祖先節點編號儲存到變數b。
第25到33行：若a不等於b，表示將變數edge加入最小生成樹不會形成循環，將變數edge加入到最小生成樹，若num[a]大於num[b]，則元素多的集合要放在上面，設定parent[b]為a(第27行)，表示集合a在集合b上方，更新集合a個數(num[a])為集合a個數(num[a])加上集合b個數(num[b])(第28行)；否則(num[a]小於等於num[b])，元素多的集合要放在上面，設定parent[a]為b(第30行)，表示集合b在集合a上方，更新集合b個數(num[b])為集合b個數(num[b])加上集合a個數(num[a])(第31行)，陣列num儲存各集合的元素個數，根據陣列num數值越大越放在上面，這樣會使用findParent函式找尋最上層節點時，可以用較少的比較次數找到根節點，可以較快找到。
第32行：將edge[0]累加到變數result。
第33行：變數numEdge遞增1。
第34行：變數i遞增1。
第35到38行：若numEdge等於(n-1)，則輸出變數result，否則輸出「找不到最小生成樹」。
(b)程式執行結果
輸入以下測試資料。
6 9
0 1 6
0 2 5
0 3 11
0 4 16
1 2 3
2 3 7
2 5 10
3 4 9
3 5 2
執行結果如下。
26
(c)程式效率分析
執行第12到17行相當於堆積排序(Heap Sort)演算法，效率為O(m*log(m))，m為邊的個數。第21到34行的演算法效率，第21行的迴圈最多執行m次，迴圈內每次執行第23行與第34行的findParent函式，若每次集合進行合併時，節點個數多的在上方，則可以在較少的比較次數找到根節點，演算法效率為O(log(n))，整個演算法效率為O(m*log(n))，m為邊的個數，n為點的個數。整體演算法效率為O(m*log(m)+m*log(n))。
12-3-2 使用Prim演算法找出最小生成樹
以下圖為例，進行Prim演算法找出最小生成樹的概念解說。
程式實作--使用Prim演算法最小生成樹
給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，每個邊的權重為正整數，相同起點與終點的邊只有一個，使用Prim演算法找出最小生成樹的邊權重和。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個有向邊，接下來有m行，每個邊有三個數字，前兩個數字為邊的兩端點節點編號，最後一個數字為邊的權重，保證節點編號由0到(n-1)。
輸出說明
輸出最小生成樹的邊權重和。
範例輸入
範例輸出
26
Prim演算法的程式實作想法
任意取一個點當成起始節點，檢查起始節點可以連接的邊，將邊的權重與兩個端點加入堆積heap，邊的權重越小，越優先取出。取出權重最小的邊，若該邊的另一端節點未拜訪過，表示加入此邊不會形成循環，此邊為最小生成樹的邊，將另一個端點設定為已經拜訪過，接著將另一個端點可以連結出去的邊，是否造成其他節點有更小的權重，如果有，則將邊的權重與端點加入堆積heap，邊的權重越小，越優先取出。不斷取出未拜訪過且權重最小的邊，再考慮該邊的另一個端點可以連結出去的邊，直到堆積heap沒有元素為止。若最後邊的個數比節點數少一，表示找到最小生成樹。
(a)程式碼與解說
(12-3-2-Prim最小生成樹.py)
第1行：匯入heapq函式庫。
第2行：宣告pq為空串列。
第3行：宣告G為二維陣列。
第4行：宣告ans為空串列。
第5行：宣告v為串列，有101個元素，每一個元素都是0。
第6行：宣告dis為串列，有101個元素，每一個元素都是100000000。
第7到11行：宣告一個Edge類別，由3個元素描述一個邊，這個邊是具有方向性的，分別是s、t與w，s為邊的起點，t為邊的終點，w為邊的權重。
第12到14行：使用input函數輸入兩個整數字串到變數n與m，使用int函式將整數字串變數n與m轉換成整數，再使用變數n與m參考到轉換後的整數，變數n為點的個數，變數m為邊的個數。
第15到23行：使用迴圈執行m次，每次輸入3個資料，前兩個數字為邊的兩個頂點到變數a與b ，最後一個數字為邊的權重到變數w(第16到19行)。設定物件e1的s為a、物件e1的t為b、物件e1的w為w(第20行)。設定物件e2的s為b、物件e2的t為a、物件e2的w為w(第21行)。將e1加入到G[a]的最後，表示點a可以到點b (第22行)。將e2加入到G[b]的最後，表示點b可以到點a (第23行)。
第24行：設定變數start為0。
第25行：設定v[start]為1，表示節點編號start為已經拜訪。
第26行：設定dist[start]為0，表示產生最小生成樹過程中連結到節點編號start的邊的權重為0，不需要邊就可以連到。
第27行：設定numEdge與result為0。
第28到31行：找出圖形中所有可以從節點編號start可以連出去的邊到變數e(第28行)，當邊的權重(e.w)小於串列dist中目標點(e.t)的權重，表示找到更小權重的邊可以連結到目標點(e.t) (第29行)，更新串列dist中目標點(e.t)的權重為邊的權重(e.w) (第30行)，將(e.w, e.s, e.t)加入到串列pq，串列pq為heapq資料結構，e.w最小的會放在最上面(第31行)。
第32到43行：當串列pq的長度不等於0時，取出串列pq的最上面的元素到(w,s,t)，w為邊的權重，s為邊的起點，t為邊的終點。若v[t]等於0，表示節點t未拜訪，設定v[t]為1，表示設定節點t為已拜訪(第35行)，設定dist[t]為w(第36行)，將(s,t)加入到串列ans(第37行)，將變數w累加到變數result(第38行)，變數numEdge遞增1(第39行)。
第40到43行：更新節點t可以連出去的點， 找出圖形中所有可以從節點編號t可以連出去的邊到變數e(第40行)，當v[e.t]等於0，表示節點e.t未拜訪過，且邊的權重(e.w)小於串列dist中目標點(e.t)的權重(第41行)，表示找到更小權重的邊可以連結到目標點(e.t)，更新串列dist中目標點(e.t)的權重為邊的權重(e.w) (第42行)，將(e.w, e.s, e.t)加入到串列pq，串列pq為heapq資料結構，e.w最小的會放在最上面(第43行)。
第44到47行：若numEdge等於n-1，表示找到n-1個邊的最小生成樹，輸出變數result，變數result為最小生成樹的權重，否則顯示「找不到最小生成樹」。
(b)程式執行結果
輸入以下測試資料。
6 9
0 1 6
0 2 5
0 3 11
0 4 16
1 2 3
2 3 7
2 5 10
3 4 9
3 5 2
執行結果如下。
26
(c)程式效率分析
本程式花費最多計算在第32到43行，第32到43行的程式效率由第40行到43行決定，第40行的迴圈最多執行2*m次，因為每個點只拜訪過一次，無向圖中每個點連結出去的邊，最多為2*m個，m為邊的個數，第43行的堆積最多元素為n個，n為點的個數，每執行一次heappush效率為O(log(n))，第32到43行的演算法效率為O(m*log(n))，整體演算法效率為O(m*log(n))。
12-4 找出關節點
在無向連通圖中找尋關節點(articulation point)，關節點表示從圖中移除這個點會形成無法連通的圖，而若圖形表示交通網路圖，這些關節點就是不可以取代的點，一定要維持能順暢通過這些關節點，不然圖形上某些點就無法到達。
使用深度優先搜尋找出關節點
任何一張連通圖可以使用深度優先搜尋(DFS)進行搜尋，一定能走訪所有點，將深度優先搜尋走訪過的點與邊會形成深度優先搜尋樹。
以下圖為例，由點0開始進行深度優先搜尋，過程中依照點的編號由小到大依序走訪。
關節點的判斷演算法
(1)若點p是深度優先搜尋樹的根節點，因為深度優先搜尋樹的子樹之間不會相連，會相連就會屬於同一子樹，所以點p只要有兩個以上的子樹，則點p就是關節點(articulation point)。
(2)若點p不是深度優先搜尋樹的根節點，點p的每個子孫都有back edge可以連到點p的祖先(不含點p)，該點就不是關節點(articulation point)，若有一個子孫沒有back edge，該點就是關節點(articulation point)。
使用程式判斷圖形的邊為back edge
深度優先搜尋走訪過程中點的走訪順序可以標記在陣列v中，可以使用陣列v來判斷是否有back edge的存在，back edge表示在深度優先搜尋走訪順序較晚的點，有邊連結到走訪順序較早的點，這些邊被稱為back edge。
以上圖的點0開始，進行深度優先搜尋走訪，來判定節點是否有back edge，與節點是否是關節點，使用陣列v儲存深度優先搜尋走訪時，拜訪節點的順序，使用陣列up儲存每個節點的子孫可以拜訪的最高祖先。
12-4-1-找出關鍵的路口
給定最多100個節點以內的無向圖，每個節點名稱由字串組成，且節點名稱皆不相同，相同起點與終點的邊只有一個，請找出圖形中的關節點。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個無向邊，接下來有m行，每個邊有兩個節點名稱，兩個節點名稱為邊的兩端點節點名稱。
輸出說明
輸出關節點的個數與節點名稱。
範例輸入
範例輸出
1
Cx
找尋關節點的程式實作想法
利用深度優先搜尋演算法(DFS)傳入兩個參數p與i，p為i的雙親，深度優先搜尋過程中標記每個節點拜訪順序到陣列v，使用另一個陣列up，表示子孫可以經由back edge拜訪的最高祖先，遞迴呼叫下一層時，使用參數i與target，i為target的雙親，分成以下兩種情形。
(1)若p等於i，表示點i是根節點，則點i的子樹只要兩個以上就是關節點。
(2)若點i不是根節點，若target等於p表示回到祖父母節點，不是back edge，否則target不等於p，若v[target]顯示已經拜訪過且up[target]小於v[i]，則邊(i,target)為back edge，若點i有一個子孫沒有back edge，也就是找到一個子孫節點target，up[target]大於等於v[i]，則點i就是關節點。
(a)程式碼與解說
(12-4-1-找出關鍵的路口.py)
第1行：宣告G為二維陣列
第2行：宣告City為空字典。
第3到5行：宣告v、up與ar為整數陣列，都有100個元素，請每一個元素為0。
第6到7行：宣告t與cnt為整數變數，初始化為0。
第8到11行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定City[p]所對應的值為字典City的長度(第9到10行)。回傳字典City以p為鍵值的對應值(第11行)。
第12到32行：定義dfs函式進行深度優先搜尋，輸入參數p表示上一個節點編號，與參數i表示目前節點編號。
第13行：設定變數t與cnt為全域變數。
第14到16行：變數t先遞增1，再將變數t儲存到v[i]與up[i]。
第17行：設定變數child為0。
第18行：設定變數ap為False。
第19到29行：使用迴圈讀取節點編號i的所有可以連結出去的邊到變數e，設定變數target為e.t。若變數target不等於變數p，表示不是走回祖父母的節點p。若v[target]大於0，表示有拜訪過，設定up[i]為up[i]與v[target]的最小值，儲存已經拜訪的最高祖先到up[i]；否則，表示v[target]等於0，表示點target未拜訪過，變數child遞增1，使用遞迴呼叫dfs函式，使用變數i與變數target為參數，設定up[i]為up[i]與up[target]的最小值。若up[target]大於等於v[i]，表示點i有子樹沒有back edge，設定變數ap為True。
第30到32行：若變數i等於變數p，表示點i是根節點，若child大於1，表示子樹個數大於1，或若變數i不等於變數p，表示點i不是根節點，且變數ap等於true，則設定ar[i]為1，變數cnt遞增1。
第33到36行：宣告一個Edge類別，由2個元素描述一個邊，分別是s與t ，s為邊的起點，t為邊的終點。
第37到39行：使用input函式輸入兩個整數字串到變數n與m，接著使用int函式將整數字串轉換成整數，變數n為點的個數，變數m為邊的個數。
第40到47行：使用迴圈執行m次，每次輸入2個資料，表示邊的兩個節點名稱到變數a與b，使用函式getCityIndex將節點名稱a轉換成編號，變數a參考到此編號，使用函式getCityIndex將節點名稱b轉換成編號，變數b參考到此編號(第41到43行)。設定物件e1的s為a、物件e1的t為b (第44行)，設定物件e2的s為b、物件e1的t為a (第45行)。將e1加入到G[a]的最後，表示點a可以到點b (第46行)。將e2加入到G[b]的最後，表示點b可以到點a (第47行)。
第48行：使用dfs函式進行深度優先搜尋，以0與0為參數。
第49行：輸出變數cnt的值。
第50到52行：迴圈變數i，由0到(n-1)，每次遞增1，若ar[i]等於1，則輸出list(City.keys())[i]，也就是節點編號i的節點名稱。
(b)程式執行結果
輸入以下測試資料。
6 8
Ax Bx
Ax Cx
Ax Dx
Ax Ex
Bx Cx
Cx Dx
Cx Fx
Dx Ex
執行結果如下。
1
Cx
(c)程式效率分析
執行getCityIndex函式是本程式花最多執行時間的區域，執行第9行的檢查p是否為G的鍵值需要O(n)時間，每個邊都要執行兩次getCityIndex函式，演算法效率為O(n*m)，n為點的個數，m為邊的個數。第12到32行深度優先搜尋演算法，每個點都要拜訪，與點連出去的邊都需要考慮，演算法效率為O(n+m)。整體演算法效率為O(n*m)。如果沒有將節點名稱轉換成編號，演算法效率為O(n+m)。
Page updated
Google Sites
Report abuse