【正文】 // 和 low。 //從根 x開(kāi)始 delete [ ] dfn。 i++ ) { dfn[i] = low[i] = 0。 //dfn是深度優(yōu)先數(shù) , low是最小祖先訪問(wèn)順序號(hào) for ( int i = 0。 // num是訪問(wèn)計(jì)數(shù)器 static int * dfn = new int[NumVertices]。 low[u] = min { dfn[u], min{ low[w] | w 是 u 的一個(gè)子女 }, min{ dfn[x] | (u, x) 是一條回邊 } } ? u 是關(guān)節(jié)點(diǎn)的充要條件是： ? u 是具有兩個(gè)以上子女的生成樹(shù)的根 ? u 不是根，但它有一個(gè)子女 w，使得 low[w] ? dfn[u] ? 這時(shí) w 及其子孫不存在指向頂點(diǎn) u的祖先的回邊。 ? 其它頂點(diǎn) u 是 關(guān)節(jié)點(diǎn) 的充要條件是 它至少有一個(gè)子女 w, 從 w 出發(fā) , 不能通過(guò) w、 w 的子孫及一條回邊所組成的路徑到達(dá) u 的祖先 。 ? 如果在深度優(yōu)先生成樹(shù)中， 頂點(diǎn) u 是 頂點(diǎn) v 的祖先 , 則有 dfn[u] dfn[v]。 ? 在一個(gè)無(wú)向連通圖 G中 , 重連通分量可以利用深度優(yōu)先生成樹(shù)找到。 ? 在重連通圖上 , 任何一對(duì)頂點(diǎn)之間至少存在有 兩條路徑 , 在刪去某個(gè)頂點(diǎn)及與該頂點(diǎn)相關(guān)聯(lián) 的邊時(shí) , 也不破壞圖的連通性。 //釋放 visited } 重連通分量 (Biconnected Component) ? 在無(wú)向連通圖 G中，當(dāng)且僅當(dāng)刪去 G中的頂點(diǎn) v及 所有依附于 v的所有邊 后，可將圖分割成 兩個(gè)或兩個(gè)以上的連通分量，則稱頂點(diǎn) v為 關(guān) 節(jié)點(diǎn) 。 //從未訪問(wèn)的頂點(diǎn)出發(fā)訪問(wèn) OutputNewComponent ( )。 i NumVertices。 i++ ) visited[i] = 0。 for ( int i = 0。 ?對(duì)于非連通的無(wú)向圖，所有連通分量的生成樹(shù)組成了非連通圖的生成森林。 ? 若從無(wú)向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，可求得無(wú)向圖的所有連通分量。 ?如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問(wèn)過(guò)的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的 n 個(gè)元素，總的時(shí)間代價(jià)為 O(n2)。 //取頂點(diǎn) v 的排在 w 后面的下一鄰接頂點(diǎn) } //重復(fù)檢測(cè) v 的所有鄰接頂點(diǎn) } //外層循環(huán)，判隊(duì)列空否 delete [ ] visited。 (w)。 //取頂點(diǎn) v 的 第一個(gè)鄰接頂點(diǎn) w while ( w != 1 ) { //若鄰接頂點(diǎn) w 存在 if ( !visited[w] ) { //若該鄰接頂點(diǎn)未訪問(wèn)過(guò) cout GetValue (w) ? ?。 //訪問(wèn) v, 進(jìn)隊(duì)列 while ( ! ( ) ) { //隊(duì)空搜索結(jié)束 v = ( )。 Queueint q。 39。 i++ ) visited[i] = 0。 for ( int i = 0。 ? 為避免重復(fù)訪問(wèn)，需要一個(gè)輔助數(shù)組 visited [ ]，給被訪問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。再?gòu)倪@些訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪問(wèn)它們的所有還未被訪問(wèn)過(guò)的鄰接頂點(diǎn)， … 如此做下去，直到圖中所有頂點(diǎn)都被訪問(wèn)到為止。 ? 如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為 O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為 O(n2)。由于總共有 2e 個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為 O(e)。 //取頂點(diǎn) v 的排在 w 后面的下一個(gè)鄰接頂點(diǎn) } } 算法分析 ? 圖中有 n 個(gè)頂點(diǎn)， e 條邊。 //取 v 的第一個(gè)鄰接頂點(diǎn) w while ( w != 1 ) { //若鄰接頂點(diǎn) w 存在 if ( !visited[w] ) DFS ( w, visited )。 //訪問(wèn)頂點(diǎn) v visited[v] = 1。 delete [ ] visited。 i++ ) visited [i] = 0。 for ( int i = 0。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。 ? 為了避免重復(fù)訪問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組 visited [ ]，它的初始狀態(tài)為 0，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn) i 被訪問(wèn)，就立即讓 visited [i] 為 1，防止它被多次訪問(wèn)。數(shù)據(jù)結(jié)構(gòu)與算法 圖的遍歷與連通性 ? 從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷 ( Graph Traversal )。 ? 圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。 深度優(yōu)先搜索 DFS ( Depth First Search ) ?深度優(yōu)先搜索的示例 ? DFS 在訪問(wèn)圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn) w1；再?gòu)? w1 出發(fā)，訪問(wèn)與 w1鄰 接但還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn) w2；然后再?gòu)? w2 出發(fā)，進(jìn)行類(lèi)似的訪問(wèn)， … ? 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn) u 為止。如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類(lèi)似的訪問(wèn)；如果沒(méi)有，就再退回一步進(jìn)行搜索。 圖的深度優(yōu)先搜索算法 templateclass NameType, class DistType void Graph NameType, DistType :: DFS ( ) { int * visited = new int [NumVertices]。 i NumVertices。 //訪問(wèn)標(biāo)記數(shù)組 visited 初始化 DFS (0, visited )。 //釋放 visited } templateclass NameType, class DistType void GraphNameType, DistType :: DFS ( const int v, int visited [ ] ) { cout GetValue (v) ? ?。 //頂點(diǎn) v 作訪問(wèn)標(biāo)記 int w = GetFirstNeighbor (v)。 //若 頂點(diǎn) w 未訪問(wèn)過(guò) , 遞歸訪問(wèn)頂點(diǎn) w w = GetNextNeighbor ( v, w )。 ? 如果用鄰接表表示圖，沿 Firstout ? link 鏈可以找到某個(gè)頂點(diǎn) v 的所有鄰接頂點(diǎn) w。而且對(duì)所有頂點(diǎn)遞歸訪問(wèn) 1次，所以遍歷圖的時(shí)間復(fù)雜性為 O(n+e)。 廣度優(yōu)先搜索 BFS ( Breadth First Search ) ?廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹(shù) ? 使用廣度優(yōu)先搜索在訪問(wèn)了起始頂點(diǎn) v 之后，由 v 出發(fā)，依次訪問(wèn) v 的各個(gè)未曾被訪問(wèn)過(guò)的鄰接頂點(diǎn) w1, w2, …, wt，然后再順序訪問(wèn) w1, w2, …, wt 的所有還未被訪問(wèn)過(guò)的鄰接頂點(diǎn)。 ? 廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。 ? 為了實(shí)現(xiàn)逐層訪問(wèn)，算法中使用了一個(gè)隊(duì)列，以記憶正在訪問(wèn)的這一層和上一層的頂點(diǎn)，以便于向下一層訪問(wèn)。 圖的廣度優(yōu)先搜索算法 templateclass NameType, class DistType void Graph NameType, DistType :: BFS ( int v ) { int * visited = new int[NumVertices]。 i NumVertices。 //visited 初始化 cout GetValue (v) 39。 visited[v] = 1。 (v)。 //不空 , 出隊(duì)列 int w = GetFirstNeighbor (v)。 //訪問(wèn) visited[w] = 1。 //進(jìn)隊(duì) } w = GetNextNeighbor (v, w)。 } 算法分析 ?如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + … + d n1 = O(e)，其中的 di 是頂點(diǎn) i 的度。 連通分量 (Connected ponent) ? 當(dāng)無(wú)向圖為非連通圖時(shí)，從圖中某一頂點(diǎn)出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn)，只能訪問(wèn)到該頂點(diǎn)所在的最大連通子圖 (連通分量 )的所有頂點(diǎn)。 ? 在算法中，需要對(duì)圖的每一個(gè)頂點(diǎn)進(jìn)行檢測(cè)：若已被訪問(wèn)過(guò)，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問(wèn)，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。 確定連通分量的算法 templateclass NameType, class DistType void GraphNameType, DistType :: Components ( ) { int *visited = new int[NumVertices]。 i NumVertices。 //visited 初始化 for ( i = 0。 i++ ) if ( !visited[i] ) { //檢測(cè)所有頂點(diǎn)是否訪問(wèn)過(guò) DFS ( i, visited )。 //輸出一個(gè)連通分量 } delete [ ] visited。 ? 沒(méi)有 關(guān)節(jié)點(diǎn) 的連通圖叫做重連通圖。 ? 一個(gè)連通圖 G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量。 ? dfn 頂點(diǎn)的深度優(yōu)先數(shù)，標(biāo)明進(jìn)行深度優(yōu)先搜索時(shí)各頂點(diǎn)訪問(wèn)的次序。 ? 深度優(yōu)先生成樹(shù)的根是 關(guān)節(jié)點(diǎn) 的充要條件是 它至少有兩個(gè)子女 。 ? 在圖 G的每一個(gè)頂點(diǎn)上定義一個(gè) low 值 ，low[u] 是從 u 或 u 的子孫 出發(fā)通過(guò) 回邊 可以到達(dá)的 最低深度優(yōu)先數(shù) 。 計(jì)算 dfn與 low的算法 (1) templateclass NameType, class DistType void GraphNameType, DistType :: DfnLow ( const int x ) { //公有函數(shù)：從頂點(diǎn) x開(kāi)始深度優(yōu)先搜索 int num = 1。 static int * low = new int[NumVertices]。 i NumVertices。 } //給予訪問(wèn)計(jì)數(shù)器 num及 dfn[u], low[u]初值 DfnLow ( x, 1 )。 delete [ ] low。在產(chǎn)生的生成樹(shù)中 v 是 u 的雙親。 int w = GetFirstNeighbor (u)。 //從 w遞歸深度優(yōu)先搜索 low[u] = min2 ( low[u], low[w] )。 //根據(jù)回邊另一頂點(diǎn) w調(diào)整 low[u] w = GetNextNeighbor ( u, w )。首先 , 根據(jù) DfnLow (w, u)的返回 , 計(jì)算 low[w]。 在算法中利用一個(gè)棧， 在遇到一條邊時(shí)保存它。 當(dāng) n 1 時(shí)輸出重連通分量 （ 1） templateclass NameType, class DistType void GraphNameType, DistType :