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

1、1. 圖的定義圖的定義（1）圖）圖G：是由一個非空有窮的頂點集合：是由一個非空有窮的頂點集合V和一個有和一個有窮的邊（或?。┘细F的邊（或?。┘螮組成。記作：組成。記作： G=（V，E）G=（V，E）V=1,2,3,4,5E=(1,2),(1,4),(2,3),(2,5),(3,5)（2）無向圖：頂點之間的連線不具有方向性的圖。）無向圖：頂點之間的連線不具有方向性的圖。注意：注意：無向圖中，頂點之間的連線，稱為邊。無向圖中，頂點之間的連線，稱為邊。1. 圖的定義圖的定義注意：注意：有向圖中，頂點之間的連線，稱為弧。有向圖中，頂點之間的連線，稱為弧。（3）有向圖：頂點之間的連線具有方向性的圖。

2、）有向圖：頂點之間的連線具有方向性的圖。G=（V，E）V=1,2,3,4,5E=,（1）完全無向圖：從圖中任一頂點到其余頂點，都）完全無向圖：從圖中任一頂點到其余頂點，都有有直接直接邊存在的無向圖。如：邊存在的無向圖。如：注意：注意：對于具有對于具有n個頂點，個頂點，e條邊的完全無向圖：條邊的完全無向圖： 2. 基本術(shù)語基本術(shù)語)n(ne121（2）完全有向圖：從圖中任一頂點到其余頂點，都）完全有向圖：從圖中任一頂點到其余頂點，都有有直接直接弧存在的有向圖。如：弧存在的有向圖。如：注意：注意：對于具有對于具有n個頂點，個頂點，e條邊的完全有向圖：條邊的完全有向圖： )n(ne1（3）兩頂點的鄰

3、接）兩頂點的鄰接 1）對于無向圖來說，如果頂點）對于無向圖來說，如果頂點Vi與與Vj之間有邊，之間有邊，則稱頂點則稱頂點Vi與與Vj互為鄰接；互為鄰接； 2）對于有向圖來說，如果頂點）對于有向圖來說，如果頂點Vi到頂點到頂點Vj有弧，有弧，則稱頂點則稱頂點Vi和和Vj是鄰接，但是鄰接，但VjVi；（4）頂點的度）頂點的度1）無向圖頂點的度，是與該頂點鄰接的邊的數(shù)目；）無向圖頂點的度，是與該頂點鄰接的邊的數(shù)目；2）有向圖頂點的度，是該頂點入度和出度之和；）有向圖頂點的度，是該頂點入度和出度之和；有向圖頂點的入度，是進入該頂點弧的數(shù)目；有向圖頂點的入度，是進入該頂點弧的數(shù)目；有向圖頂點的出度，是遠

4、離該頂點弧的數(shù)目；有向圖頂點的出度，是遠離該頂點弧的數(shù)目；（5）簡單路徑）簡單路徑1）路徑：）路徑： 對于無向圖來說，從對于無向圖來說，從Vi點到點到Vj點的點的邊邊組成的組成的序列序列，稱為路徑；稱為路徑； 對于有向圖來說，從對于有向圖來說，從Vi點到點到Vj點的點的弧弧組成的組成的有向有向序列序列，稱為路徑。，稱為路徑。2）簡單路徑：沒有重復(fù)點的路徑。）簡單路徑：沒有重復(fù)點的路徑。（6）簡單回路）簡單回路1）回路：）回路： 在圖中，從某一點出發(fā)又回到該點的路徑；在圖中，從某一點出發(fā)又回到該點的路徑；2）簡單回路：）簡單回路： 只有起點和終點重復(fù)，其他點不重復(fù)的回路。只有起點和終點重復(fù)，其他

5、點不重復(fù)的回路。1. 用鄰接矩陣存儲圖用鄰接矩陣存儲圖（1）圖的鄰接矩陣：描述圖中兩個頂點之間鄰接關(guān)）圖的鄰接矩陣：描述圖中兩個頂點之間鄰接關(guān)系的矩陣。系的矩陣。（2）鄰接矩陣的結(jié)構(gòu)：）鄰接矩陣的結(jié)構(gòu)：是一個是一個n*n階的方陣，其中的每一行或每一列對應(yīng)于階的方陣，其中的每一行或每一列對應(yīng)于圖中的一個頂點；圖中的一個頂點；一般情況下，一般情況下，Aij頂點的值如下：頂點的值如下：Aij=1：表示從頂點：表示從頂點Vi到頂點到頂點Vj有邊（或?。┯羞叄ɑ蚧。?：表示從頂點：表示從頂點Vi到頂點到頂點Vj沒有邊（或?。]有邊（或?。├?：寫出下列無向圖：寫出下列無向圖G1的鄰接矩陣的鄰接矩陣 0

6、101010101010111010001100例例2：寫出下列有向圖：寫出下列有向圖G2的鄰接矩陣的鄰接矩陣 0100000101000111000000000（3）圖的鄰接矩陣的性質(zhì)：）圖的鄰接矩陣的性質(zhì)：1）一個圖的鄰接矩陣是）一個圖的鄰接矩陣是唯一唯一的；的；2）鄰接矩陣中，各行非零的個數(shù)為該行所對應(yīng)頂點）鄰接矩陣中，各行非零的個數(shù)為該行所對應(yīng)頂點的的出度出度；各列非零的個數(shù)為該列所對應(yīng)頂點的；各列非零的個數(shù)為該列所對應(yīng)頂點的入度入度；3）無向圖和完全有向圖的鄰接矩陣是一個）無向圖和完全有向圖的鄰接矩陣是一個對稱對稱的矩的矩陣陣（4）建立）建立無向圖無向圖鄰接矩陣的算法：鄰接矩陣的算法

7、：step1：輸入頂點的個數(shù)：輸入頂點的個數(shù)n和邊數(shù)和邊數(shù)e；step2：將鄰接矩陣清零；：將鄰接矩陣清零；step3：分別輸入：分別輸入e條邊的兩個頂點條邊的兩個頂點i和和j，并且令，并且令A(yù)ij=1， Aji=1。（4）建立）建立無向圖無向圖鄰接矩陣的算法描述：鄰接矩陣的算法描述：例例：（：（09.4）設(shè)二維數(shù)組）設(shè)二維數(shù)組A33表示表示3節(jié)點無向圖的鄰節(jié)點無向圖的鄰接矩陣。編寫程序，接矩陣。編寫程序，從鍵盤上輸入鄰接矩陣的數(shù)據(jù)從鍵盤上輸入鄰接矩陣的數(shù)據(jù)，求出該無向圖的邊數(shù)求出該無向圖的邊數(shù)以及以及各個節(jié)點的度數(shù)各個節(jié)點的度數(shù)，并，并輸出所輸出所求結(jié)果。求結(jié)果。011101110解：解：2

8、. 用鄰接鏈表存儲圖用鄰接鏈表存儲圖（1）圖的鄰接鏈表：又稱為鄰接表，由）圖的鄰接鏈表：又稱為鄰接表，由n個單鏈表組個單鏈表組成，每一個單鏈表又由表頭節(jié)點和表節(jié)點兩部分構(gòu)成。成，每一個單鏈表又由表頭節(jié)點和表節(jié)點兩部分構(gòu)成。1)表頭節(jié)點：對應(yīng)于圖中的一個節(jié)點；表頭節(jié)點：對應(yīng)于圖中的一個節(jié)點；2)表節(jié)點：表頭節(jié)點所代表頂點的所有鄰接點。表節(jié)點：表頭節(jié)點所代表頂點的所有鄰接點。例如：例如：表頭節(jié)點表頭節(jié)點表節(jié)點表節(jié)點（2）圖的鄰接表的性質(zhì)）圖的鄰接表的性質(zhì)1)一個圖的鄰接表不是唯一的；一個圖的鄰接表不是唯一的；2)在無向圖的鄰接表中，各單鏈表表節(jié)點的個數(shù)為對在無向圖的鄰接表中，各單鏈表表節(jié)點的個數(shù)為

9、對應(yīng)表頭節(jié)點（頂點）的度；應(yīng)表頭節(jié)點（頂點）的度；在有向圖的鄰接表中，各單鏈表表節(jié)點的個數(shù)為對應(yīng)在有向圖的鄰接表中，各單鏈表表節(jié)點的個數(shù)為對應(yīng)表頭節(jié)點（頂點）的出度。表頭節(jié)點（頂點）的出度。1. 圖的遍歷圖的遍歷2. 深度優(yōu)先遍歷深度優(yōu)先遍歷深度遍歷；深度遍歷； 訪問圖中各節(jié)點的過程。訪問圖中各節(jié)點的過程?？谠E：口訣：小號優(yōu)先；小號優(yōu)先；刨根問底。刨根問底。3. 廣度優(yōu)先遍歷廣度優(yōu)先遍歷廣度遍歷；廣度遍歷；口訣：口訣：小號優(yōu)先；小號優(yōu)先；橫掃四周。橫掃四周。例例1：（：（2010.4）如下圖所示的無向圖，分別按鄰接頂）如下圖所示的無向圖，分別按鄰接頂點序號由小到大順序給出點序號由小到大順序給出

10、廣度優(yōu)先遍歷廣度優(yōu)先遍歷和和深度優(yōu)先遍深度優(yōu)先遍歷歷的頂點序列。的頂點序列。解：解：廣度優(yōu)先遍歷廣度優(yōu)先遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷12374561245637例例2：（：（2008.4）對于下圖）對于下圖解：解：廣度優(yōu)先遍歷廣度優(yōu)先遍歷:（1）從頂點）從頂點1出發(fā)，按鄰接頂點序號由小到大的順序出發(fā)，按鄰接頂點序號由小到大的順序給出廣度優(yōu)先遍歷的頂點序列。給出廣度優(yōu)先遍歷的頂點序列。12567341. 相關(guān)概念相關(guān)概念（1）連通圖：從圖中任意一點出發(fā)，都能直接或）連通圖：從圖中任意一點出發(fā)，都能直接或間接到達其余點的圖。間接到達其余點的圖。1. 相關(guān)概念相關(guān)概念（2）子圖：如果圖）子圖：如果圖

11、G1的所有頂點和邊完全被圖的所有頂點和邊完全被圖G包含，則稱圖包含，則稱圖G1為圖為圖G的子圖。的子圖。（3）圖的連通分量：是指所研究圖的）圖的連通分量：是指所研究圖的最大的連通的最大的連通的子圖。子圖。注意：注意：對于對于連通圖連通圖來說，其連通分量就是它本身。來說，其連通分量就是它本身。2. 圖的最小生成樹圖的最小生成樹（1）圖的生成樹：指該圖）圖的生成樹：指該圖最小最小的的連通連通的子圖。的子圖。1）“最小最小”的含義：的含義： 一個圖的生成樹有一個圖的生成樹有n個頂點，個頂點，n-1條邊，如果多一條邊，如果多一條邊將使生成樹產(chǎn)生條邊將使生成樹產(chǎn)生回路回路，少一條邊將使生成樹，少一條邊將

12、使生成樹不連不連通通2）連通圖的必要條件：）連通圖的必要條件： 一個連通圖，具有一個連通圖，具有n個頂點，則至少有個頂點，則至少有n-1條邊。條邊。例如：圖例如：圖a的的部分部分生成樹如生成樹如b所示所示結(jié)論：結(jié)論：一個圖一個圖，可以，可以 生成生成多棵樹。多棵樹。（2）最小生成樹：）最小生成樹： 各邊權(quán)值之和為各邊權(quán)值之和為最小最小的生成樹。的生成樹。（3）求最小生成樹的方法）求最小生成樹的方法克魯斯卡爾法克魯斯卡爾法口訣：口訣：權(quán)值升序選邊；權(quán)值升序選邊；包含所有頂點；包含所有頂點；禁止產(chǎn)生回路。禁止產(chǎn)生回路。確保樹木連通。確保樹木連通。例：例： （2008.4）對于下圖）對于下圖（2）給

13、出克魯斯卡爾法構(gòu)造的最小生成樹。）給出克魯斯卡爾法構(gòu)造的最小生成樹。例例11-4下圖表示一個貧困地區(qū)的位置示意圖，頂點表示貧困縣，下圖表示一個貧困地區(qū)的位置示意圖，頂點表示貧困縣，邊上的權(quán)值表示各個縣之間的里程，假設(shè)修路的單位造價相同，邊上的權(quán)值表示各個縣之間的里程，假設(shè)修路的單位造價相同，問如何修路造價最低。問如何修路造價最低。1. 有關(guān)名詞有關(guān)名詞（1） AOV網(wǎng)絡(luò)圖：又稱為頂點活動網(wǎng)，是指用頂點網(wǎng)絡(luò)圖：又稱為頂點活動網(wǎng)，是指用頂點表征各項活動、邊表征活動發(fā)生先后順序的有向圖。表征各項活動、邊表征活動發(fā)生先后順序的有向圖。（2） 拓撲序列：由拓撲序列：由AOV網(wǎng)構(gòu)造的網(wǎng)構(gòu)造的線性序列線性序

14、列。（3） 拓撲排序：構(gòu)造拓撲序列的過程。拓撲排序：構(gòu)造拓撲序列的過程。2. 構(gòu)造拓撲序列的步驟構(gòu)造拓撲序列的步驟step1: 輸出輸出入度入度為零的節(jié)點；為零的節(jié)點；step2: 劃去從該節(jié)點引出的所有箭線；劃去從該節(jié)點引出的所有箭線；step3: 重復(fù)重復(fù)step1step2，直到輸出完最后一個節(jié)點。，直到輸出完最后一個節(jié)點。例：（例：（09.4）寫出下列）寫出下列AOV網(wǎng)的所有拓撲排序序列網(wǎng)的所有拓撲排序序列step1:輸出輸出入度入度為零的為零的節(jié)點；節(jié)點；step2:劃去從該節(jié)點引出的劃去從該節(jié)點引出的所有箭線；所有箭線；表表11-1是某工廠機床檢修工序示例是某工廠機床檢修工序示例順

15、序號工序代號工序名稱緊前工序1A拆卸無2B機件檢查A3C電器檢查A4D零件修復(fù)B5E零件加工B6F組裝C、D、E7G試車F例例11-5 有六項任務(wù)，每項任務(wù)要求的前驅(qū)活動如下：有六項任務(wù)，每項任務(wù)要求的前驅(qū)活動如下：C1： C2， C5， C6C2： C3， C6C3： C4C4：無：無C5：C4，C6C6：C3，C43. 拓撲排序小結(jié)拓撲排序小結(jié)（1）拓撲排序只能針對有向無環(huán)圖進行；）拓撲排序只能針對有向無環(huán)圖進行；（2）一個確定的）一個確定的AOV網(wǎng)，其拓撲序列不是唯一的。網(wǎng)，其拓撲序列不是唯一的。人有了知識，就會具備各種分析能力，人有了知識，就會具備各種分析能力，明辨是非的能力。明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，所以我們要勤懇讀書，廣泛閱讀，古人說古人說“書中自