數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)第7章

22.05.2020，第頁(yè)，第7章，22.05.2020，頁(yè)面，上課前思考，學(xué)生們一定能畫(huà)出以下類(lèi)似的圖案。同時(shí)經(jīng)過(guò)的路是：(ab，BC，ca)，(ab，AC，ca)，(CB，ca，BC)，22.05.2020，頁(yè)面，學(xué)習(xí)目標(biāo)，1 .了解圖形的類(lèi)型定義。2.熟悉圖形的各種存儲(chǔ)結(jié)構(gòu)及其配置算法，了解各種存儲(chǔ)結(jié)構(gòu)的特性和選擇原理。熟練掌握?qǐng)D的兩種遍歷算法。4.理解各種圖的應(yīng)用問(wèn)題的算法。22.05.2020，第頁(yè)，【重點(diǎn)和難點(diǎn)】，圖使用得很廣泛，圖中各種應(yīng)用問(wèn)題的算法都比較經(jīng)典，因此本章著重了解各種圖的算法及其應(yīng)用實(shí)例。知識(shí)點(diǎn)、圖的類(lèi)型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和圖的寬度優(yōu)先搜索遍歷、全向網(wǎng)絡(luò)的最小生成樹(shù)、最短路徑、拓?fù)渑判?、關(guān)鍵路徑。22.05.2020，第頁(yè)，學(xué)習(xí)指南，離散數(shù)學(xué)的圖論是專(zhuān)門(mén)研究圖形性質(zhì)的數(shù)學(xué)分支，而圖論則側(cè)重研究圖的純粹數(shù)學(xué)特性，數(shù)據(jù)結(jié)構(gòu)中對(duì)圖形的討論則集中在計(jì)算機(jī)上如何顯示圖形以及如何實(shí)現(xiàn)圖形的運(yùn)行和應(yīng)用。圖形是比線性表和樹(shù)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因此，與線性表、樹(shù)不同，可以通過(guò)圖形以不同的方式操作頂點(diǎn)或弧，但是更多圖形的應(yīng)用問(wèn)題(例如最小生成樹(shù)和最短路徑查找等)在圖論研究中已經(jīng)有了特定的算法，本章主要介紹計(jì)算機(jī)內(nèi)的特定實(shí)現(xiàn)。這種算法乍一看也比較難，應(yīng)該通過(guò)比較具體圖例的存儲(chǔ)結(jié)構(gòu)來(lái)學(xué)習(xí)。圖導(dǎo)航的兩個(gè)搜索路徑和樹(shù)導(dǎo)航的兩個(gè)搜索路徑非常相似，因此必須通過(guò)兩種算法的比較學(xué)習(xí)提高學(xué)習(xí)效果。本章需要完成的算法設(shè)計(jì)包括：7.7、7.9、7.10、7.12、7.14、7.15、7.22、22.05.2020、第頁(yè)，7.1圖的定義和術(shù)語(yǔ)，7.2圖的存儲(chǔ)表示，7.3圖通過(guò)，7.4最小生成樹(shù)，7.5重量(雙)連接圖和關(guān)節(jié)點(diǎn)，7.6兩點(diǎn)之間的最短路徑問(wèn)題，7.7拓?fù)渑判颍?.8主要路徑，22.05.2020，頁(yè)面，插圖由一個(gè)頂點(diǎn)組成，Graph=(V，VR)，其中VR=| v，w/v和P(v，w)表示從V到w的弧，V表示弧頭，w表示弧終點(diǎn)。謂詞P(v，w)定義圓弧的含義或信息。圖的結(jié)構(gòu)定義：7.1圖的定義和術(shù)語(yǔ)，22.05.2020，頁(yè)面，“弧”具有方向，因此由一組頂點(diǎn)和一組弧組成的圖表稱(chēng)為直接圖形。ABECD，例如：G1=(V1，VR1)，其中v1=a，b，c，d，頁(yè)面，如果VR需要VR，則(v，w)表示頂點(diǎn)v和頂點(diǎn)w之間存在角點(diǎn)。由、BCADFE、頂點(diǎn)集和邊集組成的插圖稱(chēng)為全向插圖。例如3360 G2=(v2，vr2) v2=a，b，c，d，e，f vr2=(a，b)，(a，e)，以及頁(yè)面、名詞和術(shù)語(yǔ)、網(wǎng)絡(luò)、子圖形、完全圖形、稀疏圖形、密度、相鄰點(diǎn)、度、粒度、出圖、路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路、連接圖形、連接元件、強(qiáng)連接頁(yè)面，a，b，e，c，f，a，e，f，b，c，圖表G=(V，VR)，15，9，7，21，11，3，2，圓弧或邊權(quán)重的圖解分別稱(chēng)為直接或無(wú)方向網(wǎng)絡(luò)。C、22.05.2020、頁(yè)面上，假設(shè)圖中有n個(gè)頂點(diǎn)和