《數(shù)據(jù)結(jié)構(gòu)圖論部分》課件

數(shù)據(jù)結(jié)構(gòu)圖論部分圖論是數(shù)據(jù)結(jié)構(gòu)中重要的組成部分，它用圖形的方式來表示實(shí)體之間關(guān)系，幫助我們分析和解決各種問題。by圖的基本概念圖的定義圖由頂點(diǎn)和邊組成。頂點(diǎn)表示對象，邊表示對象之間的關(guān)系。圖的分類圖可以分為無向圖和有向圖。無向圖的邊沒有方向，有向圖的邊有方向。圖的應(yīng)用圖在現(xiàn)實(shí)世界中有著廣泛的應(yīng)用，例如社交網(wǎng)絡(luò)、交通路線、電路設(shè)計等。圖的表示11.鄰接矩陣用二維數(shù)組存儲頂點(diǎn)之間的關(guān)系，若頂點(diǎn)i和頂點(diǎn)j之間有邊，則矩陣元素a[i][j]的值為1，否則為0。22.鄰接表用鏈表存儲頂點(diǎn)和與之相鄰的頂點(diǎn)之間的關(guān)系，每個頂點(diǎn)對應(yīng)一個鏈表，鏈表中存儲與其相鄰的頂點(diǎn)信息。33.鄰接多重表針對帶權(quán)圖，擴(kuò)展了鄰接表，每個頂點(diǎn)對應(yīng)一個鏈表，每個鏈表中存儲了與之相鄰頂點(diǎn)的信息以及邊上的權(quán)值信息。44.鄰接多重集類似鄰接表，每個頂點(diǎn)對應(yīng)一個集合，集合中包含了與其相鄰頂點(diǎn)的信息，以及邊的權(quán)值信息。鄰接矩陣定義用一個二維數(shù)組來表示圖的結(jié)構(gòu)。數(shù)組的大小為頂點(diǎn)數(shù)乘以頂點(diǎn)數(shù)。元素值如果頂點(diǎn)i和頂點(diǎn)j之間存在邊，則數(shù)組元素a[i][j]的值為邊的權(quán)重。否則值為0或∞。優(yōu)點(diǎn)簡單易懂，實(shí)現(xiàn)方便，便于查找任意兩個頂點(diǎn)之間的邊。缺點(diǎn)空間復(fù)雜度較高，對于稀疏圖來說，空間利用率低。對圖進(jìn)行修改操作比較麻煩。鄰接表每個節(jié)點(diǎn)對應(yīng)一個鏈表鏈表中的每個節(jié)點(diǎn)表示與該節(jié)點(diǎn)相連的邊存儲圖的連接關(guān)系圖的基本操作創(chuàng)建圖圖的創(chuàng)建是圖論操作的起點(diǎn)，它包括確定圖的節(jié)點(diǎn)和邊，以及邊上的權(quán)重信息。遍歷圖圖的遍歷用于訪問圖中所有節(jié)點(diǎn)，常見的遍歷方法包括深度優(yōu)先搜索和廣度優(yōu)先搜索。查找節(jié)點(diǎn)查找圖中特定節(jié)點(diǎn)，可以根據(jù)節(jié)點(diǎn)的標(biāo)識信息、鄰接關(guān)系或其他屬性進(jìn)行查找。插入和刪除節(jié)點(diǎn)在圖中添加新的節(jié)點(diǎn)或刪除現(xiàn)有節(jié)點(diǎn)，需要更新圖的存儲結(jié)構(gòu)以反映變化。圖的創(chuàng)建節(jié)點(diǎn)圖中包含的元素，表示網(wǎng)絡(luò)中的實(shí)體。邊連接節(jié)點(diǎn)的連接線，表示節(jié)點(diǎn)之間的關(guān)系。有向邊節(jié)點(diǎn)之間的關(guān)系具有方向性，比如城市之間的單向道路。無向邊節(jié)點(diǎn)之間的關(guān)系沒有方向性，比如城市之間的雙向道路。圖的遍歷深度優(yōu)先搜索從起點(diǎn)開始，沿著一條路徑一直走下去，直到遇到一個沒有訪問過的節(jié)點(diǎn)，然后再從該節(jié)點(diǎn)開始沿著新的路徑繼續(xù)探索，直到所有節(jié)點(diǎn)都被訪問過。廣度優(yōu)先搜索從起點(diǎn)開始，依次訪問與起點(diǎn)相鄰的節(jié)點(diǎn)，然后再訪問與這些節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，以此類推，直到所有節(jié)點(diǎn)都被訪問過。圖的查找操作節(jié)點(diǎn)查找根據(jù)節(jié)點(diǎn)的標(biāo)識符，例如節(jié)點(diǎn)的名稱或索引，查找圖中是否存在該節(jié)點(diǎn)。邊查找根據(jù)邊的起點(diǎn)和終點(diǎn)節(jié)點(diǎn)標(biāo)識符，查找圖中是否存在該邊。路徑查找根據(jù)指定的起點(diǎn)和終點(diǎn)節(jié)點(diǎn)，查找連接這兩個節(jié)點(diǎn)的路徑。圖的存儲結(jié)構(gòu)矩陣存儲使用二維數(shù)組存儲圖的頂點(diǎn)之間的關(guān)系，元素值為邊權(quán)重，適用于稠密圖。鏈表存儲用鏈表表示每個頂點(diǎn)連接的邊，適用于稀疏圖，節(jié)省空間。圖的鏈?zhǔn)酱鎯?1.鄰接表使用鏈表存儲每個頂點(diǎn)的所有鄰接頂點(diǎn)。22.逆鄰接表用于表示圖中頂點(diǎn)之間的反向關(guān)系。33.鄰接多重表存儲有向圖的邊，每個頂點(diǎn)對應(yīng)一個表，每個邊對應(yīng)一個節(jié)點(diǎn)。矩陣存儲1鄰接矩陣使用一個二維數(shù)組來存儲圖的頂點(diǎn)之間的關(guān)系。2存儲方式如果兩個頂點(diǎn)之間存在邊，則矩陣對應(yīng)位置的值為邊的權(quán)重，否則為0或無窮大。3優(yōu)點(diǎn)簡單直觀，易于實(shí)現(xiàn)。4缺點(diǎn)空間復(fù)雜度高，不適合存儲稀疏圖。圖的遍歷算法深度優(yōu)先搜索從起點(diǎn)開始，沿著一條路徑盡可能深地探索，直到無法繼續(xù)。廣度優(yōu)先搜索從起點(diǎn)開始，逐層擴(kuò)展，先訪問所有與起點(diǎn)直接相連的節(jié)點(diǎn)，然后訪問這些節(jié)點(diǎn)的鄰居，依次類推。深度優(yōu)先搜索基本思想從起始節(jié)點(diǎn)出發(fā)，沿著一條路徑盡可能地往下走，直到無法繼續(xù)前進(jìn)為止。然后回溯到上一個節(jié)點(diǎn)，選擇另一條路徑繼續(xù)探索。算法步驟訪問當(dāng)前節(jié)點(diǎn)標(biāo)記當(dāng)前節(jié)點(diǎn)為已訪問遞歸地訪問當(dāng)前節(jié)點(diǎn)的所有未訪問鄰接節(jié)點(diǎn)回溯到上一個節(jié)點(diǎn)，繼續(xù)探索其他路徑廣度優(yōu)先搜索圖的遍歷廣度優(yōu)先搜索算法從圖中某個頂點(diǎn)開始，依次訪問該頂點(diǎn)的所有鄰接頂點(diǎn)，然后依次訪問這些鄰接頂點(diǎn)的鄰接頂點(diǎn)，直到所有可達(dá)頂點(diǎn)都被訪問過為止。層級訪問廣度優(yōu)先搜索按照層級訪問圖的頂點(diǎn)，先訪問與起點(diǎn)相鄰的頂點(diǎn)，再訪問與起點(diǎn)相鄰頂點(diǎn)的鄰接頂點(diǎn)，依次類推，直到訪問完所有可達(dá)頂點(diǎn)。數(shù)據(jù)結(jié)構(gòu)廣度優(yōu)先搜索需要使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)，用來存儲待訪問的頂點(diǎn)。應(yīng)用場景廣度優(yōu)先搜索算法廣泛應(yīng)用于各種圖算法中，例如最短路徑查找、網(wǎng)絡(luò)連接分析、游戲地圖搜索等。圖的連通性連通性圖的連通性描述了圖中節(jié)點(diǎn)之間的連接關(guān)系，判斷圖中節(jié)點(diǎn)是否可以相互到達(dá)。強(qiáng)連通如果圖中任意兩個節(jié)點(diǎn)之間都存在一條路徑，則稱該圖為強(qiáng)連通圖。弱連通如果圖中任意兩個節(jié)點(diǎn)之間都存在一條路徑，則稱該圖為弱連通圖。連通分量圖的連通分量是指圖中最大連通子圖。強(qiáng)連通分量定義圖中任意兩點(diǎn)之間都存在路徑，則該圖是強(qiáng)連通圖。判斷可以使用深度優(yōu)先搜索(DFS)算法，判斷圖中是否包含強(qiáng)連通分量。應(yīng)用強(qiáng)連通分量在社交網(wǎng)絡(luò)分析、路徑規(guī)劃等領(lǐng)域都有應(yīng)用。弱連通分量定義有向圖中，如果兩個頂點(diǎn)v和w之間存在一條從v到w的路徑，同時也存在一條從w到v的路徑，則稱v和w強(qiáng)連通。一個有向圖的極大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。性質(zhì)每個強(qiáng)連通分量內(nèi)部的頂點(diǎn)之間相互可達(dá)。強(qiáng)連通分量之間沒有路徑連接。最短路徑算法定義最短路徑算法用于在圖中找到兩個節(jié)點(diǎn)之間最短的路徑。應(yīng)用該算法廣泛應(yīng)用于交通導(dǎo)航、網(wǎng)絡(luò)路由和資源分配等領(lǐng)域。示例在交通導(dǎo)航中，算法可以找到最短的路線，節(jié)省時間和燃料。Dijkstra算法單源最短路徑從一個起點(diǎn)到圖中其他所有點(diǎn)的最短路徑貪心算法每次選擇距離起點(diǎn)最近的點(diǎn)進(jìn)行擴(kuò)展路徑更新不斷更新每個點(diǎn)的最短路徑估計值Floyd算法多源最短路徑Floyd算法是一種經(jīng)典的求解圖中任意兩點(diǎn)之間最短路徑的算法。動態(tài)規(guī)劃思想該算法利用動態(tài)規(guī)劃的思想，通過逐步更新距離矩陣來找到最短路徑。應(yīng)用廣泛Floyd算法在交通路線規(guī)劃、網(wǎng)絡(luò)路由等領(lǐng)域有著廣泛的應(yīng)用。最小生成樹連接所有節(jié)點(diǎn)最小生成樹(MST)是一個連接圖中所有節(jié)點(diǎn)的無環(huán)子圖，并且邊的總權(quán)重最小?，F(xiàn)實(shí)世界應(yīng)用最小生成樹在現(xiàn)實(shí)世界中有很多應(yīng)用，例如網(wǎng)絡(luò)設(shè)計、道路規(guī)劃和電路布線。貪心算法最小生成樹算法通常使用貪心算法來構(gòu)建，每次選擇最小的邊來連接節(jié)點(diǎn)。Prim算法貪心算法Prim算法是一種貪心算法，它通過不斷選擇邊權(quán)最小的邊來構(gòu)建最小生成樹。起始點(diǎn)算法從圖中任意一個節(jié)點(diǎn)開始，逐步擴(kuò)展生成樹。最小權(quán)值每次選擇與當(dāng)前生成樹相連的邊中權(quán)值最小的邊加入生成樹。Kruskal算法貪心算法Kruskal算法是一種貪心算法，它通過不斷選擇權(quán)重最小的邊來構(gòu)建最小生成樹。邊集算法首先將所有邊按權(quán)重從小到大排序，然后依次選擇邊，如果邊不會形成環(huán)，則將該邊加入到最小生成樹中。并查集Kruskal算法使用并查集數(shù)據(jù)結(jié)構(gòu)來判斷邊的加入是否會導(dǎo)致環(huán)的形成。拓?fù)渑判?1.有向無環(huán)圖拓?fù)渑判蜻m用于有向無環(huán)圖（DAG），這種圖中不存在環(huán)路。22.線性序列拓?fù)渑判驅(qū)D中的節(jié)點(diǎn)排成一個線性序列，滿足所有依賴關(guān)系。33.前驅(qū)節(jié)點(diǎn)在排序中，每個節(jié)點(diǎn)都排在其所有前驅(qū)節(jié)點(diǎn)之后。44.應(yīng)用場景拓?fù)渑判驈V泛應(yīng)用于任務(wù)調(diào)度、項(xiàng)目管理和依賴關(guān)系分析等領(lǐng)域。拓?fù)渑判蛩惴ㄋ惴ú襟E從圖中選擇一個入度為0的節(jié)點(diǎn)，將其輸出。刪除該節(jié)點(diǎn)及其所有出邊。重復(fù)步驟1和2，直到圖中所有節(jié)點(diǎn)都被輸出。應(yīng)用場景項(xiàng)目進(jìn)度管理：對任務(wù)進(jìn)行排序，確定完成任務(wù)的先后順序。編譯器優(yōu)化：對代碼進(jìn)行分析，優(yōu)化代碼執(zhí)行效率。網(wǎng)絡(luò)協(xié)議設(shè)計：對網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序，確保數(shù)據(jù)傳輸順序。應(yīng)用場景項(xiàng)目管理拓?fù)渑判蚩梢詭椭覀冇行У匕才彭?xiàng)目任務(wù)的執(zhí)行順序，確保所有依賴關(guān)系都得到滿足，從而提高項(xiàng)目效率。編譯器在編譯器中，拓?fù)渑判蚩梢杂脕泶_定變量和函數(shù)的定義和使用順序，以確保程序代碼的正確性。網(wǎng)絡(luò)路由拓?fù)渑判蚩梢杂脕泶_定網(wǎng)絡(luò)數(shù)據(jù)包的路由路徑，以確保數(shù)據(jù)包能夠按照正確的順序到達(dá)目的地。社交網(wǎng)絡(luò)拓?fù)渑判蚩梢杂脕矸治錾缃痪W(wǎng)絡(luò)中的用戶關(guān)系，例如，可以用來識別用戶之間的影響力關(guān)系。關(guān)鍵路徑1關(guān)鍵路徑定義關(guān)鍵路徑是指從起點(diǎn)到終點(diǎn)最長的路徑。2關(guān)鍵活動關(guān)鍵路徑上的活動稱為關(guān)鍵活動，這些活動延遲會影響整個項(xiàng)目的完成時間。3關(guān)鍵路徑的作用通過確定關(guān)鍵路徑，可以有效管理項(xiàng)目進(jìn)度，優(yōu)化資源分配，確保項(xiàng)目按時完成。關(guān)鍵路徑算法關(guān)鍵路徑在AOV網(wǎng)絡(luò)中，從源點(diǎn)到匯點(diǎn)的最長路徑被稱為關(guān)鍵路徑。關(guān)鍵路徑上的活動稱為關(guān)鍵活動。關(guān)鍵路徑上的活動延遲會直接影響整個項(xiàng)目的完成時間。算法步驟計算每個節(jié)點(diǎn)的最早開始時間計算每個節(jié)點(diǎn)的最晚完成時間確定關(guān)鍵活動，即滿足最早開始時間等于最晚完成時間的活動關(guān)鍵路徑就是連接關(guān)鍵活動的路徑計算關(guān)鍵路徑關(guān)鍵路徑的計算關(guān)鍵路徑計算的步驟，確定項(xiàng)目完成所需要的最短時間。項(xiàng)目進(jìn)度管理關(guān)鍵路徑可以幫助項(xiàng)目經(jīng)理確定最關(guān)鍵的任務(wù)，分配資源，監(jiān)控進(jìn)度，提高項(xiàng)目效率。關(guān)鍵路徑算法關(guān)鍵路徑算法可應(yīng)用于各種工程項(xiàng)目，例如建筑，軟件開發(fā)，生產(chǎn)等領(lǐng)域。應(yīng)用案例社交網(wǎng)絡(luò)分析圖論可以用于分析社交網(wǎng)絡(luò)中的用戶關(guān)系，例如朋友關(guān)系、關(guān)注關(guān)系等。路徑規(guī)劃圖論可以用于規(guī)劃最短路徑，例如導(dǎo)航軟件中的路線規(guī)劃。工藝流程優(yōu)化圖論可以用于優(yōu)化工藝流程，例如減少生產(chǎn)環(huán)節(jié)、提高生產(chǎn)效率。社交網(wǎng)絡(luò)分析用戶關(guān)系分析社交網(wǎng)絡(luò)圖可以用來分析用戶之間的關(guān)系，例如朋友、家人、同事等。影響力分析可以識別社交網(wǎng)絡(luò)中具有高影響力的用戶，例如意見領(lǐng)袖、網(wǎng)紅等。社群發(fā)現(xiàn)識別社交網(wǎng)絡(luò)中具有共同興趣的用戶群體