[理學(xué)]數(shù)據(jù)結(jié)構(gòu)第7章(已修改)
2025-01-31 14:46 本頁(yè)面
【正文】 2 第 7章 圖 學(xué)習(xí)目標(biāo)與要求： 了解圖的定義和相關(guān)術(shù)語(yǔ)。 熟練掌握?qǐng)D的鄰接矩陣和鄰接鏈表表示。 熟練掌握?qǐng)D的兩種遍歷方式：深度優(yōu)先搜索和廣度優(yōu)先搜索。 熟練掌握求最小生成樹(shù)的兩種方法：普里姆算法和克魯斯卡爾算法。 熟練掌握求單源最短路徑的迪杰斯特拉算法，了解求每對(duì)頂點(diǎn)間最短路徑的弗洛伊德算法。 熟練掌握求拓?fù)湫蛄械姆椒ā? 3 圖是另一種非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，是一種更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖中，數(shù)據(jù)元素之間是多對(duì)多的關(guān)系，即一個(gè)數(shù)據(jù)元素對(duì)應(yīng)多個(gè)直接前驅(qū)元素和多個(gè)直接后繼元素。圖的應(yīng)用領(lǐng)域十分廣泛，如化學(xué)分析、工程設(shè)計(jì)、遺傳學(xué)、人工智能等。 圖的定義和術(shù)語(yǔ) 4 ?圖是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系 — 邊的有限集合組成的一種數(shù)據(jù)結(jié)構(gòu)?？梢杂枚M定義為： G＝（ V， E） ?其中， G表示一個(gè)圖， V是圖 G中頂點(diǎn)的集合，E是圖 G中邊的集合。 圖的定義和術(shù)語(yǔ) 5 V1 V3 V2 V4 V5 G1=（ V1， E1） V1＝ {v1,v2,v3,v4,v5}； E1＝ {(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)}。 (vi,vj)表示頂點(diǎn) vi和頂點(diǎn) vj之間有一條無(wú)向直接連線(xiàn)，也稱(chēng)為邊。 圖的定義和術(shù)語(yǔ) 6 V1 V3 V2 V4 G2=(V2,E2) V2={v1,v2,v3,v4} E2={v1,v2,v1,v3,v3,v4,v4,v1} vi,vj表示頂點(diǎn) vi和頂點(diǎn) vj之間有一條有向直接連線(xiàn)，也稱(chēng)為弧。其中 vi稱(chēng)為弧尾， vj稱(chēng)為弧頭。 圖的定義和術(shù)語(yǔ) 7 假設(shè)圖的頂點(diǎn)數(shù)目是 n，圖的邊數(shù)或者弧的數(shù)目是 e。如果不考慮頂點(diǎn)到自身的邊或者弧，即如果 vi,vj,則 vi≠vj 。對(duì)于無(wú)向圖，邊數(shù) e的取值范圍為 0~n(n1)/2。將具有 n(n1)/2條邊的無(wú)向圖稱(chēng)為 完全圖或無(wú)向完全圖 。對(duì)于有向圖，弧度 e的取值范圍是0~n(n1)。將具有 n(n1)條弧的有向圖稱(chēng)為 有向完全圖 。具有 enlogn條弧或者邊的圖稱(chēng)為 稀疏圖 。具有 enlogn條弧或者邊的圖稱(chēng)為 稠密圖 。 圖的定義和術(shù)語(yǔ) 8 圖的基本術(shù)語(yǔ) 1．鄰接點(diǎn) 在無(wú)向圖 G=(V,E)中，如果存在邊（ vi,vj） ∈ E，則稱(chēng) vi和 vj互為鄰接點(diǎn)，即 vi和 vj相互鄰接。邊（ vi,vj）依附于頂點(diǎn) vi和 vj，或者稱(chēng)邊（ vi,vj）與頂點(diǎn)相互關(guān)聯(lián) 在有向圖 G=(V,E)中，如果存在弧 vi,vj∈ E，則稱(chēng) vi鄰接到 vj。 弧 vi,vj與頂點(diǎn) vi和 vj相互關(guān)聯(lián)。 9 圖的基本術(shù)語(yǔ) 2．頂點(diǎn)的度 在無(wú)向圖中：一個(gè)頂點(diǎn)擁有的邊數(shù)，稱(chēng)為該頂點(diǎn)的度。記為 TD (v)。 在有向圖中： (a)一個(gè)頂點(diǎn)擁有的弧頭的數(shù)目，稱(chēng)為該頂點(diǎn)的入度， 記為 ID (v)； (b)一個(gè)頂點(diǎn)擁有的弧尾的數(shù)目，稱(chēng)為該頂點(diǎn)的出度， 記為 OD (v)； (c)一個(gè)頂點(diǎn)度等于頂點(diǎn)的入度 +出度， 即： TD (v)=ID (v)＋ OD (v)。 10 在圖 71的 G1中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在圖 72的 G2中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2 圖 71 無(wú)向圖 G1 圖 72 有向圖 G2 V1 V3 V2 V4 V5 V1 V3 V2 V4 圖的基本術(shù)語(yǔ) 11 圖的基本術(shù)語(yǔ) 2．頂點(diǎn)的度 假設(shè)頂點(diǎn)的個(gè)數(shù)為 n，邊數(shù)或弧數(shù)為 e，頂點(diǎn) vi的度記作 TD(vi),則頂點(diǎn)的度與弧度或者邊數(shù)滿(mǎn)足關(guān)系： 12 圖的基本術(shù)語(yǔ) 3．路徑 在圖中，從頂點(diǎn) vi出發(fā)經(jīng)過(guò)一系列的頂點(diǎn)序列到達(dá)頂點(diǎn) vj稱(chēng)為從頂點(diǎn) vi到 vj的路徑。路徑的長(zhǎng)度是路徑上弧或者邊的數(shù)目。 在路徑中，如果第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同，則這樣的路徑稱(chēng)為 回路 或者 環(huán) 。 13 圖的基本術(shù)語(yǔ) 3．路徑 在路徑所經(jīng)過(guò)的頂點(diǎn)序列中，如果頂點(diǎn)不重復(fù)出現(xiàn)，則稱(chēng)這樣的路徑為 簡(jiǎn)單路徑 。 在回路中，除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，如果其他頂點(diǎn)不重復(fù)出現(xiàn)，則稱(chēng)這樣的回路為簡(jiǎn)單回路 或者 簡(jiǎn)單環(huán) 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1