1、第8章圖,2020年9月17日,第8章圖,8.1 圖的基本概念 8.2 圖的基本存儲結(jié)構(gòu) 8.2.1 鄰接距陣及其實現(xiàn) 8.2.2 鄰接表及其實現(xiàn) 8.3 圖的遍歷 8.3.1 深度優(yōu)先搜索遍歷 8.3.2 廣度優(yōu)先搜索遍歷 8.4 圖的應(yīng)用 8.4.1 連通圖的最小生成樹 8.4.2 拓?fù)渑判?一、現(xiàn)實中的圖,8.1 圖的基本概念,圖最常見的應(yīng)用是在交通運輸和通信網(wǎng)絡(luò)中找出造價最低的方案。通信網(wǎng)絡(luò)示例如下圖所示：,圖G是由一個頂點集V和一個邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。記為二元組形式： G= (V, E) 其中: V是由頂點構(gòu)成的非空有限集合，記為：VV0, V1, V2, Vn-1 E是由V中頂點

2、的對偶構(gòu)成的有限集合，記為：E=(V0, V2), (V3, V4), ，若E為空，則圖中只有頂點而沒有邊。 其中對偶可以表示成： (Vi, Vj)無序的對偶稱為邊，即(Vi, Vj)=(Vj, Vi) ，其圖稱為無向圖 有序的對偶稱為弧，即 ，則稱Vi為弧尾，稱Vj為弧頭，該圖稱為有向圖,二、圖的定義,有向圖和無向圖示例：,無向圖G1的二元組表示： V(G1)=V1, V2, V3, V4 E(G1)=(V1, V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4),有向圖G3的二元組表示： V(G3)=V1, V2, V3 E(G3)=，,在無向圖

3、中，若存在一條邊（Vi, Vj），則稱Vi和Vj互為鄰接點（Adjacent） 在有向圖中，若存在一條弧，則稱Vi為此弧的起點，稱Vj為此弧的終點，稱Vi鄰接到Vj，Vj鄰接自Vi，Vi和Vj互為鄰接點。,1鄰接點,2頂點的度、入度和出度,在無向圖中，與頂點v相鄰接的邊數(shù)稱為該頂點的度，記為D(v)。 在有向圖中，頂點v的度又分為入度和出度兩種： 以頂點v為終點(弧頭)的弧的數(shù)目稱為頂點v的入度，記為ID(v)； 以頂點v為起點(弧尾)的弧的數(shù)目稱為頂點v的出度，記為OD(v)； 有向圖頂點v的度為該頂點的入度和出度之和，即 D(v)=ID(v)+OD(v),無論是有向圖還是無向圖，一個圖的頂

4、點數(shù)n、邊(弧)數(shù)e和每個頂點的度di之間滿足以下的關(guān)系式：,即在有向圖或無向圖中： 所有頂點度數(shù)之和 ：邊數(shù) = 2 ：1,3完全圖、稠密圖和稀疏圖,在圖G中： 若G為無向圖，任意兩個頂點之間都有一條邊，稱G為無向完全圖。頂點數(shù)為n，無向完全圖的邊數(shù)： e=Cn2 =n(n1)/2 若G為有向圖，任意兩個頂點Vi, Vj之間都有弧 、 ，稱G為有向完全圖。如頂點數(shù)為n，有向完全圖的弧數(shù)： e=Pn2 =n(n1) 例如，無向圖G1就是4個頂點無向完全圖。 若一個圖接近完全圖，則稱其為稠密圖；反之，若一個圖含有很少條邊或弧（即en2），則稱其為稀疏圖。,4子圖,若有圖G=(V, E)和G=(V

5、, E) 且V 是V的子集，即V V ， E是E的子集，即 E E 則稱圖G為圖G的子圖。,5路徑、回路和路徑長度,在無向圖G中，若存在一個頂點序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均為圖G的邊，則該稱頂點的序列為頂點Vp到頂點Vq的路徑。若G是有向圖，則路徑是有向的。 路徑長度定義為路徑上的邊數(shù)或者弧的數(shù)目。 若一條路徑中不出現(xiàn)重復(fù)頂點，則稱此路徑為簡單路徑。 若一條路徑的起點和終點相同（Vp=Vq）稱為回路或環(huán)。 除了起點和終點相同外，其余頂點不相同的回路，稱為簡單回路或簡單環(huán)。,例如，在無向圖G1中：

6、 頂點序列（V1, V2, V3, V4）是一條從頂點V1到頂點V4，長度為3的簡單路徑； 頂點序列（V1, V2, V4, V1, V3）是一條從頂點V1到頂點V3，長度為4的路徑，但不是簡單路徑； 頂點序列（V1, V2, V3, V1）是一條長度為3的簡單回路。 在有向圖G3中： 頂點序列（V2, V3, V2）是一個長度為2的有向簡單環(huán)。,6連通、連通分量和連通圖、生成樹,在無向圖G中： 如果從頂點Vi 到頂點Vj至少有一條路徑，則稱Vi與Vj是連通的。 如果圖中任意兩個頂點都連通，則稱G為連通圖，否則稱為非連通圖。 在非連通圖G中，任何一個極大連通子圖稱為G的連通分量。 任何連通圖的

7、連通分量只有一個，即其自身，而非連通圖有多個連通分量。 在一個連通圖中，含有全部頂點的極小(邊數(shù)最少)連通子圖，稱為該連通圖的生成樹。(包含圖的所有 n 個結(jié)點，但只含圖的 n-1 條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán)),非連通圖G4,圖G1和G2為連通圖,非連通圖G4的三個連通分量,連通圖G5,連通圖G5的兩棵生成樹,7強(qiáng)連通、強(qiáng)連通分量和強(qiáng)連通圖,在有向圖G中： 存在從頂點Vi 到頂點Vj的路徑，也存在從頂點Vj 到頂點Vi的路徑，則稱Vi與Vj是強(qiáng)連通的。 如果圖中任意兩個頂點都是強(qiáng)連通，則稱G為強(qiáng)連通圖，否則稱為非強(qiáng)連通圖。 在非強(qiáng)連通圖G中，任何一個極大強(qiáng)連通子圖稱為G

8、的強(qiáng)連通分量。 任何強(qiáng)連通圖的強(qiáng)連通分量只有一個，即其自身，而非強(qiáng)連通圖有多個強(qiáng)連通分量。,有向圖G和強(qiáng)連通分量示例：,8權(quán)、帶權(quán)圖、有向網(wǎng)和無向網(wǎng),在一個圖中，各邊(或弧)上可以帶一個數(shù)值，這個數(shù)值稱為權(quán)。 這種每條邊都帶權(quán)的圖稱為帶權(quán)圖或網(wǎng) 有向網(wǎng)：帶權(quán)有向圖 無向網(wǎng)：帶權(quán)無向圖,8.2 圖的基本存儲結(jié)構(gòu),圖需存儲的信息： 各頂點的數(shù)據(jù) 各個邊（弧）的信息，包括： 哪兩個頂點有邊（?。?若有權(quán)要表示出來 頂點數(shù)、邊（?。?shù),8.2.1 鄰接矩陣及其實現(xiàn),頂點數(shù)據(jù)存儲： 一維數(shù)組（順序存儲） 邊（弧）信息的存儲： 鄰接矩陣：圖中n個頂點之間相鄰關(guān)系的n階方陣（即二維數(shù)組ann） 鄰接矩陣中元

9、素值情況（規(guī)定自身無邊、無?。?無向圖,有向圖,網(wǎng),W 表示邊上的權(quán)值； 0 表示vi與vj是同一個頂點 表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。,1、舉例,無向圖,特點： 對稱 行或列方向的非零元素（或1）的個數(shù)為此頂點的度,無向網(wǎng),1、舉例,有向圖,特點： 不一定對稱 行方向的非零元素（或1）的個數(shù)為此頂點的出度 列方向的非零元素（或1）的個數(shù)為此頂點的入度,容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否 有邊（弧）、找頂點的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。,鄰接矩陣法優(yōu)點：,鄰接矩陣法缺點：,2、鄰接矩陣法

10、特點,3、鄰接矩陣存儲的圖類型定義,# define MAX 100 /* MAX為圖中頂點最多個數(shù) */ typedef int vextype; /* vextype為頂點的數(shù)據(jù)類型 */ typedef struct vextype vexMAX; /* 一維數(shù)組存儲頂點信息 */ int arcMAXMAX; /*鄰接矩陣存儲邊（弧）信息 */ int vn, en; /* vn頂點數(shù)和en邊數(shù) */ MGraph; /* 圖類型 */,注：MGraph 既可以表示有向圖、無向圖，也可以表示有整型權(quán)的網(wǎng),分析： 各頂點信息：鍵盤輸入 各邊信息：鄰接矩陣，頂點間有邊值為1，無邊值為0 頂

11、點數(shù)、邊數(shù)：鍵盤輸入,例：建一個如圖所示的無向圖,4、建圖運算 建圖就是完成圖類型變量中各個成員值的創(chuàng)建過程。,執(zhí)行時輸入數(shù)據(jù)： 5 6 0 1 2 3 4 0 1 0 3 1 2 1 4 2 3 2 4,算法實現(xiàn)（無向圖）,void CreateGraph(MGraph *g) int i, j, v, e; scanf(%d %d, /*建有向圖時此句不要*/ ,8.2.2 鄰接表及其實現(xiàn),是順序與鏈接相結(jié)合的圖的存儲方式 所有頂點組成一個數(shù)組，為每個頂點建立一個單鏈表 有兩部分組成： 表頭頂點數(shù)組（存放頂點信息） 表體單鏈表（存放與頂點相關(guān)的邊或弧的信息）,1、舉例,無向圖,頂點的度：該

12、頂點所在單鏈表中表結(jié)點個數(shù),無向網(wǎng),與頂點V1相鄰接的頂點在數(shù)組中的下標(biāo),權(quán)值,1、舉例,有向圖,以頂點V1為始點的弧的終點頂點在數(shù)組中的下標(biāo),頂點的出度 該頂點所在單鏈表中表結(jié)點個數(shù) 頂點的入度 查詢整個鄰接表中的表結(jié)點，與該頂點的序號（數(shù)組下標(biāo)）一致的表結(jié)點個數(shù),鄰接表的缺點：,鄰接表的優(yōu)點：,空間效率高；容易尋找頂點的鄰接點；,判斷任意兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。,2、鄰接表法特點,3、鄰接表存儲的圖類型定義,（1）表(邊)結(jié)點表示邊(或弧)信息的鏈表中結(jié)點,表結(jié)點：,鄰接點序號(下標(biāo)),下一個鄰接點地址,權(quán)值,typedef struct arcn

13、ode int adjvex; struct arcnode *next; ArcNode, *Arc;,表結(jié)點類型,3、鄰接表存儲的圖類型定義,（2）頂點結(jié)點類型,頂點結(jié)點：,頂點信息,鏈表頭指針(指向第一個表結(jié)點),typedef struct vexnode vextype vertex; ArcNode *firstarc; VexNode;,頂點結(jié)點類型,（3）圖的鄰接表類型,typedef struct VexNode adjlistMAX; /*頂點結(jié)點所在數(shù)組*/ int vn, en; ALGraph;,分析： 各頂點信息：頂點數(shù)據(jù)鍵盤輸入 各鏈表：若頂點有出度弧，創(chuàng)建表結(jié)點

14、，頭插入鏈表 頂點數(shù)、邊數(shù)：鍵盤輸入,例：建一個如圖所示的有向圖,4、建圖運算 建圖就是完成圖類型變量中各個成員值的創(chuàng)建過程。,執(zhí)行時輸入數(shù)據(jù)： 4 4 0 1 2 3 0 2 0 1 2 3 3 0,vertex,firstarc,adjvex,next,算法實現(xiàn)（有向圖）,void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(%d %d, ,思考： 建無向圖如何修改？,B,A,C,D,F,E,補(bǔ)例：圖的鄰接表存儲表示,有向圖的鄰接表,A,B,E,C,D,可見，在有向圖的鄰接表中不易找到指向該頂點的弧,A,B,E,C,

15、D,有向圖的逆鄰接表,在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧,8.3 圖的遍歷,從圖中某個頂點出發(fā)遍歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。 圖的遍歷有兩種方法： 深度優(yōu)先搜索遍歷（DFS） 廣度優(yōu)先搜索遍歷（BFS）。 它們對無向圖和有向圖都適用。,8.3.1 連通圖的深度優(yōu)先搜索遍歷,1深度優(yōu)先搜索(dfs)的基本思想 首先訪問初始出發(fā)點V0，并將其標(biāo)記設(shè)置為已訪問； 然后任選一個與V0相鄰接且沒有被訪問的鄰接點V1作為新的出發(fā)點，訪問V1之后，將其標(biāo)記設(shè)置為已訪問； 再以V1為新的出發(fā)點，繼續(xù)進(jìn)行深度優(yōu)先搜索，訪問與V1相鄰接且沒有被訪問的任一個

16、頂點V2； 重復(fù)上述過程，若遇到一個所有鄰接點均被訪問過的頂點，則回到已訪問頂點序列中最后一個還存在未被訪問的鄰接點的頂點，再從該頂點出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中所有頂點都被訪問過，搜索結(jié)束。,例,序列1： V0,V1,V3,V7,V4,V2,V5,V6,從v0出發(fā)的DFS序列為：,由于沒有規(guī)定 訪問鄰接點的順序， DFS序列不是唯一的,序列2： V0,V1,V4,V7,V3,V2,V5,V6,算法描述： 訪問開始頂點（如 v）； 尋找 v 頂點未被訪問的第一個鄰接頂點（如 w）； 并把 w 作為開始頂點繼續(xù)深度優(yōu)先搜索遍歷（遞歸思想）； 直到所有頂點被訪問； 其中處理： （1）訪問頂點

17、：自定義訪問函數(shù) visit() （2）未被訪問的鄰接點：定義一個標(biāo)記數(shù)組：int visitedMAX visitedi= 0 i號頂點未被訪問 1 i號頂點已被訪問 注意：由于函數(shù)是遞歸的，數(shù)組定義成外部數(shù)組 （3）第一個鄰接點：按鄰接距陣或鄰接表中邊存儲的順序,2 dfs遞歸算法實現(xiàn),函數(shù)實現(xiàn)： 形參：圖變量地址，開始頂點的序號（下標(biāo)） 返回值：無 void dfs(MGraph *g, int v) int j, w; visit(g, v); /*訪問v號頂點*/ visitedv=1; /*v號頂點為已訪問*/ for(j=0; jvn; j+) /*找所有的鄰接頂點*/ if(

18、g-arcvj=1 ,2 dfs遞歸算法實現(xiàn),鄰接距陣存儲結(jié)構(gòu)的圖,起始頂點的序號（下標(biāo)）,void visit (MGraph *g, int v) printf(n %d, g-vexv); ,按算法實現(xiàn)的dfs遍歷舉例：,V0頂點出發(fā)遍歷結(jié)果（唯一） ： V0、 V1、 V2、 V3、 V4 V2頂點出發(fā)遍歷結(jié)果（唯一） ： V2、 V1、 V0、 V4、 V3,設(shè)計程序創(chuàng)建鄰接矩陣的無向圖，并用dfs圖中頂點信息并輸出： 宏定義及數(shù)據(jù)類型： #include #define MAX 20 /*圖頂點最多不超過20*/ typedef int vextype; /*圖頂點為int型*/

19、typedef struct vextype vexMAX; int arcMAXMAX; int vn, en; MGraph; /*鄰接矩陣圖類型*/ int visitedMAX; /*訪問標(biāo)記數(shù)組*/,函數(shù)定義： void CreateGraph(MGraph *g) /*創(chuàng)建無向圖*/ void visit(MGraph *g, int v) /*訪問圖中某個頂點*/ void dfs(MGraph *g, int v) /*dfs遍歷圖*/ main() /*主函數(shù)*/ MGraph mg; /*mg為圖結(jié)構(gòu)變量/ int i, start; /*start開始頂點序號*/ Cre

20、ateGraph( ,8.3.2 連通圖的廣度優(yōu)先搜索遍歷,1廣度優(yōu)先搜索(bfs)的基本思想 從圖G=(V, E)的某個起始點v0出發(fā)，首先訪問起始點v0，接著依次訪問v0所有鄰接點; 再找v0的第一個鄰接頂點(如 w1)，再依次訪問w1頂點的所有未被訪問的鄰接頂點； 再找v0的第二個鄰接頂點(如 w2)，再依次訪問w2頂點的所有未被訪問的鄰接頂點； 直到圖中所有頂點都被訪問到為止。,求圖G 的以V0起點的的廣度優(yōu)先序列:,V0,V1,V2,V3,V4,V5,V6,V7,例,從C0出發(fā)的BFS序列為：,由于沒有規(guī)定 訪問鄰接點的順序， BFS序列不是唯一的,c0 c1 c2 c3 c4 c5

21、,從圖中某頂點vi出發(fā)： 1）訪問頂點vi ；（容易實現(xiàn)） 2）訪問vi 的所有未被訪問的鄰接點w1 ,w2 , wk ； 3）依次從這些鄰接點（在步驟 2）訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問； 為實現(xiàn) 3），需要保存在步驟2）中訪問的頂點，而且訪問這些頂點鄰接點的順序為：“先被訪問先出發(fā)”的原則。故用隊列來管理鄰接點出發(fā)的次序。,在廣度優(yōu)先遍歷算法中， 需設(shè)置一隊列Q， 保存已訪問的頂點， 并控制遍歷頂點的順序。,2 bfs算法實現(xiàn),QUEUE,V0,V1,V2,V3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V

22、5,V6,V7,數(shù)據(jù)結(jié)構(gòu)： 1）全局標(biāo)記數(shù)組 int visitedMAX; visitedi= 0 i號頂點未被訪問 1 i號頂點已被訪問 2）鄰接表存儲結(jié)構(gòu),算法描述： (1) 定義一個隊列Q并初始化 (2) 開始頂點（如 v）入隊，置訪問標(biāo)記為1； (3) 當(dāng)隊列不空時，反復(fù)做： (a)隊頭頂點出隊w ，訪問w； (b)尋找w的所有未被訪問的鄰接頂點入隊，置訪問標(biāo)記為1；,2 bfs算法實現(xiàn),函數(shù)實現(xiàn)： 形參：圖變量地址，開始頂點的序號（下標(biāo)） 返回值：無 void bfs(ALGraph *g, int v) int i, w; ArcNode *p; SeqQueue Q; /*循環(huán)

23、隊列*/ InitQueue( /*w號頂點的第一個鄰接點地址*/,2 bfs算法實現(xiàn),鄰接表存儲結(jié)構(gòu)的圖,起始頂點的序號（下標(biāo)）,while(p!=NULL) i=p-adjvex; /*i為鄰接頂點的序號（下標(biāo)）*/ if(visitedi=0) EnQueue( /*找所有未訪問的鄰接點的循環(huán)*/ /*隊列循環(huán)*/ /*函數(shù)結(jié)束*/,按算法實現(xiàn)的bfs遍歷舉例：,V0頂點出發(fā)遍歷結(jié)果（唯一） ： V0、 V1、 V4、 V3、 V2 V2頂點出發(fā)遍歷結(jié)果（唯一） ： V2、 V3、 V1、 V4、 V0,設(shè)計程序創(chuàng)建鄰接表存儲的無向圖，并用bfs圖中頂點信息并輸出： 宏定義及數(shù)據(jù)類型：

24、#include #include Queue.h /*循環(huán)隊列相關(guān)操作的定義文件*/ #define MAX 20 /*圖頂點最多不超過20*/ typedef int vextype; /*圖頂點為int型*/ typedef struct arcnode int adjvex; struct arcnode *next; ArcNode; /*表結(jié)點類型*/,typedef struct vexnode vextype vertex; ArcNode *firstarc; VexNode; /*頂點結(jié)點類型*/ typedef struct VexNode adjlistMAX; /*頂

25、點結(jié)點所在數(shù)組*/ int vn, en; ALGraph; /*鄰接表存儲的圖類型*/ int visitedMAX; /*訪問標(biāo)記數(shù)組*/,函數(shù)定義： void CreateGraph(ALGraph *g) /*創(chuàng)建圖*/ void visit(MGraph *g, int v) /*訪問圖中某個頂點*/ void bfs(MGraph *g, int v) /*bfs遍歷圖*/ main() /*主函數(shù)*/ ALGraph alg; /*mg為鄰接表圖結(jié)構(gòu)變量/ int i, start; /*start開始頂點序號*/ CreateGraph( ,關(guān)于遍歷小結(jié)： 若圖是連通的或強(qiáng)連通

26、的，則從圖中某一個頂點出發(fā)可以訪問到圖中所有頂點； 若圖是非連通的或非強(qiáng)連通圖，則需從圖中多個頂點出發(fā)搜索訪問，而每一次從一個新的起始點出發(fā)進(jìn)行搜索過程中得到的頂點訪問序列恰為每個連通分量中的頂點集。,問題：如何通過遍歷算法，求一個非連通圖的連同分量個數(shù)？ int count (MGraph *g) int i, m=0; for(i=0; ivn; i+) if(visitedi=0) m+; dfs(g, i); return m; ,生成樹定義,圖的遍歷過程中經(jīng)過的n個頂點n-1條邊即為一棵生成樹。,8.4 圖的應(yīng)用,8.4.1 連通圖的最小生成樹無向圖的應(yīng)用,在無向連通圖G中，其一個極

27、小連通子圖(無回路)是G的生成樹，它含有圖中全部n個頂點，但只有n-1條邊，且不唯一。,深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的生成樹,c0,c1,c3,c2,c4,c5,例,c0,c1,c3,c2,c4,c5,例,c0,c1,c3,c2,c4,c5,廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的生成樹,非連通圖的生成森林,例,要在 n 個城市間建立通訊網(wǎng)，如何在保證 n 個城市連通的前題下最節(jié)省經(jīng)費?,無向網(wǎng)G1,例,要在 n 個城市間建立通訊網(wǎng)，如何在保證 n 個城市連通的前題下最節(jié)省經(jīng)費?,無向網(wǎng)G1,這個問題實際上是連通圖的最小生成樹問題。,最小生成樹的定義,若圖G是帶權(quán)的無向連通圖（連通網(wǎng)），生成

28、樹上各邊權(quán)值之和稱為生成樹的代價，代價最小的生成樹稱為最小生成樹； n個頂點、n-1條邊、權(quán)值之和最小。,代價：44,代價：60,最小生成樹,例,最小生成樹的應(yīng)用,集成電路布線,通訊線路布線,構(gòu)造最小生成樹的準(zhǔn)則：,必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹； 必須使用且僅使用n-1條邊來聯(lián)接網(wǎng)絡(luò)中的n個頂點。,一、Prim(普里姆)算法,1、算法思想,設(shè)原連通網(wǎng)G=(V, E)，生成的最小生成樹T=(U, TE)，則算法步驟如下： (1)任選一個頂點u0放入U中，即初始U=u0，TE= (2)找連接U與V-U集合的一條權(quán)值最小的邊 即找頂點uU,頂點vV-U的權(quán)值最小的一條邊(u,v)E； 并把

29、頂點v加入到U中，邊(u,v) 加入到TE中，即修改U=U+v,TE=TE+(u,v) (3)轉(zhuǎn)到（2）重復(fù)執(zhí)行，直到U=V結(jié)束,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,E,10,15,12,（b）求解過程,6,7,A,B,C,D,E,F,10,10,15,12,12,8,6,5,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,15,12,7,6,5,（b）求解過程,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,15,7,6,5,（b）求解過程,6,A,B,C,D,E,F,10,10,15

30、,12,12,8,7,6,5,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,15,7,6,5,（b）求解過程,6,A,B,C,D,E,F,10,10,15,12,12,8,7,6,5,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,15,7,6,5,（b）求解過程,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,15,7,6,5,（b）求解過程,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,15,7,6,5,（b）求解過程,6,A,B,C,

31、D,E,F,10,10,15,12,12,8,7,6,6,5,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,B,C,D,E,F,10,10,15,7,5,（b）求解過程,A,6,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,10,7,5,（b）求解過程,15,6,7,A,B,C,D,E,F,10,10,15,12,12,8,7,6,6,5,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,A,B,C,D,E,F,10,10,5,（b）求解過程,E,6,7,（a）無向網(wǎng)G1,算法演示:Prim算法求解最小生成樹,最小生成樹,A,B,C,D,

32、E,F,10,10,5,E,1,Prim算法最小生成樹生成過程事例(從1號頂點開始),課堂練習(xí)：寫出如下連通網(wǎng)的最小生成樹過程,最小生成樹 不唯一！,定義一個結(jié)構(gòu)數(shù)組： struct cost int adj; int dist; d20;,2、算法實現(xiàn),說明： i數(shù)組下標(biāo)，又是圖中對應(yīng)頂點的序號 di.adj表示i號頂點與生成樹中頂點集合U距離最小的頂點號（u） di.dist表示i號頂點與生成樹中adj頂點（u號頂點）的距離，當(dāng)dist=0時表示i號頂點已到生成樹中。,生成樹初始 選0號頂點,2、算法實現(xiàn),(1)取d數(shù)組中dist0的最小值，則把u=0, v=1,w=1送入生成樹，其頂點集

33、為：0,1，并修改數(shù)組d的內(nèi)容,生成樹初始 選0號頂點,u,v,w,(2)取d數(shù)組中dist0的最小值，則把u=1, v=2,w=2送入生成樹，其頂點集為：0,1,2，并修改數(shù)組d的內(nèi)容,(3)取d數(shù)組中dist0的最小值，則把u=0, v=4,w=5送入生成樹，其頂點集為：0,1,2,4，并修改數(shù)組d的內(nèi)容,(4)取d數(shù)組中dist0的最小值，則把u=4, v=3,w=3送入生成樹，其頂點集為：0,1,2,4,3，并修改數(shù)組d的內(nèi)容,(5)取d數(shù)組中dist0的最小值，則把u=2, v=5,w=6送入生成樹，其頂點集為：0,1,2,4,3,5，并修改數(shù)組d的內(nèi)容,無向網(wǎng)的建立：,#inclu

34、de #define INF 32767 typedef struct int u, v, w; Tree; /*最小生成樹順序存儲元素類型*/ void CreateGraph(MGraph *g) int i, j, w, e; FILE *fp; /*文件指針fp*/ fp=fopen(graph.dat, r); /*打開數(shù)據(jù)文件*/ /*圖的頂點數(shù)和邊數(shù)、頂點數(shù)據(jù)和邊的信息從文件獲取*/ fscanf(fp,%d %d, ,無向網(wǎng)的建立（續(xù)）：,for(i=0;ivn;i+) g-vexi=A+i; /*頂點數(shù)據(jù)為A、B、C*/ for(e=0;een;e+) /*從文件讀取對應(yīng)邊信

35、息，即有邊的頂點序號及權(quán)值*/ fscanf(fp, %d %d %d, /*關(guān)閉文件*/ /*結(jié)束函數(shù)*/,文件graph.dat中的內(nèi)容為： 6 8 0 1 1 0 4 5 0 5 8 1 2 2 2 3 7 2 5 6 3 4 3 3 5 9,無向網(wǎng)鄰接距陣的輸出：,void OutGraph(MGraph *g) int i, j; printf(n-Graph-n); printf(n vn=%d t en=%d, g-vn, g-en); for(i=0;ivn;i+) for(j=0;jvn;j+) printf(%dt,g-arcij); printf(n); ,輸出： -Gr

36、aph- 6 8,prim算法實現(xiàn)：,void Prim(MGraph *g, int v0, Tree E) int i,j, k, min; struct cost int adj; int dist; d20; for(i=0;ivn;i+) /*d數(shù)組初始化*/ di.adj=v0; di.dist=g-arcv0i; for(k=0; kvn-1; k+) /*求vn-1條生成樹的邊*/ min=INF; j=-1; for(i=0; ivn; i+) /*找權(quán)值最小的邊*/ if(di.dist!=0 /*修改新送入生成樹頂點的信息*/,prim算法實現(xiàn)（續(xù)）：,for(i=0;

37、ivn; i+) /*修改數(shù)組d中數(shù)組*/ /*新加入到生成樹的j頂點與i頂點邊的權(quán)值更小，則修改*/ if(di.dist!=0 /*結(jié)束求生成樹的for */ /*結(jié)束函數(shù) */,最小生成樹的輸出：,void OutTree(Tree E, int k) int i; printf(n spaning treen); for(i=0; ik; i+) /*生成樹E數(shù)組中有k條邊*/ printf(n%c-%c-%d, Ei.u, Ei.v, Ei.w ); ,輸出： spaning tree 0-1-1 1-2-2 0-4-5 4-3-3 2-5-6,主函數(shù)：,main( ) MGraph G; Tree E20; CreateGraph( ,二、 Kruskal（克魯斯卡爾）算法,1、算法思想,把圖的所有邊按其權(quán)值從小到大排成升序 先把權(quán)值最小的邊加入生成樹 依次選取后面的邊，如該邊加到生成樹中，使生成樹構(gòu)成回路，則舍棄該邊，否則該邊加入到生成樹中。 重復(fù)上述過程，直到生成樹中包含n1條邊為