【文章內(nèi)容簡介】 需要時還可設置一個存放與該邊相關(guān)的權(quán)值的域 cost。 ? 頂點結(jié)點的結(jié)構(gòu) ? 頂點信息的結(jié)點表以順序表方式組織 , 每一個頂點結(jié)點有兩個數(shù)據(jù)成員：其中， data 存放與該頂點相關(guān)的信息， Firstout 是指示第一條依附該頂點的邊的指針。 ? 在鄰接多重表中 , 所有依附同一個頂點的邊都鏈接在同一個單鏈表中。 data Firstout 14641 mark vtx1 vtx2 path1 path2 ? ? ? ? 0 1 0 2 1 3 e1 e2 e3 data Fout A B C D 0 1 2 3 e1 e2 e3 A B C D ? 從頂點 i 出發(fā) , 可以循鏈找到所有依附于該頂點的邊，也可以找到它的所有鄰接頂點。 鄰接多重表的結(jié)構(gòu) 14642 ? 有向圖的情形 ? 在用鄰接表表示有向圖時 , 有時需要同時使用鄰接表和逆鄰接表。用有向圖的鄰接多重表(十字鏈表 )可把兩個表結(jié)合起來表示。 ? 邊結(jié)點的結(jié)構(gòu) ? 其中， mark是處理標記； vertex1和 vertex2指明該有向邊始頂點和終頂點的位置。 path1是指向 始頂點與該邊相同 的下一條邊的指針；path2是指向 終頂點與該邊相同 的下一條邊的指針。需要時還可有權(quán)值域 cost。 mark vertex1 vertex2 path1 path2 14643 ? 頂點結(jié)點的結(jié)構(gòu) ? 每個頂點有一個結(jié)點，它相當于出邊表和入邊表的表頭結(jié)點：其中，數(shù)據(jù)成員 data存放與該頂點相關(guān)的信息，指針 Firstin 指示以該頂點為始頂點的出邊表的第一條邊， Firstout 指示以該頂點為終頂點的入邊表的第一條邊。 data Firstin Firstout 14644 mark vtx1 vtx2 path1 path2 ? ? ? ? ? ? ? ? ? ? 0 1 0 3 1 2 2 3 3 4 4 0 e1 e2 e3 e4 e5 e6 data Fin Fout A B C D E 0 1 2 3 4 e1 e2 e3 e4 e5 e6 A B C D E 鄰接多重表的結(jié)構(gòu) 14645 圖的遍歷與連通性 ? 從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷 (Graph Traversal)。 ? 圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。 ? 為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數(shù)組 visited [ ]。 14646 ? 輔助數(shù)組 visited[ ]的初始狀態(tài)為 0, 在圖的遍歷過程中 , 一旦某一個頂點 i 被訪問 , 就立即讓 visited[i]為 1, 防止它被多次訪問。 ? 圖的遍歷的分類 : ? 深度優(yōu)先搜索 DFS (Depth First Search) ? 廣度優(yōu)先搜索 BFS (Breadth First Search) 14647 深度優(yōu)先搜索 DFS (Depth First Search) ? 深度優(yōu)先搜索的示例 A C D E G B F I H A C D E G B F I H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 前進 回退 深度優(yōu)先搜索過程 深度優(yōu)先生成樹 14648 ? DFS 在訪問圖中某一 起始頂點 v 后 , 由 v 出發(fā) , 訪問它的任一 鄰接頂點 w1。 再從 w1 出發(fā) , 訪問與 w1鄰 接 但還 沒有訪問過的頂點 w2。 然后再從 w2 出發(fā) , 進行類似的訪問 , … 如此進行下去 , 直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。 接著 , 退回一步 , 退到前一次剛訪問過的頂點 , 看是否還有其它沒有被訪問的鄰接頂點。 如果有 , 則訪問此頂點 , 之后再從此頂點出發(fā) , 進行與前述類似的訪問 。 如果沒有 , 就再退回一步進行搜索。重復上述過程 , 直到連通圖中所有頂點都被訪問過為止。 14649 圖的深度優(yōu)先搜索算法 templateclass T, class E void DFS (GraphT, Eamp。 G, const Tamp。 v) { //從頂點 v出發(fā)對圖 G進行深度優(yōu)先遍歷的主過程 int i, loc, n = ()。 //頂點個數(shù) bool *visited = new bool[n]。 //創(chuàng)建輔助數(shù)組 for (i = 0。 i n。 i++) visited [i] = false。 //輔助數(shù)組 visited初始化 loc = (v)。 DFS (G, loc, visited)。 //從頂點 0開始深度優(yōu)先搜索 delete [] visited。 //釋放 visited }。 14650 templateclass T, class E void DFS (GraphT, Eamp。 G, int v, bool visited[]) { cout (v) 39。 39。 //訪問頂點 v visited[v] = true。 //作訪問標記 int w = (v)。 //第一個鄰接頂點 while (w != 1) { //若鄰接頂點 w存在 if ( !visited[w] ) DFS(G, w, visited)。 //若 w未訪問過 , 遞歸訪問頂點 w w = (v, w)。 //下一個鄰接頂點 } }。 14651 廣度優(yōu)先搜索 BFS (Breadth First Search) ? 廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹 A C D E G B F I H A C D E G B F H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 I 14652 ? BFS在訪問了起始頂點 v 之后 , 由 v 出發(fā) , 依次訪問 v 的各個未被訪問過的鄰接頂點 w1, w2, …, wt, 然后再順序訪問 w1, w2, …, wt 的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點， … 如此做下去，直到圖中所有頂點都被訪問到為止。 ? 廣度優(yōu)先搜索是一種分層的搜索過程 , 每向前走一步可能訪問一批頂點 , 不像深度優(yōu)先搜索那樣有往回退的情況。因此 , 廣度優(yōu)先搜索不是一個遞歸的過程。 14653 ? 為了實現(xiàn)逐層訪問 , 算法中使用了一個隊列 , 以記憶正在訪問的這一層和上一層的頂點 , 以便于向下一層訪問。 ? 為避免重復訪問 , 需要一個輔助數(shù)組 visited [ ]，給被訪問過的頂點加標記。 template class T, class E void BFS (GraphT, Eamp。 G, const Tamp。 v) { int i, w, n = ()。 //圖中頂點個數(shù) 圖的廣度優(yōu)先搜索算法 14654 bool *visited = new bool[n]。 for (i = 0。 i n。 i++) visited[i] = false。 int loc = (v)。 //取頂點號 cout (loc) 39。 39。 //訪問頂點 v visited[loc] = true。 //做已訪問標記 Queueint Q。 (loc)。 //頂點進隊列 , 實現(xiàn)分層訪問 while (!() ) { //循環(huán) , 訪問所有結(jié)點 (loc)。 w = (loc)。 //第一個鄰接頂點 while (w != 1) { //若鄰接頂點 w存在 if (!visited[w]) { //若未訪問過 14655 cout (w) 39。 39。 //訪問 visited[w] = true。 (w)。 //頂點 w進隊列 } w = (loc, w)。 //找頂點 loc的下一個鄰接頂點 } } //外層循環(huán)，判隊列空否 delete [] visited。 }。 14656 連通分量 (Connected ponent) ? 當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在最大連通子圖 （連通分量）的 所有頂點。 ? 若從無向圖每一連通分量中的一個頂點出發(fā)進行遍歷 , 可求得無向圖的所有連通分量。 ? 例如，對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。 14657 A C D E B F G O I H J N M L K 非連通無向圖 A H K C D E I B F O G J N M L 非連通圖的連通分量 14664 重連通分量 (Biconnected Component) ? 在無向連通圖 G中 , 當且僅當刪去 G中的頂點 v及所有依附于 v的所有邊后 , 可將圖分割成兩個或兩個以上的連通分量，則稱頂點 v為 關(guān)節(jié)點 。 ? 沒有 關(guān)節(jié)點 的連通圖叫做重連通圖。 ? 在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時 , 也不破壞圖的連通性。 14665 ? 一個連通圖 G如果不是重連通圖，那么它可以包括幾個重連通分量。 ? 在一個無向連通圖 G中 , 重連通分量可以利用深度優(yōu)先生成樹找到。 ? 在圖中各 頂點旁標明的深度優(yōu)先數(shù) , 給出進行深度優(yōu)先搜索時各頂點訪問的次序。 ? 深度優(yōu)先生成樹的 根是 關(guān)節(jié)點 的充要條件是它至少有兩個子女 。 ? 其它頂點 u 是 關(guān)節(jié)點 的充要條件是它至少有一個子女 w, 從 w 出發(fā) , 不能通過 w、 w 的子孫及一條回邊所組成的路徑到達 u 的祖先 。 14666 A B C D E F G H I J A B C D E F G H J A B C D E F G H J I I 1 2 3 4 5 6 7 8 9 10 根有兩 個子女 關(guān)節(jié)點 關(guān)節(jié)點 關(guān)節(jié)點 14667 最小生成樹 ( minimum cost spanning tree ) ? 使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。 ? 按照生成樹的定義， n 個頂點的連通網(wǎng)絡的生成樹有 n 個頂點、 n1條邊。 ? 構(gòu)造最小生成樹 假設有一個網(wǎng)絡，用以表示 n 個城市之間架設通信線路，邊上的權(quán)值代表架設通信線路的成本。如何架設才能使線路架設的成本達到最??？ 14668 ? 構(gòu)造最小生成樹的準則 ? 必須使用且僅使用該網(wǎng)絡中的 n1 條邊來聯(lián)結(jié)網(wǎng)絡中的 n 個頂點； ? 不能使用產(chǎn)生回路的邊； ? 各邊上的權(quán)值的總和達到最小。 北京 天津 南京 上海 廣州 西安 成都 昆明 武漢 34 7 6 41 58 31 24 19 25 38 22 22 19 31 39 44 50 14669