【正文】 中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在 T中不同的連通分量上，則將此邊加入到 T中；否則，舍去此邊，選取下一條代價(jià)最小的邊 （ 3） 依此類(lèi)推，直至 T中所有頂點(diǎn)都在同一連通分量上為止 第七章 圖 生成樹(shù) 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 第七章 圖 生成樹(shù) 算法描述： 構(gòu)造非連通圖 ST=( V,{ } )。 2. 如何判別 V的鄰接點(diǎn)是否被訪問(wèn)？ 第七章 圖 圖的遍歷 開(kāi)始 訪問(wèn)標(biāo)志初始化 i=1 Vi訪問(wèn)過(guò) DFS i=i+1 i==Vexnums 結(jié)束 N N Y Y 深度優(yōu)先遍歷算法 開(kāi)始 訪問(wèn) V,置 標(biāo)志 求 V鄰接點(diǎn) 有鄰接點(diǎn) w 求下一鄰接點(diǎn) W訪問(wèn)過(guò) 結(jié)束 N Y N Y DFS w?V0 第七章 圖 圖的遍歷 a b c h d e k f g 8 1 2 3 4 5 6 7 0 F F F F F F F F F 0 1 2 3 4 5 6 7 8 T T T T T T T T T a c h d k f e b g 訪問(wèn)標(biāo)志 : 訪問(wèn)次序 : 例如 : a c h d k f e 第七章 圖 圖的遍歷 廣度優(yōu)先搜索 思想 （ 1）從圖的某一頂點(diǎn) V0出發(fā)，訪問(wèn)該頂點(diǎn)后，依次訪問(wèn) V0的各個(gè) 未被訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到 （ 2） 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止 第七章 圖 圖的遍歷 V1 V2 V4 V5 V3 V7 V6 V8 例 1 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 第七章 圖 圖的遍歷 例 2 V1 V2 V4 V5 V3 V7 V6 V8 例 3 V1 V2 V4 V5 V3 V7 V6 V8 例 2： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 例 3： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 V1 V2 V4 V5 V3 V7 V6 V8 例 4 例 4： V1? V2 ?V3 ? V4 ?V6 ?V7 ?V8 ?V5 第七章 圖 圖的遍歷 廣度優(yōu)先遍歷算法 思想：借助隊(duì)列 開(kāi)始 標(biāo)志數(shù)組初始化 Vi=1 Vi訪問(wèn)過(guò) BFS Vi=Vi+1 Vi==Vexnums 結(jié)束 N N Y Y 第七章 圖 圖的遍歷 開(kāi)始 訪問(wèn) V0,置 標(biāo)志 求 V鄰接點(diǎn) w w存在嗎 V下一鄰接點(diǎn) ?w w訪問(wèn)過(guò) 結(jié)束 N Y N Y BFS 初始化隊(duì)列 V0入隊(duì) 隊(duì)列空嗎 隊(duì)頭 V出隊(duì) 訪問(wèn) w,置 標(biāo)志 w入隊(duì) N Y 第七章 圖 生成樹(shù) 生成樹(shù) 最小生成樹(shù) 構(gòu)造最小生成樹(shù) 第七章 圖 生成樹(shù) 生成樹(shù) 定義：所有（ n個(gè)）頂點(diǎn)均由邊（ n1個(gè)）連接在一起，但不存在回路的圖 深度優(yōu)先生成樹(shù)：由深度優(yōu)先遍歷得到的生成樹(shù) 廣度優(yōu)先生成樹(shù)：由廣度優(yōu)先遍歷得到的生成樹(shù) 生成森林：非連通圖每個(gè)連通分量的生成樹(shù)一起組成非連通圖 第七章 圖 生成樹(shù) 說(shuō)明 一個(gè)圖可以有許多棵不同的生成樹(shù) 所有生成樹(shù)具有以下共同特點(diǎn)： ?生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同 ?生成樹(shù)是圖的極小連通子圖 ?一個(gè)有 n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有 n1條邊 ?生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的 ?在生成樹(shù)中再加一條邊必然形成回路 含 n個(gè)頂點(diǎn) n1條邊的圖不一定是生成樹(shù) 第七章 圖 生成樹(shù) V5 V1 V2 V4 V3 V7 V6 V8 例 深度： V1? V2 ?V4 ? V8 ?V5?V3 ?V6 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 深度優(yōu)先生成樹(shù) V1 V2 V4 V5 V3 V7 V6 V8 廣度優(yōu)先生成樹(shù) 廣度： V1? V2 ?V3 ? V4 ?V5?V6 ?V7 ?V8 V5 V1 V2 V4 V3 V7 V6 V8 V5 V1 V2 V4 V3 V7 V6 V8 第七章 圖 生成樹(shù) 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度優(yōu)先生成森林 第七章 圖 生成樹(shù) 最小生成樹(shù) 問(wèn)題提出 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n1條線路， 如何在最節(jié)省經(jīng)費(fèi)的前提下建立 這個(gè) 通訊網(wǎng) ？ 頂點(diǎn) ——表示城市 權(quán) ——城市間建立通信線路所需花費(fèi)代價(jià) 最?。ù鷥r(jià)）生成樹(shù) ：希望找到一棵生成樹(shù)，它的每條邊上的權(quán)值之和即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小 第七章 圖 生成樹(shù) 問(wèn)題分析 n個(gè)城市間，最多可設(shè)置 n(n1)/2條線路 n個(gè)城市間建立通信網(wǎng)，只需 n1條線路 該問(wèn)題等價(jià)于 ：構(gòu)造網(wǎng)的一棵 最小生成樹(shù) ，即： 在 e條帶權(quán)的邊中選取 n1條邊 （不構(gòu)成回路），使 “ 權(quán)值之和 ” 為最小 。 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 第七章 圖 圖的遍歷 思想： （ 1）從圖的某一頂點(diǎn) V0出發(fā)，訪問(wèn)該頂點(diǎn)；然后依次從 V0的 未被訪問(wèn)的鄰接 點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和 V0相通的頂點(diǎn)都被訪問(wèn)到； （ 2） 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè) 未被訪問(wèn)的頂點(diǎn) 作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中 所有頂點(diǎn) 都被訪問(wèn)為止 深度優(yōu)先遍歷 第七章 圖 圖的遍歷 V1 V2 V4 V5 V3 V7 V6 V8 例 1 深度遍歷： V1? V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7 第七章 圖 圖的遍歷 例 2 V1 V2 V4 V5 V3 V7 V6 V8 例 3 V1 V2 V4 V5 V3 V7 V6 V8 例 2： V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 例 3： V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 例 4 例 4： V1? V2 ?V4 ? V8 ?V3 ?V6 ?V7 ?V5 第七章 圖 圖的遍歷 從上面例可見(jiàn) : 1. 從深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷 。 }AMLGraph。 Typedef struct { //頂點(diǎn)表 VexBox adjlist[MAX_VERTEX_NUM]。 EBox *firstedge。 }EBox。 struct EBox *ilink, *jlink。 typedef struct ArcBox //弧結(jié)點(diǎn) { VisitIf mark。 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 建立有向圖十字鏈表算法 思想： （ 1）初始化表頭向量、數(shù)據(jù)、指針 （ 2）輸入一條弧，確定在 G中位置，申請(qǐng)結(jié)點(diǎn)空間，賦值 （ 3）插入到十字鏈表中 （ 4）若 InInfo=1，輸入其信息 （ 5）重復(fù)（ 2）至（ 4），直到所有弧輸入完為止。//表頭向量 int vexnum, arum。 }VexNode。 Typedef struct VexNode //頂點(diǎn)結(jié)點(diǎn) { VertexType data。 infoType *info。 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 有向圖的十字鏈表存儲(chǔ)表示 十字鏈表結(jié)點(diǎn)結(jié)構(gòu) tailvex headvex hlink tlink info 弧結(jié)點(diǎn) data firstin firstout 頂點(diǎn)結(jié)點(diǎn) 弧尾位置 弧頭位置 弧尾相同的下一條弧指針 弧相關(guān)信息的指針 弧頭相同的下一條弧指針 指向該頂點(diǎn)第一條入弧 指向該頂點(diǎn)第一條出弧 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 例 v2 v4 v1 v3 0 2 0 1 2 3 2 0 3 2 3 1 3 0 ^ v1 v2 v3 v4 0 1 2 3 ^ ^ ^ ^ ^ ^ ^ 第七章 圖 圖的存儲(chǔ)結(jié)構(gòu) 有向圖十字鏈表存儲(chǔ)表示 define MAX_VERTEX_NUM 20 typedef struct ArcBox //弧結(jié)點(diǎn) { int tailvex,hesdvex。 鄰接表的 優(yōu)缺點(diǎn) 空間較??； 無(wú)向圖 容易求 各頂點(diǎn)的 度 ；表中結(jié)點(diǎn)個(gè)數(shù)是邊的兩倍； 有向圖 容易求 頂點(diǎn)的 出度 ； 不容易求 頂點(diǎn)的 入度 ，要遍歷整個(gè)表。 }ALGraph。 Typedef struct //圖 { AdjList vertices。 ArcNode *firstarc。 }//ArcNode。 //與 vi鄰接的頂點(diǎn)的下標(biāo)位置 struct ArcNode *nextarc。 //圖的種類(lèi) }MGraph。 //弧的信息 int vexnum, arum。 typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。 //頂點(diǎn)關(guān)系類(lèi)型 InfoType *info。容易判定頂點(diǎn)間有無(wú)邊（?。?，容易計(jì)算頂點(diǎn)的度（出度、入度） 缺點(diǎn)： 所占空間只和頂點(diǎn)個(gè)數(shù)有關(guān)，和邊數(shù)無(wú)關(guān)，在 邊 數(shù) 較少 時(shí)，空間 浪費(fèi) 較大 鄰接矩陣的存儲(chǔ)表示 define INFINITY INT_MAX define MA