《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件5-10普里姆算法思路及步驟

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：劉斌普里姆算法思路及步驟常州信息職業(yè)技術(shù)學(xué)院02教學(xué)目標(biāo)12生成樹（Spanning Tree）的概念03普里姆（Prim）算法三、鏈表的插入04普里姆算法思路及步驟1.0最小生成樹對于一個無回路的連通圖G，選擇任意頂點作為根，則圖G構(gòu)成一棵樹，因此，我們將一個無回路的連通圖也稱為樹。04普里姆算法思路及步驟1.01生成樹（Spanning Tree）如果連通圖G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹。V5V0V1V3V4V2V6V7圖G9V5V0V1V3V4V2V6V7（a）V0V1V3V4V2V5V6V7（b）05普里

2、姆算法思路及步驟1.0說明：生成樹是連通圖的包含圖中所有頂點的極小連通子圖。n個頂點連通圖的生成樹共有n-1條邊。圖的生成樹不唯一。05普里姆算法思路及步驟1.02深度優(yōu)先生成樹和廣度優(yōu)先生成樹設(shè)圖G=(V，E)是一個具有n個頂點的連通圖。則從G的任一頂點（源點）出發(fā)，作一次深度（或廣度）優(yōu)先搜索，搜索到的n個頂點和搜索過程中從一個已訪問過的頂點vi搜索到一個未曾訪問過的鄰接點vj，所經(jīng)過的邊(vi，vj)組成的極小連通子圖就是生成樹（源點是生成樹的根）。由深度優(yōu)先搜索得到的生成樹稱為深度優(yōu)先生成樹，簡稱為DFS生成樹；由廣度優(yōu)先搜索得到的生成樹稱為廣度優(yōu)先生成樹，簡稱為BFS生成樹。V0V1

3、V3V4V2V6V7圖G9V5V0V1V3V4V2V6V7（a）V0V1V3V4V2V5V6V7（b）06普里姆算法思路及步驟1.033最小生成樹對于連通的帶權(quán)圖（連通網(wǎng)）G=(V,E)，其生成樹也是帶權(quán)的，生成樹T=(V,TE)各邊的權(quán)值總和稱為該樹的權(quán)，記作： 其中，w(u,v)表示邊(u,v)上的權(quán)。權(quán)值最小的生成樹稱為G的最小生成樹（Minimum SpannirngTree），最小生成樹簡記為MST。07普里姆算法思路及步驟1.0求最小生成樹算法1普里姆（Prim）算法設(shè)G=(V,E)是連通網(wǎng)，G的最小生成樹為T=(V,TE)，每次選取一端在U中，另一端在V-U中且權(quán)值最小的邊，將其

4、加入TE，另一端的頂點加入U，當(dāng)TE含有n-1條邊或U=V時，TE便是最小生成樹的邊集。33最小生成樹三、鏈表的插入08普里姆算法思路及步驟1.03（2）數(shù)據(jù)描述 使用鄰接矩陣的存儲結(jié)構(gòu)存儲圖G。為了實現(xiàn)普里姆算法需要附設(shè)一個輔助數(shù)組EdgeVertexNum，用于記錄U中頂點到V-U頂點具有較小權(quán)值的邊，該數(shù)組的每個元素包含三個域，ch1、ch2和weight，分別表示邊(ch1,ch2)的兩個頂點和該邊上的權(quán)值。具體定義如下：#define VertexNum 20 /最大頂點數(shù)typedef char VertexType;/頂點類型定義typedef int EdgeType;/權(quán)值類型定義struct edge/用于算法中存儲一條邊及權(quán)值VertexType ch1;/頂點1VertexType ch2;/頂點2EdgeType weight;/權(quán)值EdgeVertexNum;09普里姆算法思路及步驟1.0132（3）算法步驟初始化：U=u0，TE=，u0是圖G中任選的一個頂點（起始頂點），轉(zhuǎn)向；求最小權(quán)值的邊：在所有uU，vV-U中，找一條權(quán)值最小的