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

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