計(jì)算機(jī)軟件基礎(chǔ)自考本科圖

計(jì)算機(jī)軟件基礎(chǔ)第二篇數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第十一章圖一、簡單概念1.圖的定義（1）圖G：是由一個(gè)非空有窮的頂點(diǎn)集合V和一個(gè)有窮的邊（或?。┘螮組成。記作：G=（V，E）12345G=（V，E）V={1,2,3,4,5}E={(1,2),(1,4),(2,3),(2,5),(3,5)}（2）無向圖：頂點(diǎn)之間的連線不具有方向性的圖。注意：無向圖中，頂點(diǎn)之間的連線，稱為邊。一、簡單概念1.圖的定義注意：有向圖中，頂點(diǎn)之間的連線，稱為弧。（3）有向圖：頂點(diǎn)之間的連線具有方向性的圖。12345G=（V，E）V={1,2,3,4,5}E={<1,2>,<2,3>,<4,1>,<2,5>,<3,5>}一、簡單概念（1）完全無向圖：從圖中任一頂點(diǎn)到其余頂點(diǎn)，都有直接邊存在的無向圖。如：12345注意：對于具有n個(gè)頂點(diǎn)，e條邊的完全無向圖：

2.基本術(shù)語一、簡單概念（2）完全有向圖：從圖中任一頂點(diǎn)到其余頂點(diǎn)，都有直接弧存在的有向圖。如：1234注意：對于具有n個(gè)頂點(diǎn)，e條邊的完全有向圖：

一、簡單概念（3）兩頂點(diǎn)的鄰接1）對于無向圖來說，如果頂點(diǎn)Vi與Vj之間有邊，則稱頂點(diǎn)Vi與Vj互為鄰接；2）對于有向圖來說，如果頂點(diǎn)Vi到頂點(diǎn)Vj有弧，則稱頂點(diǎn)Vi和Vj是鄰接，但Vj和Vi是不鄰接的；一、簡單概念（4）頂點(diǎn)的度1）無向圖頂點(diǎn)的度，是與該頂點(diǎn)鄰接的邊的數(shù)目；2）有向圖頂點(diǎn)的度，是該頂點(diǎn)入度和出度之和；有向圖頂點(diǎn)的入度，是進(jìn)入該頂點(diǎn)弧的數(shù)目；有向圖頂點(diǎn)的出度，是遠(yuǎn)離該頂點(diǎn)弧的數(shù)目；一、簡單概念（5）簡單路徑1）路徑：對于無向圖來說，從Vi點(diǎn)到Vj點(diǎn)的邊組成的序列，稱為路徑；對于有向圖來說，從Vi點(diǎn)到Vj點(diǎn)的弧組成的有向序列，稱為路徑。2）簡單路徑：沒有重復(fù)點(diǎn)的路徑。一、簡單概念（6）簡單回路1）回路：在圖中，從某一點(diǎn)出發(fā)又回到該點(diǎn)的路徑；2）簡單回路：只有起點(diǎn)和終點(diǎn)重復(fù)，其他點(diǎn)不重復(fù)的回路。二、圖的存儲結(jié)構(gòu)1.用鄰接矩陣存儲圖（1）圖的鄰接矩陣：描述圖中兩個(gè)頂點(diǎn)之間鄰接關(guān)系的矩陣。（2）鄰接矩陣的結(jié)構(gòu)：是一個(gè)n*n階的方陣，其中的每一行或每一列對應(yīng)于圖中的一個(gè)頂點(diǎn)；一般情況下，Aij頂點(diǎn)的值如下：Aij=1：表示從頂點(diǎn)Vi到頂點(diǎn)Vj有邊（或弧）0：表示從頂點(diǎn)Vi到頂點(diǎn)Vj沒有邊（或?。┒?、圖的存儲結(jié)構(gòu)例1：寫出下列無向圖G1的鄰接矩陣12435①②③④⑤①②③④⑤0101010101010111010001100二、圖的存儲結(jié)構(gòu)例2：寫出下列有向圖G2的鄰接矩陣①②③④⑤①②③④⑤010000010100011100000000012435二、圖的存儲結(jié)構(gòu)（3）圖的鄰接矩陣的性質(zhì)：1）一個(gè)圖的鄰接矩陣是唯一的；2）鄰接矩陣中，各行非零的個(gè)數(shù)為該行所對應(yīng)頂點(diǎn)的出度；各列非零的個(gè)數(shù)為該列所對應(yīng)頂點(diǎn)的入度；3）無向圖和完全有向圖的鄰接矩陣是一個(gè)對稱的矩陣二、圖的存儲結(jié)構(gòu)（4）建立無向圖鄰接矩陣的算法：step1：輸入頂點(diǎn)的個(gè)數(shù)n和邊數(shù)e；step2：將鄰接矩陣清零；step3：分別輸入e條邊的兩個(gè)頂點(diǎn)i和j，并且令A(yù)[i][j]=1，A[j][i]=1。二、圖的存儲結(jié)構(gòu)（4）建立無向圖鄰接矩陣的算法描述：voidcreat(G,A[][n+1],n,e){scanf("%d","%d",&n,&e);//輸入圖的頂點(diǎn)數(shù)和邊數(shù)for(i=1;i<=n;i++)//將矩陣清零for(j=1;j<=n;j++)A[i][j]=0;for(k=1;k<=e;k++)//分別輸入e條邊的兩個(gè)頂點(diǎn){ scanf("%d","%d",&i,&j) A[i][j]=1; A[j][i]=1;}}二、圖的存儲結(jié)構(gòu)例：（09.4）設(shè)二維數(shù)組A[3][3]表示3節(jié)點(diǎn)無向圖的鄰接矩陣。編寫程序，從鍵盤上輸入鄰接矩陣的數(shù)據(jù)，求出該無向圖的邊數(shù)以及各個(gè)節(jié)點(diǎn)的度數(shù)，并輸出所求結(jié)果。123二、圖的存儲結(jié)構(gòu)解：#include<stdio.h>main(){inta[3][3],i,j,b,s;//b：累積節(jié)點(diǎn)的度；s：累積無向圖的度s=0;for(i=0;i<3;i++)//輸入鄰接矩陣的數(shù)據(jù)for(j=0;j<3;j++)scanf("%d",&a[i][j]);for(i=0;i<3;i++)//求各節(jié)點(diǎn)的度以及圖的度{b=0;for(j=0;j<3;j++)if(a[i][j]==1)b=b+1;printf("Thedegreeofnode%d:%d\n",i,b);s=s+b;}printf("Thesumofedgeis:%d\n",s/2);//輸出圖的邊數(shù)}二、圖的存儲結(jié)構(gòu)2.用鄰接鏈表存儲圖（1）圖的鄰接鏈表：又稱為鄰接表，由n個(gè)單鏈表組成，每一個(gè)單鏈表又由表頭節(jié)點(diǎn)和表節(jié)點(diǎn)兩部分構(gòu)成。1)表頭節(jié)點(diǎn)：對應(yīng)于圖中的一個(gè)節(jié)點(diǎn)；2)表節(jié)點(diǎn)：表頭節(jié)點(diǎn)所代表頂點(diǎn)的所有鄰接點(diǎn)。二、圖的存儲結(jié)構(gòu)例如：12435V1V3V4V2V5V2V2V1V1V2V4V3V4V3V3V5V5表頭節(jié)點(diǎn)表節(jié)點(diǎn)二、圖的存儲結(jié)構(gòu)（2）圖的鄰接表的性質(zhì)1)一個(gè)圖的鄰接表不是唯一的；2)在無向圖的鄰接表中，各單鏈表表節(jié)點(diǎn)的個(gè)數(shù)為對應(yīng)表頭節(jié)點(diǎn)（頂點(diǎn)）的度；在有向圖的鄰接表中，各單鏈表表節(jié)點(diǎn)的個(gè)數(shù)為對應(yīng)表頭節(jié)點(diǎn)（頂點(diǎn)）的出度。三、圖的遍歷1.圖的遍歷2.深度優(yōu)先遍歷深度遍歷；訪問圖中各節(jié)點(diǎn)的過程。口訣：小號優(yōu)先；刨根問底。3.廣度優(yōu)先遍歷廣度遍歷；口訣：小號優(yōu)先；橫掃四周。三、圖的遍歷例1：（2010.4）如下圖所示的無向圖，分別按鄰接頂點(diǎn)序號由小到大順序給出廣度優(yōu)先遍歷和深度優(yōu)先遍歷的頂點(diǎn)序列。解：廣度優(yōu)先遍歷深度優(yōu)先遍歷1372456三、圖的遍歷例2：（2008.4）對于下圖解：廣度優(yōu)先遍歷:（1）從頂點(diǎn)1出發(fā)，按鄰接頂點(diǎn)序號由小到大的順序給出廣度優(yōu)先遍歷的頂點(diǎn)序列。1372456四、最小生成樹——無向圖的應(yīng)用1.相關(guān)概念（1）連通圖：從圖中任意一點(diǎn)出發(fā)，都能直接或間接到達(dá)其余點(diǎn)的圖。1234567四、最小生成樹——無向圖的應(yīng)用1.相關(guān)概念（2）子圖：如果圖G1的所有頂點(diǎn)和邊完全被圖G包含，則稱圖G1為圖G的子圖。（3）圖的連通分量：是指所研究圖的最大的連通的子圖。注意：對于連通圖來說，其連通分量就是它本身。15234124123415234四、最小生成樹——無向圖的應(yīng)用2.圖的最小生成樹（1）圖的生成樹：指該圖最小的連通的子圖。1）“最小”的含義：一個(gè)圖的生成樹有n個(gè)頂點(diǎn)，n-1條邊，如果多一條邊將使生成樹產(chǎn)生回路，少一條邊將使生成樹不連通2）連通圖的必要條件：一個(gè)連通圖，具有n個(gè)頂點(diǎn)，則至少有n-1條邊。四、最小生成樹——無向圖的應(yīng)用例如：圖a的部分生成樹如b所示12435124351243512435結(jié)論：一個(gè)圖，可以

生成多棵樹。四、最小生成樹——無向圖的應(yīng)用（2）最小生成樹：各邊權(quán)值之和為最小的生成樹。（3）求最小生成樹的方法——克魯斯卡爾法口訣：權(quán)值升序選邊；包含所有頂點(diǎn)；禁止產(chǎn)生回路。確保樹木連通。四、最小生成樹——無向圖的應(yīng)用例：（2008.4）對于下圖（2）給出克魯斯卡爾法構(gòu)造的最小生成樹。13724566718423251215851020761816451248325四、最小生成樹——無向圖的應(yīng)用例11-4下圖表示一個(gè)貧困地區(qū)的位置示意圖，頂點(diǎn)表示貧困縣，邊上的權(quán)值表示各個(gè)縣之間的里程，假設(shè)修路的單位造價(jià)相同，問如何修路造價(jià)最低。181643521519281014848161643521510841616435215104816五、拓?fù)渑判颉邢驁D的應(yīng)用1.有關(guān)名詞（1）AOV網(wǎng)絡(luò)圖：又稱為頂點(diǎn)活動網(wǎng)，是指用頂點(diǎn)表征各項(xiàng)活動、邊表征活動發(fā)生先后順序的有向圖。（2）拓?fù)湫蛄校河葾OV網(wǎng)構(gòu)造的線性序列。（3）拓?fù)渑判颍簶?gòu)造拓?fù)湫蛄械倪^程。五、拓?fù)渑判颉邢驁D的應(yīng)用2.構(gòu)造拓?fù)湫蛄械牟襟Estep1:輸出入度為零的節(jié)點(diǎn)；step2:劃去從該節(jié)點(diǎn)引出的所有箭線；step3:重復(fù)step1~step2，直到輸出完最后一個(gè)節(jié)點(diǎn)。五、拓?fù)渑判颉邢驁D的應(yīng)用例：（09.4）寫出下列AOV網(wǎng)的所有拓?fù)渑判蛐蛄?165432step1:輸出入度為零的節(jié)點(diǎn)；step2:劃去從該節(jié)點(diǎn)引出的所有箭線；五、拓?fù)渑判颉邢驁D的應(yīng)用表11-1是某工廠機(jī)床檢修工序示例順序號工序代號工序名稱緊前工序1A拆卸無2B機(jī)件檢查A3C電器檢查A4D零件修復(fù)B5E零件加工B6F組裝C、D、E7G試車FEA