假若在刪去頂點v以及和v相關(guān)聯(lián)的各邊之后,將圖的一個連通分量分割成兩個或兩個以上的連接分量,則稱頂點v為該圖的一個關(guān)節(jié)點。一個沒有關(guān)節(jié)點的連通圖稱為重連通圖。在重連通圖上,任意一對頂點之間至少存在兩條路徑,則在刪去某個頂點以及依附于該頂點的各邊時也不會破壞圖的連通性。
利用深度優(yōu)先搜索可以求出圖的關(guān)節(jié)點,并由此可以判斷圖是否是重連通的。
通過修改深度優(yōu)先搜索遍歷的算法便可以得到求關(guān)節(jié)點的算法,其算法描述如下:
在本題中,讀入一個無向圖的鄰接矩陣(即數(shù)組表示),建立無向圖并按照以上描述中的算法求出所有的關(guān)節(jié)點,并輸出這些關(guān)節(jié)點。