數(shù)據(jù)結(jié)構(gòu)圖的基本知識點

1、第第8章圖章圖2022年1月1日第第8章圖章圖一、一、現(xiàn)實中的圖現(xiàn)實中的圖8.1 8.1 圖的基本概念圖的基本概念 圖最常見的應(yīng)用是在交通運輸和通信網(wǎng)絡(luò)中找出造價圖最常見的應(yīng)用是在交通運輸和通信網(wǎng)絡(luò)中找出造價最低的方案。通信網(wǎng)絡(luò)示例如下圖所示：最低的方案。通信網(wǎng)絡(luò)示例如下圖所示： 圖圖G是由一個是由一個頂點集頂點集V和一個和一個邊邊集集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。記為二元組形式：記為二元組形式： G= (V, E)其中其中: V是由頂點構(gòu)成的是由頂點構(gòu)成的非空非空有限集合，記為：有限集合，記為：VV0, V1, V2, Vn-1 E是由是由V中頂點的對偶構(gòu)成的有限集合，記為：中頂點的對偶

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

3、2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4)有向圖有向圖G3的二元組表示：的二元組表示： V(G3)=V1, V2, V3 E(G3)=，l 在無向圖中，若存在一條邊（在無向圖中，若存在一條邊（Vi, Vj），則稱），則稱Vi和和Vj互為互為（Adjacent）l 在有向圖中，若存在一條弧在有向圖中，若存在一條弧，則稱，則稱Vi為此為此弧的弧的起點，起點，稱稱Vj為此弧的為此弧的終點，終點，稱稱Vi鄰接到鄰接到Vj，Vj鄰接自鄰接自Vi，Vi和和Vj互為鄰接點互為鄰接點。 2頂點的度、入度和出度頂點的度、入度和出度l 在無向圖中，與頂點在無向圖

4、中，與頂點v相鄰接的邊數(shù)稱為相鄰接的邊數(shù)稱為該頂點的該頂點的度度，記為，記為D(v)。l 在有向圖中，頂點在有向圖中，頂點v的度又分為的度又分為入度入度和和出度出度兩種：兩種：以頂點以頂點v為終點為終點(弧頭弧頭)的弧的數(shù)目稱為頂點的弧的數(shù)目稱為頂點v的的入度入度，記，記為為ID(v)；以頂點以頂點v為起點為起點(弧尾弧尾)的弧的數(shù)目稱為頂點的弧的數(shù)目稱為頂點v的的出度出度，記，記為為OD(v)；有向圖頂點有向圖頂點v的度為該頂點的入度和出度之和，即的度為該頂點的入度和出度之和，即 D(v)=ID(v)+OD(v)l 無論是有向圖還是無向圖，一個圖的頂點數(shù)無論是有向圖還是無向圖，一個圖的頂點數(shù)

5、n n、邊、邊( (弧弧) )數(shù)數(shù)e e和每個頂點的度和每個頂點的度d di i之間滿足以下的關(guān)系式：之間滿足以下的關(guān)系式：11()2niieD vl 即在有向圖或無向圖中：即在有向圖或無向圖中：所有頂點度數(shù)之和所有頂點度數(shù)之和 ：邊數(shù)：邊數(shù) = 2 = 2 ：1 13完全圖、稠密圖和稀疏圖完全圖、稠密圖和稀疏圖l 在圖在圖G中：中：若若G為無向圖，任意兩個頂點之間都有一條邊，稱為無向圖，任意兩個頂點之間都有一條邊，稱G為為無無向完全圖向完全圖。頂點數(shù)為。頂點數(shù)為n，無向完全圖的邊數(shù)：，無向完全圖的邊數(shù)： e=Cn2 =n(n 1)/2若若G為有向圖，任意兩個頂點為有向圖，任意兩個頂點Vi,

6、Vj之間都有弧之間都有弧 、 ，稱，稱G為為有向完全圖有向完全圖。如頂點數(shù)為。如頂點數(shù)為n，有向完全圖，有向完全圖的弧數(shù)：的弧數(shù)： e=Pn2 =n(n 1)l 例如，無向圖例如，無向圖G1就是就是4個頂點無向完全圖。個頂點無向完全圖。l 若一個圖接近完全圖，則稱其為若一個圖接近完全圖，則稱其為；反之，若一個圖含；反之，若一個圖含有很少條邊或?。从泻苌贄l邊或?。磂n2），則稱其為），則稱其為。l 若有圖若有圖G=(V, E)和和G=(V, E) l 且且V 是是V的子集，即的子集，即V V ， E是是E的子集，即的子集，即 E El 則稱圖則稱圖G為圖為圖G的子圖。的子圖。 5路徑、回路和

7、路徑長度路徑、回路和路徑長度l 在無向圖在無向圖G中，若存在一個頂點序列中，若存在一個頂點序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均為圖均為圖G的邊，則該稱頂?shù)倪?，則該稱頂點的序列為頂點點的序列為頂點Vp到頂點到頂點Vq的的路徑路徑。若。若G是有向圖，則路徑是有向圖，則路徑是有向的。是有向的。l 路徑長度路徑長度定義為路徑上的邊數(shù)或者弧的數(shù)目。定義為路徑上的邊數(shù)或者弧的數(shù)目。l 若一條路徑中不出現(xiàn)重復(fù)頂點，則稱此路徑為若一條路徑中不出現(xiàn)重復(fù)頂點，則稱此路徑為簡單路徑簡單路徑。l 若一條路徑的起點和終點相同（

8、若一條路徑的起點和終點相同（Vp=Vq）稱為）稱為回路回路或或環(huán)環(huán)。l 除了起點和終點相同外，其余頂點不相同的回路，稱為除了起點和終點相同外，其余頂點不相同的回路，稱為簡單簡單回路回路或或簡單環(huán)簡單環(huán)。l 例如，在無向圖例如，在無向圖G1中：中：頂點序列（頂點序列（V1, V2, V3, V4）是一條從頂點）是一條從頂點V1到頂點到頂點V4，長度為，長度為3的的簡單路徑簡單路徑；頂點序列（頂點序列（V1, V2, V4, V1, V3）是一條從頂點）是一條從頂點V1到到頂點頂點V3，長度為，長度為4的的路徑路徑，但不是簡單路徑；，但不是簡單路徑；頂點序列（頂點序列（V1, V2, V3, V1

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

10、連通分量。任何連通圖的連通分量只有一個，即其自身，而非連通圖有任何連通圖的連通分量只有一個，即其自身，而非連通圖有多個連通分量。多個連通分量。在一個連通圖中，在一個連通圖中，含有全部頂點的極小含有全部頂點的極小(邊數(shù)最少邊數(shù)最少)連通子圖連通子圖，稱為該連通圖的稱為該連通圖的生成樹生成樹。(包含圖的所有包含圖的所有 n 個結(jié)點，但只含個結(jié)點，但只含圖的圖的 n-1 條邊。在生成樹中添加一條邊之后，必定會形成回條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán)路或環(huán))l 非連通圖非連通圖G4G4A AB BC CD DE EF FG GI IJ JK KA AB BC CD DE EI IJ J

11、K KF FG Gl 圖圖G1G1和和G2G2為連通圖為連通圖l 非連通圖非連通圖G4G4的三個連通分量的三個連通分量l 連通圖連通圖G5G5A AB BC CD Dl 連通圖連通圖G5G5的兩棵生成樹的兩棵生成樹A AB BC CD DA AB BC CD D7強連通、強連通分量和強連通圖強連通、強連通分量和強連通圖l 在有向圖在有向圖G中：中：存在從頂點存在從頂點Vi 到頂點到頂點Vj的路徑，也存在從頂點的路徑，也存在從頂點Vj 到頂點到頂點Vi的路徑，則稱的路徑，則稱Vi與與Vj是是強連通強連通的。的。如果圖中任意兩個頂點都是強連通，則稱如果圖中任意兩個頂點都是強連通，則稱G為為強連通圖

12、強連通圖，否則稱為否則稱為非強連通圖。非強連通圖。在非強連通圖在非強連通圖G中，任何一個中，任何一個極大強連通子圖極大強連通子圖稱為稱為G的的強連強連通分量通分量。任何強連通圖的強連通分量只有一個，即其自身，而非強任何強連通圖的強連通分量只有一個，即其自身，而非強連通圖有多個強連通分量。連通圖有多個強連通分量。有向圖有向圖G G和強連通分量示例：和強連通分量示例： 8權(quán)、帶權(quán)圖、有向網(wǎng)和無向網(wǎng)權(quán)、帶權(quán)圖、有向網(wǎng)和無向網(wǎng)l 在一個圖中，各邊在一個圖中，各邊(或弧或弧)上可以帶一個數(shù)值，這個數(shù)值稱為上可以帶一個數(shù)值，這個數(shù)值稱為權(quán)權(quán)。l 這種每條邊都帶權(quán)的圖稱為這種每條邊都帶權(quán)的圖稱為8.2 圖的

13、基本存儲結(jié)構(gòu)圖的基本存儲結(jié)構(gòu) V V0 0 V V4 4 V V3 3 V V1 1 V V2 2 V V0 0 V V1 1 V V2 2 V V3 3a ij=0 vi與與vj無邊無邊1 vi與與vj有邊有邊a ij=0 vi到到vj無弧無弧1 vi到到vj有弧有弧a ij=或或0 vi與與vj無邊（或無邊（或vi到到vj無?。o?。﹚ vi與與vj有邊（或有邊（或vi到到vj有?。┯谢。￤ 表示邊上的權(quán)值；表示邊上的權(quán)值； 0 表示表示vi與與vj是同一個頂點是同一個頂點 表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。 鄰接矩陣表示鄰接矩陣表示0

14、 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0V1V2 V4 V5 V3 V1V2 V4 V5 V3 254311鄰接矩陣表示鄰接矩陣表示0 2 4 2 0 1 5 1 0 3 1 4 3 0 5 1 0 V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2 V3 V4 0 1 1 00 0 0 00 0 0 11 0 0 0鄰接矩陣表示鄰接矩陣表示V1V2V3V4V1V2V3V4 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。

15、有邊（?。?、找頂點的鄰接點等等。 n n個頂點需要個頂點需要n n* *n n個單元存儲邊個單元存儲邊( (弧弧););空間效率為空間效率為O(nO(n2 2) )。 對稀疏圖而言尤其浪費空間。對稀疏圖而言尤其浪費空間。鄰接矩陣法鄰接矩陣法優(yōu)點：優(yōu)點：鄰接矩陣法鄰接矩陣法缺點：缺點：2、鄰接矩陣法、鄰接矩陣法特點特點# define MAX 100 /* MAX為圖中頂點最多個數(shù)為圖中頂點最多個數(shù) */typedef int vextype; /* vextype為頂點的數(shù)據(jù)類型為頂點的數(shù)據(jù)類型 */typedef struct vextype vexMAX; /* 一維數(shù)組存儲頂點信息一維數(shù)

16、組存儲頂點信息 */ int arcMAXMAX; /*鄰接矩陣存儲邊（弧）信息鄰接矩陣存儲邊（?。┬畔?*/ int vn, en; /* vn頂點數(shù)和頂點數(shù)和en邊數(shù)邊數(shù) */MGraph; /* 圖類型圖類型 */注：注：MGraph 既可以表示有向圖、無向圖，也可以表示有既可以表示有向圖、無向圖，也可以表示有整型權(quán)的網(wǎng)整型權(quán)的網(wǎng)例：建一個如圖所示的無向圖例：建一個如圖所示的無向圖013420 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0void CreateGraph(MGraph *g) int i, j, v, e; scanf(%d %d

17、, &g-vn, &g-en); /*輸入頂點數(shù)和邊數(shù)輸入頂點數(shù)和邊數(shù)*/ for(v=0;vvn;v+) scanf(%d, &g-vexv); /*頂點數(shù)據(jù)輸入頂點數(shù)據(jù)輸入*/ for(i=0;ivn;i+) for(j=0;jvn;j+) g-arcij=0; /*鄰接矩陣的初始值都為鄰接矩陣的初始值都為0*/ for(e=0;een;e+) /*共有共有g(shù)-en條邊條邊*/ scanf(%d %d, &i, &j); /*指明有邊的兩個頂點的序號指明有邊的兩個頂點的序號*/ g-arcij=1; /*有邊賦值為有邊賦值為1*/ g-arcji=1; /*建有向圖時此句不要建有向圖時此句

18、不要*/ 鄰接表表示鄰接表表示V1V2 V4 V5 V3 V1V2 V4 V5 V3 254311鄰接表表示鄰接表表示V1V2V3V4V501234130420212143V1V2V3V4V501234123402452111413304231521與頂點與頂點V1相鄰接的頂點相鄰接的頂點在數(shù)組中的下標(biāo)在數(shù)組中的下標(biāo)權(quán)值權(quán)值V1V2 V3 V4 鄰接表表示鄰接表表示12V1V2V3V4012330以頂點以頂點V1為始點的弧的終點為始點的弧的終點頂點在數(shù)組中的下標(biāo)頂點在數(shù)組中的下標(biāo)鄰接表的鄰接表的缺點：缺點：鄰接表的鄰接表的優(yōu)點：優(yōu)點：空間效率高；空間效率高；容易尋找頂點的鄰接點；容易尋找頂點的

19、鄰接點；判斷任意兩頂點間是否有邊或弧，需搜判斷任意兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。方便。2、鄰接表法、鄰接表法特點特點adjvexnext表結(jié)點：表結(jié)點：adjvexnextw鄰接點序號鄰接點序號(下標(biāo)下標(biāo))下一個鄰接下一個鄰接點地址點地址權(quán)值權(quán)值表結(jié)點類型表結(jié)點類型vertexfirstarc頂點結(jié)點：頂點結(jié)點：頂點信息頂點信息鏈表頭指針鏈表頭指針(指向第一個表結(jié)點指向第一個表結(jié)點)頂點結(jié)點類型頂點結(jié)點類型頂點結(jié)點所在數(shù)組頂點結(jié)點所在數(shù)組例：建一個如圖所示的有向圖例：建一個如圖所示的有向圖01 2 3120123012330

20、void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(%d %d, &g-vn, &g-en); /*輸入頂點數(shù)和邊數(shù)輸入頂點數(shù)和邊數(shù)*/ for(v=0;vvn;v+) /*頂點數(shù)組元素值的獲得頂點數(shù)組元素值的獲得*/ scanf(%d,&g-adjlistv.vertex); /*頂點數(shù)據(jù)鍵盤輸入頂點數(shù)據(jù)鍵盤輸入*/ g-adjlistv.firstarc=NULL; for(e=0;een;e+) /*共有共有g(shù)-en條邊條邊*/ scanf(%d %d, &i, &j); /*i j有弧，有弧，i、j為頂點序號為

21、頂點序號*/ p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; /*把值為把值為j的結(jié)點頭插入到的結(jié)點頭插入到i頂點的鏈表中頂點的鏈表中*/ p-next=g-adjlisti.firstarc; g-adjlisti.firstarc=p; 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有向圖的

22、逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧 8.3 圖的遍歷圖的遍歷 從圖中某個頂點出發(fā)遍歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。圖的遍歷有兩種方法： 深度優(yōu)先搜索遍歷（DFS） 廣度優(yōu)先搜索遍歷（BFS）。它們對無向圖和有向圖都適用。 8.3.1 連通圖的深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷l 首先訪問初始出發(fā)點首先訪問初始出發(fā)點V V0 0，并將其標(biāo)記設(shè)置為已訪問；，并將其標(biāo)記設(shè)置為已訪問；l 然后任選一個與然后任選一個與V V0 0相鄰接且沒有被訪問的鄰接點相鄰接且沒有被訪問的鄰

23、接點V V1 1作為新的作為新的出發(fā)點，訪問出發(fā)點，訪問V V1 1之后，將其標(biāo)記設(shè)置為已訪問；之后，將其標(biāo)記設(shè)置為已訪問；l 再以再以V V1 1為新的出發(fā)點，繼續(xù)進(jìn)行深度優(yōu)先搜索，訪問與為新的出發(fā)點，繼續(xù)進(jìn)行深度優(yōu)先搜索，訪問與V V1 1相相鄰接且沒有被訪問的任一個頂點鄰接且沒有被訪問的任一個頂點V V2 2；l 重復(fù)上述過程，若遇到一個所有鄰接點均被訪問過的頂點，重復(fù)上述過程，若遇到一個所有鄰接點均被訪問過的頂點，則回到已訪問頂點序列中最后一個還存在未被訪問的鄰接點則回到已訪問頂點序列中最后一個還存在未被訪問的鄰接點的頂點，再從該頂點出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中的頂點，再從該頂點

24、出發(fā)繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中所有頂點都被訪問過，搜索結(jié)束。所有頂點都被訪問過，搜索結(jié)束。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4例例l序列序列1： V0,V1,V3,V7,V4,V2,V5,V6l從從v0出發(fā)的出發(fā)的DFS序列為：序列為：由于沒有規(guī)定由于沒有規(guī)定訪問鄰接點的順序，訪問鄰接點的順序，DFSDFS序列不是唯一的序列不是唯一的l序列序列2： V0,V1,V4,V7,V3,V2,V5,V6算法描述：算法描述： 訪問開始頂點（如訪問開始頂點（如 v）；）； 尋找尋

25、找 v 頂點未被訪問的第一個鄰接頂點（如頂點未被訪問的第一個鄰接頂點（如 w）；）； 并把并把 w 作為開始頂點繼續(xù)深度優(yōu)先搜索遍歷（遞歸思想）；作為開始頂點繼續(xù)深度優(yōu)先搜索遍歷（遞歸思想）； 直到所有頂點被訪問；直到所有頂點被訪問； 其中處理：其中處理：（1）訪問頂點：自定義訪問函數(shù)）訪問頂點：自定義訪問函數(shù) visit()（2）未被訪問的鄰接點：定義一個標(biāo)記數(shù)組：）未被訪問的鄰接點：定義一個標(biāo)記數(shù)組：int visitedMAX visitedi= 0 i號頂點號頂點未未被訪問被訪問 1 i號頂點號頂點已已被訪問被訪問 注意：由于函數(shù)是遞歸的，數(shù)組定義成外部數(shù)組注意：由于函數(shù)是遞歸的，數(shù)組

26、定義成外部數(shù)組 （3）第一個鄰接點：按鄰接距陣或鄰接表中邊存儲的順序）第一個鄰接點：按鄰接距陣或鄰接表中邊存儲的順序 函數(shù)實現(xiàn)：函數(shù)實現(xiàn)：形參：形參：圖變量地址，開始頂點的序號（下標(biāo)）圖變量地址，開始頂點的序號（下標(biāo)）返回值：返回值：無無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號頂點號

27、頂點 間有邊，且間有邊，且j號頂點為被訪問號頂點為被訪問*/ w=j; dfs(g, w); 鄰接距陣存儲結(jié)構(gòu)的圖鄰接距陣存儲結(jié)構(gòu)的圖起始頂點的序號（下標(biāo)）起始頂點的序號（下標(biāo)）void visit (MGraph *g, int v) printf(n %d, g-vexv); 按算法實現(xiàn)的按算法實現(xiàn)的dfs遍歷舉例：遍歷舉例：V0頂點出發(fā)遍歷結(jié)果（唯一）頂點出發(fā)遍歷結(jié)果（唯一） ：V0、 V1、 V2、 V3、 V4V2頂點出發(fā)遍歷結(jié)果（唯一）頂點出發(fā)遍歷結(jié)果（唯一） ：V2、 V1、 V0、 V4、 V3V0V1V2V3V4無向圖：無向圖：010111011001010111011001

28、0鄰接矩陣存儲結(jié)構(gòu)：鄰接矩陣存儲結(jié)構(gòu)：V0V1V2V3V401234設(shè)計程序創(chuàng)建鄰接矩陣的無向圖，并用設(shè)計程序創(chuàng)建鄰接矩陣的無向圖，并用dfsdfs圖中頂點圖中頂點信息并輸出：信息并輸出：宏定義及數(shù)據(jù)類型：宏定義及數(shù)據(jù)類型：#include #define MAX 20 /*圖頂點最多不超過圖頂點最多不超過20*/typedef int vextype; /*圖頂點為圖頂點為int型型*/typedef struct vextype vexMAX; int arcMAXMAX; int vn, en; MGraph; /*鄰接矩陣圖類型鄰接矩陣圖類型*/int visitedMAX; /*訪問

29、標(biāo)記數(shù)組訪問標(biāo)記數(shù)組*/函數(shù)定義：函數(shù)定義：void CreateGraph(MGraph *g) /*創(chuàng)建無向圖創(chuàng)建無向圖*/ void visit(MGraph *g, int v) /*訪問圖中某個頂點訪問圖中某個頂點*/ void dfs(MGraph *g, int v) /*dfs遍歷圖遍歷圖*/ main() /*主函數(shù)主函數(shù)*/ MGraph mg; /*mg為圖結(jié)構(gòu)變量為圖結(jié)構(gòu)變量/ int i, start; /*start開始頂點序號開始頂點序號*/ CreateGraph(&mg); for(i=0; iadjlistw.firstarc; /*w號頂點的第一個鄰接點地

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

31、歷結(jié)果（唯一）頂點出發(fā)遍歷結(jié)果（唯一） ：V2、 V3、 V1、 V4、 V0V0V1V2V3V4無向圖：無向圖：鄰接表存儲結(jié)構(gòu)：鄰接表存儲結(jié)構(gòu)：V0V1V2V3V4012341403312403設(shè)計程序創(chuàng)建鄰接表存儲的無向圖，并用設(shè)計程序創(chuàng)建鄰接表存儲的無向圖，并用bfsbfs圖中頂圖中頂點信息并輸出：點信息并輸出：宏定義及數(shù)據(jù)類型：宏定義及數(shù)據(jù)類型：#include #include Queue.h /*循環(huán)隊列相關(guān)操作的定義文件循環(huán)隊列相關(guān)操作的定義文件*/#define MAX 20 /*圖頂點最多不超過圖頂點最多不超過20*/typedef int vextype; /*圖頂點為圖頂

32、點為int型型*/typedef struct arcnode int adjvex; struct arcnode *next; ArcNode; /*表結(jié)點類型表結(jié)點類型*/typedef struct vexnode vextype vertex;ArcNode *firstarc; VexNode; /*頂點結(jié)點類型頂點結(jié)點類型*/typedef struct VexNode adjlistMAX; /*頂點結(jié)點所在數(shù)組頂點結(jié)點所在數(shù)組*/ int vn, en; ALGraph; /*鄰接表存儲的圖類型鄰接表存儲的圖類型*/int visitedMAX; /*訪問標(biāo)記數(shù)組訪問標(biāo)記數(shù)組

33、*/函數(shù)定義：函數(shù)定義：void CreateGraph(ALGraph *g) /*創(chuàng)建圖創(chuàng)建圖*/ void visit(MGraph *g, int v) /*訪問圖中某個頂點訪問圖中某個頂點*/ void bfs(MGraph *g, int v) /*bfs遍歷圖遍歷圖*/ main() /*主函數(shù)主函數(shù)*/ ALGraph alg; /*mg為鄰接表圖結(jié)構(gòu)變量為鄰接表圖結(jié)構(gòu)變量/ int i, start; /*start開始頂點序號開始頂點序號*/ CreateGraph(&alg); for(i=0; ialg.vn; i+) /*訪問標(biāo)記數(shù)組置初值訪問標(biāo)記數(shù)組置初值0*/ v

34、isitedi=0; scanf(%d, &start); bfs(&alg, start);l關(guān)于遍歷小結(jié)：關(guān)于遍歷小結(jié)：若圖是連通的或強連通的，則從圖中某一個若圖是連通的或強連通的，則從圖中某一個頂點出發(fā)可以訪問到圖中所有頂點；頂點出發(fā)可以訪問到圖中所有頂點；若圖是非連通的或非強連通圖，則需從圖中若圖是非連通的或非強連通圖，則需從圖中多個頂點出發(fā)搜索訪問，而每一次從一個新多個頂點出發(fā)搜索訪問，而每一次從一個新的起始點出發(fā)進(jìn)行搜索過程中得到的頂點訪的起始點出發(fā)進(jìn)行搜索過程中得到的頂點訪問序列恰為每個連通分量中的頂點集。問序列恰為每個連通分量中的頂點集。問題：如何通過遍歷算法，求一個非連通圖的

35、連問題：如何通過遍歷算法，求一個非連通圖的連同分量個數(shù)？同分量個數(shù)？int count (MGraph *g) int i, m=0; for(i=0; ivn; i+) if(visitedi=0) m+; dfs(g, i); return m; 生成樹定義生成樹定義l圖的遍歷過程中經(jīng)過的圖的遍歷過程中經(jīng)過的n個頂點個頂點n-1條邊條邊即為一即為一棵生成樹?？蒙蓸?。8.4 圖的應(yīng)用圖的應(yīng)用8.4.1 連通圖的最小生成樹連通圖的最小生成樹無向圖的應(yīng)用無向圖的應(yīng)用在無向連通圖在無向連通圖G G中，其一個極小連通子圖中，其一個極小連通子圖( (無回?zé)o回路路) )是是G G的生成樹，它含有圖中全

36、部的生成樹，它含有圖中全部n n個頂點個頂點，但，但只有只有n-1n-1條邊條邊，且不唯一。，且不唯一。深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的生成樹生成樹c0c1c3c2c4c5例例c0c1c3c2c4c5c0c1c3c2c4c5c0c1c3c2c4c5廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的生成樹生成樹非連通圖的生成森林非連通圖的生成森林V0V1V3V4V2V6V8V7V5V9（a）不連通的無向圖）不連通的無向圖G12V0V1V3V4V2V8V7V9V6V5（c）圖）圖G12的一個的一個BFS生成森林生成森林V0V1V3V4V

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

38、是連通圖的最小生成樹問這個問題實際上是連通圖的最小生成樹問題。題。ABCDEF1010151212876655ABCDEF107610最小生成樹的定義最小生成樹的定義若圖若圖G G是帶權(quán)的無向連通圖（連通網(wǎng)），生成樹上各是帶權(quán)的無向連通圖（連通網(wǎng)），生成樹上各邊權(quán)值之和稱為生成樹的代價，邊權(quán)值之和稱為生成樹的代價，代價最小的生成樹代價最小的生成樹稱為最小生成樹；稱為最小生成樹；ln n個頂點、個頂點、n-1n-1條邊、權(quán)值之和最小。條邊、權(quán)值之和最小。1654327131791812752410連通網(wǎng)：連通網(wǎng)：1654321397510生成樹生成樹1：1654327139724生成樹生成樹2：

39、代價：代價：44代價：代價：60最小生成樹最小生成樹最小生成樹的應(yīng)用最小生成樹的應(yīng)用l集成電路布線集成電路布線l通訊線路布線通訊線路布線如何快速有效地構(gòu)造如何快速有效地構(gòu)造最小生成樹最小生成樹 構(gòu)造最小生成樹的準(zhǔn)則：構(gòu)造最小生成樹的準(zhǔn)則：l必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；l必須使用且僅使用必須使用且僅使用n-1條邊來聯(lián)接網(wǎng)絡(luò)中的條邊來聯(lián)接網(wǎng)絡(luò)中的n個頂點個頂點一、一、Prim(普里姆普里姆)算法算法 1 1、算法思想、算法思想 設(shè)原連通網(wǎng)設(shè)原連通網(wǎng)G=(V, E)G=(V, E)，生成的最小生成樹，生成的最小生成樹T=(U, T=(U, TE)T

40、E)，則算法步驟如下：，則算法步驟如下：(1)(1)任選一個頂點任選一個頂點u u0 0放入放入U U中，即初始中，即初始U=uU=u0 0 ，TE= TE= (2)(2)找連接找連接U U與與V-UV-U集合的一條權(quán)值最小的邊集合的一條權(quán)值最小的邊即找即找頂點頂點uU,uU,頂點頂點vV-UvV-U的權(quán)值最小的一條邊的權(quán)值最小的一條邊(u,v)E(u,v)E；并把頂點并把頂點v v加入到加入到U U中，邊中，邊(u,v) (u,v) 加入到加入到TETE中，中，即修改即修改U=U+v,TE=TE+(u,v)U=U+v,TE=TE+(u,v)(3)(3)轉(zhuǎn)到（轉(zhuǎn)到（2 2）重復(fù)執(zhí)行，直到）重復(fù)

41、執(zhí)行，直到U=VU=V結(jié)束結(jié)束ABCDEF101015121287665（a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹BCE101512（b）求解過程）求解過程67ABCDEF1010151212865（a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CDEF101512765（b）求解過程）求解過程ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CDEF1015765（b）求解過程）求解過程6ABCDEF10101512128765 （

42、a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CEF1015765（b）求解過程）求解過程6ABCDEF10101512128765 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CEF10157665（b）求解過程）求解過程ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CE1015765（b）求解過程）求解過程ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小

43、生成樹CE1015765（b）求解過程）求解過程86ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹CE10101575（b）求解過程）求解過程6ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹E101075（b）求解過程）求解過程1567ABCDEF101015121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹E1010125（b）求解過程）求解過程67ABCDEF10101

44、5121287665 （a）無向網(wǎng)）無向網(wǎng)G1算法演示算法演示:Prim算法求解最小生成樹算法求解最小生成樹最小生成樹最小生成樹E10105例1654326513566425131163141643142116432142516543214253Prim算法最小生成樹生成過程事例算法最小生成樹生成過程事例(從從1號頂點開始號頂點開始) 課堂練習(xí)：寫出如下連通網(wǎng)的最小生成樹過程課堂練習(xí)：寫出如下連通網(wǎng)的最小生成樹過程165432496102014510106165432495106最小生成樹最小生成樹1165432495106最小生成樹最小生成樹2最小生成樹最小生成樹不唯一！不唯一！i01234

45、5di.adj000000di.dist 01 58 定義一個結(jié)構(gòu)數(shù)組：定義一個結(jié)構(gòu)數(shù)組：struct cost int adj; int dist;d20;2 2、算法實現(xiàn)、算法實現(xiàn) 02315451839762說明：說明：i i數(shù)組下標(biāo)，又是圖中對應(yīng)數(shù)組下標(biāo)，又是圖中對應(yīng)頂點的序號頂點的序號di.adjdi.adj表示表示i i號頂點號頂點與生成樹中頂點集合與生成樹中頂點集合U U距離距離最小最小的的頂點頂點號（號（u u）di.distdi.dist表示表示i i號頂點號頂點與生成樹中與生成樹中adjadj頂點（頂點（u u號頂點號頂點）的）的距距離離，當(dāng)，當(dāng)dist=0dist=0時表

46、示時表示i i號頂點已到生成樹中。號頂點已到生成樹中。生成樹初始生成樹初始 選選0號頂點號頂點2 2、算法實現(xiàn)、算法實現(xiàn) i012345di.adj000000di.dist 01 58 02315451839762(1)(1)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=0, v=1,w=1送入生成樹，送入生成樹，其頂點集為：其頂點集為：0,1，并修改數(shù)組，并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj011000di.dist 002 58 生成樹初始生成樹初始 選選0號頂點號頂點uvw(2)(2)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值

47、，則把u=1, v=2,w=2送入生成樹送入生成樹，其頂點集為：其頂點集為：0,1,20,1,2，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj011000di.dist 002 58 i012345di.adj012202di.dist 0007 56 i012345di.adj012202di.dist 0007 56 (3)(3)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=0, v=4,w=5送入生成樹送入生成樹，其頂點集為：其頂點集為：0,1,2,40,1,2,4，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj012442di.d

48、ist 0003 06 (4)(4)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=4, v=3,w=3送入生成樹送入生成樹，其頂點集為：其頂點集為：0,1,2,4,30,1,2,4,3，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj012442di.dist 0003 06 i012345di.adj012342di.dist 0000 06 i012345di.adj012342di.dist 0000 06 (5)(5)取取d d數(shù)組中數(shù)組中distdist0的最小值，則把的最小值，則把u=2, v=5,w=6送入生成樹送入生成樹，其頂點集為：其頂點

49、集為：0,1,2,4,3,50,1,2,4,3,5，并修改數(shù)組并修改數(shù)組d的內(nèi)容的內(nèi)容i012345di.adj012345di.dist 0000 00 無向網(wǎng)的建立：無向網(wǎng)的建立： #include #define INF 32767typedef 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ù)據(jù)文件*/ /*圖的頂點數(shù)

50、和邊數(shù)、頂點數(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ù)）：無向網(wǎng)的建立（續(xù)）： for(i=0;ivn;i+) g-vexi=A+i; /*頂點數(shù)據(jù)為頂點數(shù)據(jù)為A、B、C*/ for(e=0;een;e+) /*從文件讀取對應(yīng)邊信息，即有邊

51、的頂點序號及權(quán)值從文件讀取對應(yīng)邊信息，即有邊的頂點序號及權(quán)值*/ fscanf(fp, %d %d %d, &i,&j,&w)； g-arcij=w; g-arcji=w; fclose(fp); /*關(guān)閉文件關(guān)閉文件*/ /*結(jié)束函數(shù)結(jié)束函數(shù)*/0968035930767022018510文件文件graph.dat中中的內(nèi)容為：的內(nèi)容為：6 80 1 10 4 50 5 81 2 22 3 72 5 63 4 33 5 9無向網(wǎng)鄰接距陣的輸出：無向網(wǎng)鄰接距陣的輸出： void OutGraph(MGraph *g) int i, j; printf(n-Graph-n); printf(n

52、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); 0968035930767022018510輸出：輸出：-Graph-6 8primprim算法實現(xiàn)：算法實現(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ù)組初始化數(shù)組初始化*/ di.adj=v0; di.dist=g-arcv0i;

53、for(k=0; kvn-1; k+) /*求求vn-1條生成樹的邊條生成樹的邊*/ min=INF; j=-1; for(i=0; ivn; i+) /*找權(quán)值最小的邊找權(quán)值最小的邊*/ if(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; /*修改新送入生成樹頂點的信息修改新送入生成樹頂點的信息*/primprim算法實現(xiàn)（續(xù)）：算法實現(xiàn)（續(xù)）： for(i=0; ivn; i+) /*修改數(shù)組修改數(shù)組d中數(shù)組中數(shù)組*/

54、 /*新加入到生成樹的新加入到生成樹的j頂點與頂點與i頂點邊的權(quán)值更小，則修改頂點邊的權(quán)值更小，則修改*/ if(di.dist!=0 & g-arcjiarcji; /*結(jié)束求生成樹的結(jié)束求生成樹的for */ /*結(jié)束函數(shù)結(jié)束函數(shù) */最小生成樹的輸出：最小生成樹的輸出： void OutTree(Tree E, int k) int i; printf(n spaning treen); for(i=0; ik; i+) /*生成樹生成樹E數(shù)組中有數(shù)組中有k條邊條邊*/ printf(n%c-%c-%d, Ei.u, Ei.v, Ei.w ); 輸出：輸出：spaning tree0-1

55、-1 1-2-2 0-4-5 4-3-32-5-6主函數(shù)：主函數(shù)： main( ) MGraph G; Tree E20; CreateGraph(&G); OutGraph(&G); Prim(&G,0,E); OutTree( E, G.vn-1 ); 二、二、 Kruskal（克魯斯卡爾）算法（克魯斯卡爾）算法 1 1、算法思想、算法思想 l把圖的所有邊按其權(quán)值從小到大排成升序把圖的所有邊按其權(quán)值從小到大排成升序l先把權(quán)值最小的邊加入生成樹先把權(quán)值最小的邊加入生成樹l依次選取后面的邊，如該邊加到生成樹中，使生成依次選取后面的邊，如該邊加到生成樹中，使生成樹構(gòu)成回路，則舍棄該邊，否則該邊加

56、入到生成樹樹構(gòu)成回路，則舍棄該邊，否則該邊加入到生成樹中。中。l重復(fù)上述過程，直到生成樹中包含重復(fù)上述過程，直到生成樹中包含n n 1 1條邊為止，條邊為止，此時即為最小生成樹。此時即為最小生成樹。例AFEDCB6314566425AFEDCB13254Kruskal算法最小生成樹生成過程事例：算法最小生成樹生成過程事例： AC10DF21AD32CF43BE44CD55BC56AB67CE68EF69KruskalKruskal算法練習(xí)算法練習(xí): :abcdegf195141827168213ae12dcbgf71485316217121819abcdegf195141827168213ae12dcbgf7148531621最小生成樹代價= 14+8+3+5+16+21 = 67 PrimPrim算法練習(xí)算法練習(xí): :8.4.2 拓?fù)渑判蛲負(fù)渑判蛴邢驘o環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用1、AOV網(wǎng)概念網(wǎng)概念在一個有向圖中，若用頂點表示活動，有向邊表示活動間在一個有向圖中，若用頂點表示活動，有向邊表示活動間先后關(guān)系，稱該有向圖叫做頂點活動網(wǎng)絡(luò)，簡稱為先后關(guān)系，稱該有向圖叫做頂點活動網(wǎng)絡(luò)，簡稱為AOV網(wǎng)