1、數(shù)據(jù)結(jié)構(gòu)圖的基本知識點第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 拓撲排序一、現(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中頂點的對偶構(gòu)成的有限集合，記為：E=(V

2、0, V2), (V3, V4), ，若E為空，則圖中只有頂點而沒有邊。其中對偶可以表示成： (Vi, Vj)無序的對偶稱為邊，即(Vi, Vj)=(Vj, Vi) ，其圖稱為無向圖 有序的對偶稱為弧，即 ，則稱Vi為弧尾，稱Vj為弧頭，該圖稱為有向圖二、圖的定義有向圖和無向圖示例：無向圖G1的二元組表示：V(G1)=V1, V2, V3, V4E(G1)=(V1, V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4)有向圖G3的二元組表示： V(G3)=V1, V2, V3 E(G3)=，在無向圖中，若存在一條邊（Vi, Vj），則稱Vi和Vj互為

3、鄰接點（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)無論是有向圖還是無向圖，一個圖的頂點數(shù)n、邊(弧)數(shù)e和每個頂點的度di之間滿足以下的關(guān)系式：即在有

4、向圖或無向圖中：所有頂點度數(shù)之和 ：邊數(shù) = 2 ：13完全圖、稠密圖和稀疏圖在圖G中：若G為無向圖，任意兩個頂點之間都有一條邊，稱G為無向完全圖。頂點數(shù)為n，無向完全圖的邊數(shù)： e=Cn2 =n(n1)/2若G為有向圖，任意兩個頂點Vi, Vj之間都有弧 、 ，稱G為有向完全圖。如頂點數(shù)為n，有向完全圖的弧數(shù)： e=Pn2 =n(n1)例如，無向圖G1就是4個頂點無向完全圖。若一個圖接近完全圖，則稱其為稠密圖；反之，若一個圖含有很少條邊或?。磂n2），則稱其為稀疏圖。4子圖若有圖G=(V, E)和G=(V, E) 且V 是V的子集，即V V ， E是E的子集，即 E E則稱圖G為圖G的子圖

5、。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中：頂點序列（V1, V2, V3, V4）是一條從頂點V1到頂點V4，長度為3的簡單路徑；頂點序列（V1

6、, 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的連通分量。任何連通圖的連通分量只有一個，即其自身，而非連通圖有多個連通分量。在一個連通圖中，含有全部頂點的極小(邊數(shù)最少)連通子圖，稱為該連通圖的

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

8、分量。有向圖G和強連通分量示例： 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ù) V0 V4 V3 V1 V2 V0 V1 V2 V3a ij=0 vi與vj無邊1 vi與vj有邊8.2.1 鄰接矩陣及其實現(xiàn)頂點數(shù)據(jù)存儲：一維數(shù)組（順序存儲）邊（?。┬畔⒌拇鎯Γ亨徑泳仃嚕簣D中n個頂點之間相鄰關(guān)系的n階方陣（即二維數(shù)組ann）鄰接矩陣中元素值情況（規(guī)定自身無

9、邊、無弧）：無向圖a ij=0 vi到vj無弧1 vi到vj有弧有向圖a ij=或0 vi與vj無邊（或vi到vj無?。﹚ vi與vj有邊（或vi到vj有?。┚W(wǎng)W 表示邊上的權(quán)值； 0 表示vi與vj是同一個頂點 表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。 1、舉例無向圖鄰接矩陣表示0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0V1V2 V4 V5 V3 特點：對稱行或列方向的非零元素（或1）的個數(shù)為此頂點的度無向網(wǎng)V1V2 V4 V5 V3 254311鄰接矩陣表示0 2 4 2 0 1 5 1 0 3 1 4 3 0 5 1 0 V1V2V3V

10、4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V51、舉例有向圖V1V2 V3 V4 0 1 1 00 0 0 00 0 0 11 0 0 0鄰接矩陣表示特點：不一定對稱行方向的非零元素（或1）的個數(shù)為此頂點的出度列方向的非零元素（或1）的個數(shù)為此頂點的入度V1V2V3V4V1V2V3V4 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：2、鄰接矩陣法特點3、鄰接矩陣存儲的圖類型定義# define MAX 100 /*

11、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頂點數(shù)、邊數(shù)：鍵盤輸入例：建一個如圖所示的無向圖013424、建圖運算建圖就是完成圖類型變量中

12、各個成員值的創(chuàng)建過程。執(zhí)行時輸入數(shù)據(jù)：5 60 1 2 3 40 10 3 1 2 1 42 32 40 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0算法實現(xiàn)（無向圖）void CreateGraph(MGraph *g) int i, j, v, e; scanf(%d %d, &g-vn, &g-en); /*輸入頂點數(shù)和邊數(shù)*/ for(v=0;vvn;v+) scanf(%d, &g-vexv); /*頂點數(shù)據(jù)輸入*/ for(i=0;ivn;i+) for(j=0;jvn;j+) g-arcij=0; /*鄰接矩陣的初始值都為0*/ for(

13、e=0;een;e+) /*共有g(shù)-en條邊*/ scanf(%d %d, &i, &j); /*指明有邊的兩個頂點的序號*/ g-arcij=1; /*有邊賦值為1*/ g-arcji=1; /*建有向圖時此句不要*/ 8.2.2 鄰接表及其實現(xiàn)是順序與鏈接相結(jié)合的圖的存儲方式所有頂點組成一個數(shù)組，為每個頂點建立一個單鏈表有兩部分組成：表頭頂點數(shù)組（存放頂點信息）表體單鏈表（存放與頂點相關(guān)的邊或弧的信息）1、舉例無向圖鄰接表表示V1V2 V4 V5 V3 頂點的度：該頂點所在單鏈表中表結(jié)點個數(shù)無向網(wǎng)V1V2 V4 V5 V3 254311鄰接表表示V1V2V3V4V5012341304202

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

15、exnext表結(jié)點：adjvexnextw鄰接點序號(下標)下一個鄰接點地址權(quán)值typedef struct arcnode int adjvex; struct arcnode *next; ArcNode, *Arc;表結(jié)點類型3、鄰接表存儲的圖類型定義（2）頂點結(jié)點類型vertexfirstarc頂點結(jié)點：頂點信息鏈表頭指針(指向第一個表結(jié)點)typedef struct vexnode vextype vertex; ArcNode *firstarc; VexNode;頂點結(jié)點類型（3）圖的鄰接表類型typedef struct VexNode adjlistMAX; /*頂點結(jié)點所

16、在數(shù)組*/ int vn, en; ALGraph;分析：各頂點信息：頂點數(shù)據(jù)鍵盤輸入各鏈表：若頂點有出度弧，創(chuàng)建表結(jié)點，頭插入鏈表頂點數(shù)、邊數(shù)：鍵盤輸入例：建一個如圖所示的有向圖4、建圖運算建圖就是完成圖類型變量中各個成員值的創(chuàng)建過程。執(zhí)行時輸入數(shù)據(jù)：4 40 1 2 30 20 1 2 3 3 001 2 3120123012330vertexfirstarcadjvexnext算法實現(xiàn)（有向圖）void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(%d %d, &g-vn, &g-en); /*輸入頂點數(shù)和邊數(shù)*/

17、 for(v=0;vvn;v+) /*頂點數(shù)組元素值的獲得*/ scanf(%d,&g-adjlistv.vertex); /*頂點數(shù)據(jù)鍵盤輸入*/ g-adjlistv.firstarc=NULL; for(e=0;een;e+) /*共有g(shù)-en條邊*/ scanf(%d %d, &i, &j); /*i j有弧，i、j為頂點序號*/ p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; /*把值為j的結(jié)點頭插入到i頂點的鏈表中*/ p-next=g-adjlisti.firstarc; g-adjlisti.firstarc=p; 思考：建無向圖

18、如何修改？0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE補例：圖的鄰接表存儲表示有向圖的鄰接表1 4230 120 1 2 3 4 A B C D EABECD可見，在有向圖的鄰接表中不易找到指向該頂點的弧ABECD有向圖的逆鄰接表A B C D E 30342001234在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧 8.3 圖的遍歷 從圖中某個頂點出發(fā)遍歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。圖的遍歷有兩種方法： 深度優(yōu)先搜索遍歷（DFS） 廣度優(yōu)先搜索遍歷（BFS）。它們對無向圖和有向圖都適用。

19、8.3.1 連通圖的深度優(yōu)先搜索遍歷 1深度優(yōu)先搜索(dfs)的基本思想首先訪問初始出發(fā)點V0，并將其標記設(shè)置為已訪問；然后任選一個與V0相鄰接且沒有被訪問的鄰接點V1作為新的出發(fā)點，訪問V1之后，將其標記設(shè)置為已訪問；再以V1為新的出發(fā)點，繼續(xù)進行深度優(yōu)先搜索，訪問與V1相鄰接且沒有被訪問的任一個頂點V2；重復(fù)上述過程，若遇到一個所有鄰接點均被訪問過的頂點，則回到已訪問頂點序列中最后一個還存在未被訪問的鄰接點的頂點，再從該頂點出發(fā)繼續(xù)進行深度優(yōu)先搜索，直到圖中所有頂點都被訪問過，搜索結(jié)束。 V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2 V7 V6 V5 V4例序列1

20、： 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）訪問頂點：自定義訪問函數(shù) visit()（2）未被訪問的鄰接點：定義一個標記數(shù)組：int visitedMAX visitedi= 0 i號頂點未被訪問 1 i號頂點已被訪問 注意：由于函數(shù)是遞歸的，數(shù)組定義成外部數(shù)組 （3）第一個

21、鄰接點：按鄰接距陣或鄰接表中邊存儲的順序 2 dfs遞歸算法實現(xiàn)函數(shù)實現(xiàn)：形參：圖變量地址，開始頂點的序號（下標）返回值：無void dfs(MGraph *g, int v) int j, w; visit(g, v); /*訪問v號頂點*/ visitedv=1; /*v號頂點為已訪問*/ for(j=0; jvn; j+) /*找所有的鄰接頂點*/ if( g-arcvj=1 & visitedj=0) /*v號頂點與j號頂點 間有邊，且j號頂點為被訪問*/ w=j; dfs(g, w); 2 dfs遞歸算法實現(xiàn)鄰接距陣存儲結(jié)構(gòu)的圖起始頂點的序號（下標）void visit (MGrap

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

23、arcMAXMAX; int vn, en; MGraph; /*鄰接矩陣圖類型*/int visitedMAX; /*訪問標記數(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開始頂點序號*/ CreateGraph(&mg); for(i=0; iadjlistw.firs

24、tarc; /*w號頂點的第一個鄰接點地址*/ 2 bfs算法實現(xiàn)鄰接表存儲結(jié)構(gòu)的圖起始頂點的序號（下標）while(p!=NULL) i=p-adjvex; /*i為鄰接頂點的序號（下標）*/ if(visitedi=0) EnQueue(&Q, i); visitedi=1; p=p-next; /*找所有未訪問的鄰接點的循環(huán)*/ /*隊列循環(huán)*/ /*函數(shù)結(jié)束*/按算法實現(xiàn)的bfs遍歷舉例：V0頂點出發(fā)遍歷結(jié)果（唯一） ：V0、 V1、 V4、 V3、 V2V2頂點出發(fā)遍歷結(jié)果（唯一） ：V2、 V3、 V1、 V4、 V0V0V1V2V3V4無向圖：鄰接表存儲結(jié)構(gòu)：V0V1V2V3V4

25、012341403312403設(shè)計程序創(chuàng)建鄰接表存儲的無向圖，并用bfs圖中頂點信息并輸出：宏定義及數(shù)據(jù)類型：#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

26、; /*頂點結(jié)點類型*/typedef struct VexNode adjlistMAX; /*頂點結(jié)點所在數(shù)組*/ int vn, en; ALGraph; /*鄰接表存儲的圖類型*/int visitedMAX; /*訪問標記數(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; /

27、*start開始頂點序號*/ CreateGraph(&alg); for(i=0; ialg.vn; i+) /*訪問標記數(shù)組置初值0*/ visitedi=0; scanf(%d, &start); bfs(&alg, start);關(guān)于遍歷小結(jié)：若圖是連通的或強連通的，則從圖中某一個頂點出發(fā)可以訪問到圖中所有頂點；若圖是非連通的或非強連通圖，則需從圖中多個頂點出發(fā)搜索訪問，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為每個連通分量中的頂點集。問題：如何通過遍歷算法，求一個非連通圖的連同分量個數(shù)？int count (MGraph *g) int i, m=0; for(

28、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中，其一個極小連通子圖(無回路)是G的生成樹，它含有圖中全部n個頂點，但只有n-1條邊，且不唯一。深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的生成樹c0c1c3c2c4c5例c0c1c3c2c4c5c0c1c3c2c4c5例c0c1c3c2c4c5廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的生成樹非連通圖的生成森林V0V1V3V4V2V6V8V7V5V9（a）不連通的無

29、向圖G12V0V1V3V4V2V8V7V9V6V5（c）圖G12的一個BFS生成森林V0V1V3V4V2V6V8V7V5V9（b）圖G12的一個DFS生成森林 例 要在 n 個城市間建立通訊網(wǎng)，如何在保證 n 個城市連通的前題下最節(jié)省經(jīng)費? ABCDEF101015121287665無向網(wǎng)G1ABCDEF10101276花費：45ABCDEF1512865花費：465ABCDEF107610花費：38例 要在 n 個城市間建立通訊網(wǎng)，如何在保證 n 個城市連通的前題下最節(jié)省經(jīng)費? ABCDEF101015121287665無向網(wǎng)G1這個問題實際上是連通圖的最小生成樹問題。ABCDEF10101

30、51212876655ABCDEF107610最小生成樹的定義若圖G是帶權(quán)的無向連通圖（連通網(wǎng)），生成樹上各邊權(quán)值之和稱為生成樹的代價，代價最小的生成樹稱為最小生成樹；n個頂點、n-1條邊、權(quán)值之和最小。1654327131791812752410連通網(wǎng)：1654321397510生成樹1：1654327139724生成樹2：代價：44代價：60最小生成樹例最小生成樹的應(yīng)用集成電路布線通訊線路布線如何快速有效地構(gòu)造最小生成樹？ 構(gòu)造最小生成樹的準則：必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須使用且僅使用n-1條邊來聯(lián)接網(wǎng)絡(luò)中的n個頂點。一、Prim(普里姆)算法 1、算法思想 設(shè)原連通網(wǎng)G=

31、(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；并把頂點v加入到U中，邊(u,v) 加入到TE中，即修改U=U+v,TE=TE+(u,v)(3)轉(zhuǎn)到（2）重復(fù)執(zhí)行，直到U=V結(jié)束ABCDEF101015121287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCE101512（b）求解過程67ABCDEF1010151212865 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF1015

32、12765（b）求解過程ABCDEF101015121287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF1015765（b）求解過程6ABCDEF10101512128765 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF1015765（b）求解過程6ABCDEF10101512128765 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF10157665（b）求解過程ABCDEF101015121287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF1015765（b）求解過程ABCDEF101015121

33、287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF1015765（b）求解過程86ABCDEF101015121287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹BCDEF10101575（b）求解過程A6ABCDEF101015121287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF101075（b）求解過程1567ABCDEF101015121287665 （a）無向網(wǎng)G1算法演示:Prim算法求解最小生成樹ABCDEF1010125（b）求解過程E67ABCDEF101015121287665 （a）無向網(wǎng)G1算法演

34、示:Prim算法求解最小生成樹最小生成樹ABCDEF10105E例1654326513566425131163141643142116432142516543214253Prim算法最小生成樹生成過程事例(從1號頂點開始) 課堂練習：寫出如下連通網(wǎng)的最小生成樹過程165432496102014510106165432495106最小生成樹1165432495106最小生成樹2最小生成樹不唯一！i012345di.adj000000di.dist01 58 定義一個結(jié)構(gòu)數(shù)組：struct cost int adj; int dist;d20;2、算法實現(xiàn) 02315451839762說明：i數(shù)組

35、下標，又是圖中對應(yīng)頂點的序號di.adj表示i號頂點與生成樹中頂點集合U距離最小的頂點號（u）di.dist表示i號頂點與生成樹中adj頂點（u號頂點）的距離，當dist=0時表示i號頂點已到生成樹中。生成樹初始 選0號頂點2、算法實現(xiàn) i012345di.adj000000di.dist01 58 02315451839762(1)取d數(shù)組中dist0的最小值，則把u=0, v=1,w=1送入生成樹，其頂點集為：0,1，并修改數(shù)組d的內(nèi)容i012345di.adj011000di.dist002 58 生成樹初始 選0號頂點uvw(2)取d數(shù)組中dist0的最小值，則把u=1, v=2,w=

36、2送入生成樹，其頂點集為：0,1,2，并修改數(shù)組d的內(nèi)容i012345di.adj011000di.dist002 58 i012345di.adj012202di.dist0007 56 i012345di.adj012202di.dist0007 56 (3)取d數(shù)組中dist0的最小值，則把u=0, v=4,w=5送入生成樹，其頂點集為：0,1,2,4，并修改數(shù)組d的內(nèi)容i012345di.adj012442di.dist0003 06 (4)取d數(shù)組中dist0的最小值，則把u=4, v=3,w=3送入生成樹，其頂點集為：0,1,2,4,3，并修改數(shù)組d的內(nèi)容i012345di.adj

37、012442di.dist0003 06 i012345di.adj012342di.dist0000 06 i012345di.adj012342di.dist0000 06 (5)取d數(shù)組中dist0的最小值，則把u=2, v=5,w=6送入生成樹，其頂點集為：0,1,2,4,3,5，并修改數(shù)組d的內(nèi)容i012345di.adj012345di.dist0000 00 無向網(wǎng)的建立： #include #define INF 32767typedef struct int u, v, w; Tree; /*最小生成樹順序存儲元素類型*/void CreateGraph(MGraph *g)

38、 int i, j, w, e; FILE *fp; /*文件指針fp*/ fp=fopen(graph.dat, r); /*打開數(shù)據(jù)文件*/ /*圖的頂點數(shù)和邊數(shù)、頂點數(shù)據(jù)和邊的信息從文件獲取*/ fscanf(fp,%d %d, &g-vn, &g-en); for(i=0;ivn;i+) /*鄰接矩陣初始化*/ for(j=0;jvn;j+) /*對角線為0，其余為*/ if(i=j) g-arcij=0; else g-arcij=INF;02315451839762無向網(wǎng)的建立（續(xù)）： for(i=0;ivn;i+) g-vexi=A+i; /*頂點數(shù)據(jù)為A、B、C*/ for(e

39、=0;een;e+) /*從文件讀取對應(yīng)邊信息，即有邊的頂點序號及權(quán)值*/ fscanf(fp, %d %d %d, &i,&j,&w)； g-arcij=w; g-arcji=w; fclose(fp); /*關(guān)閉文件*/ /*結(jié)束函數(shù)*/文件graph.dat中的內(nèi)容為：6 80 1 10 4 50 5 81 2 22 3 72 5 63 4 33 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+)

40、for(j=0;jvn;j+) printf(%dt,g-arcij); printf(n); 輸出：-Graph-6 8prim算法實現(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

41、(di.dist!=0 & di.distmin) j=i; min=di.dist; Ek.u=dj.adj; Ek.v=j; Ek.w=min; /*送入生成樹*/ dj.adj=j; dj.dist=0; /*修改新送入生成樹頂點的信息*/prim算法實現(xiàn)（續(xù)）： for(i=0; ivn; i+) /*修改數(shù)組d中數(shù)組*/ /*新加入到生成樹的j頂點與i頂點邊的權(quán)值更小，則修改*/ if(di.dist!=0 & g-arcjiarcji; /*結(jié)束求生成樹的for */ /*結(jié)束函數(shù) */最小生成樹的輸出： void OutTree(Tree E, int k) int i; pri

42、ntf(n spaning treen); for(i=0; ik; i+) /*生成樹E數(shù)組中有k條邊*/ printf(n%c-%c-%d, Ei.u, Ei.v, Ei.w ); 輸出：spaning tree0-1-1 1-2-2 0-4-5 4-3-32-5-6主函數(shù)： main( ) MGraph G; Tree E20; CreateGraph(&G); OutGraph(&G); Prim(&G,0,E); OutTree( E, G.vn-1 ); 二、 Kruskal（克魯斯卡爾）算法 1、算法思想 把圖的所有邊按其權(quán)值從小到大排成升序先把權(quán)值最小的邊加入生成樹依次選取后面的邊，如該邊加到生成樹中，使生成樹構(gòu)成回路，則舍棄該邊，否則該邊加入到生成樹中。重復(fù)上述過程，直到生成樹中包含n1條邊為止，此時即為最小生成樹。例AFEDCB6314566425AFEDCB13254Krusk