前言
在之前的推文中，我們了解了什么是圖，以及一些圖的DFS和BFS的基本操作，這一期本小編將繼續為大家介紹一些關于圖的基本算法，一起看下吧。
NO．1關節點和雙聯通域
在一個無向圖G中，若將某個節點v去除之后后G所包含的連通域增多，則v稱作切割節點（cut vertex或關節點（articulation point）。如果一個圖不含任何關節點則稱之為雙連通圖，最典型的就是完全圖。任一無向圖都可視作由若干個極大的雙連 通子圖組合而成，這樣的每一子圖都稱作原圖的一個雙連通域（bi－connected component）。例如下圖中的節點3和5就是關節點。
較之其它頂點，關節點更為重要。在網絡系統中它們對應于網關，決定子網之間能否連通。在航空系統中，某些機場的損壞，將 同時切斷其它機場之間的交通。故在資源總量有限的前提下， 找出關節點并重點予以保障，是提高系統整體穩定性和魯棒性的基本策略。接下來就讓我們來看下求關節點的算法吧。
NO．2關節點算法
遇事不決先暴力，按照暴力來解決：首先，通過BFS或DFS搜索統計出圖G所含連通域 的數目；然后逐一枚舉每個頂點v，暫時將其從圖G中刪去，并再次通過搜索統計出圖G｛v｝所含 連通域的數目。于是，頂點v是關節點，當且僅當圖G｛v｝包含的連通域多于圖G。這一算法需執行n趟搜索，耗時O（n（n ＋ e）），等它算出來黃花菜都涼了。
那我們先分析下，首先在DFS樹上面，葉節點不可能是關節點，因為將葉節點刪去后不會影響樹的連通性。另外，如果根節點有兩個及兩個以上的分支，則根節點一定是關節點，因為DFS會將此節點以下的所有點加入到分支中，如果有多個分支則這些分支是不相互連通的。
現在考慮內部節點。若節點C的移除導致其某一棵（比如以D為根的）真子樹與其真祖先（比如A）之間無法連通，則C必為關節點。反之，若C的所有真子樹都能（如以E為根的子 樹那樣）與C的某一真祖先連通，則C就不可能是關節點。那么只要 在DFS搜索過程記錄并更新各頂點v所能（經由后向邊）連通的最高祖先（highest connected ancestor， HCA）hca［v］，即可及時認定關節點，并報告對應的雙連通域。
思路出來了，那就是代碼實現了
＃include
