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

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

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

3、接）兩頂點(diǎn)的鄰接 1）對(duì)于無(wú)向圖來(lái)說(shuō)，如果頂點(diǎn)）對(duì)于無(wú)向圖來(lái)說(shuō)，如果頂點(diǎn)Vi與與Vj之間有邊，之間有邊，則稱頂點(diǎn)則稱頂點(diǎn)Vi與與Vj互為鄰接；互為鄰接； 2）對(duì)于有向圖來(lái)說(shuō)，如果頂點(diǎn)）對(duì)于有向圖來(lái)說(shuō)，如果頂點(diǎn)Vi到頂點(diǎn)到頂點(diǎn)Vj有弧，有弧，則稱頂點(diǎn)則稱頂點(diǎn)Vi和和Vj是鄰接，但是鄰接，但VjVi；（4）頂點(diǎn)的度）頂點(diǎn)的度1）無(wú)向圖頂點(diǎn)的度，是與該頂點(diǎn)鄰接的邊的數(shù)目；）無(wú)向圖頂點(diǎn)的度，是與該頂點(diǎn)鄰接的邊的數(shù)目；2）有向圖頂點(diǎn)的度，是該頂點(diǎn)入度和出度之和；）有向圖頂點(diǎn)的度，是該頂點(diǎn)入度和出度之和；有向圖頂點(diǎn)的入度，是進(jìn)入該頂點(diǎn)弧的數(shù)目；有向圖頂點(diǎn)的入度，是進(jìn)入該頂點(diǎn)弧的數(shù)目；有向圖頂點(diǎn)的出度，是遠(yuǎn)

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

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

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

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

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

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

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

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

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

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

14、列。（3） 拓?fù)渑判颍簶?gòu)造拓?fù)湫蛄械倪^(guò)程。拓?fù)渑判颍簶?gòu)造拓?fù)湫蛄械倪^(guò)程。2. 構(gòu)造拓?fù)湫蛄械牟襟E構(gòu)造拓?fù)湫蛄械牟襟Estep1: 輸出輸出入度入度為零的節(jié)點(diǎn)；為零的節(jié)點(diǎn)；step2: 劃去從該節(jié)點(diǎn)引出的所有箭線；劃去從該節(jié)點(diǎn)引出的所有箭線；step3: 重復(fù)重復(fù)step1step2，直到輸出完最后一個(gè)節(jié)點(diǎn)。，直到輸出完最后一個(gè)節(jié)點(diǎn)。例：（例：（09.4）寫(xiě)出下列）寫(xiě)出下列AOV網(wǎng)的所有拓?fù)渑判蛐蛄芯W(wǎng)的所有拓?fù)渑判蛐蛄衧tep1:輸出輸出入度入度為零的為零的節(jié)點(diǎn)；節(jié)點(diǎn)；step2:劃去從該節(jié)點(diǎn)引出的劃去從該節(jié)點(diǎn)引出的所有箭線；所有箭線；表表11-1是某工廠機(jī)床檢修工序示例是某工廠機(jī)床檢修工序示例順

15、序號(hào)工序代號(hào)工序名稱緊前工序1A拆卸無(wú)2B機(jī)件檢查A3C電器檢查A4D零件修復(fù)B5E零件加工B6F組裝C、D、E7G試車(chē)F例例11-5 有六項(xiàng)任務(wù)，每項(xiàng)任務(wù)要求的前驅(qū)活動(dòng)如下：有六項(xiàng)任務(wù)，每項(xiàng)任務(wù)要求的前驅(qū)活動(dòng)如下：C1： C2， C5， C6C2： C3， C6C3： C4C4：無(wú)：無(wú)C5：C4，C6C6：C3，C43. 拓?fù)渑判蛐〗Y(jié)拓?fù)渑判蛐〗Y(jié)（1）拓?fù)渑判蛑荒茚槍?duì)有向無(wú)環(huán)圖進(jìn)行；）拓?fù)渑判蛑荒茚槍?duì)有向無(wú)環(huán)圖進(jìn)行；（2）一個(gè)確定的）一個(gè)確定的AOV網(wǎng)，其拓?fù)湫蛄胁皇俏ㄒ坏?。網(wǎng)，其拓?fù)湫蛄胁皇俏ㄒ坏摹Ｈ擞辛酥R(shí)，就會(huì)具備各種分析能力，人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。明辨是非的能力。所以我們要勤懇讀書(shū)，廣泛閱讀，所以我們要勤懇讀書(shū)，廣泛閱讀，古人說(shuō)古人說(shuō)“書(shū)中自