前言
- 本文基礎(chǔ)知識部分來自于b站：分享筆記的好人兒的思維導(dǎo)圖與王道考研課程，感謝大佬的開源精神，習(xí)題來自老師劃的重點(diǎn)以及考研真題。
- 此前我嘗試了完全使用Python或是結(jié)合大語言模型對考研真題進(jìn)行數(shù)據(jù)清洗與可視化分析，本人技術(shù)有限，最終數(shù)據(jù)清洗結(jié)果不夠理想，相關(guān)CSDN文章便沒有發(fā)出。
（考研真題待更新）
歡迎訂閱專欄：408直通車
請注意，本文中的部分內(nèi)容來自網(wǎng)絡(luò)搜集和個(gè)人實(shí)踐，如有任何錯(cuò)誤，請隨時(shí)向我們提出批評和指正。本文僅供學(xué)習(xí)和交流使用，不涉及任何商業(yè)目的。如果因本文內(nèi)容引發(fā)版權(quán)或侵權(quán)問題，請通過私信告知我們，我們將立即予以刪除。
第六章 圖
圖的定義及基本術(shù)語
概念
- 圖G由頂點(diǎn)集V和邊集E組成，記G=(V, E)，其中V(G)表示圖G中頂點(diǎn)的有限非空集；E(G)表示圖G中頂點(diǎn)之間的關(guān)系（邊）集合
基本術(shù)語
-
關(guān)系及路徑術(shù)語
-
鄰接：有邊/弧相連的兩個(gè)頂點(diǎn)之間的關(guān)系（無向圖的邊：(vi, vj)，有向圖的邊：<vi, vj>）
-
關(guān)聯(lián)（依附）：邊/弧與頂點(diǎn)之間的關(guān)系
-
頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)
有向圖中，頂點(diǎn)的度等于該頂點(diǎn)的入度和出度之和
-
路徑：連續(xù)的邊構(gòu)成的頂點(diǎn)序列
路徑長度：路徑上邊或弧的數(shù)目/權(quán)值之和 -
回路（環(huán)）：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑
-
簡單路徑：除路徑起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同的路徑
簡單回路（簡單環(huán)）：除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑
-
-
圖的術(shù)語
-
無向圖：每條邊都是無方向的
有向圖：每條邊都是有方向的
-
簡單圖：不存在重復(fù)邊，不存在頂點(diǎn)到自身的邊
多重圖：反之
-
子圖：設(shè)有兩個(gè)圖G=(V, E)和G’=(V’, E’)，若V’是V的子集，且E’是E的子集，則稱G’是G的子圖
-
網(wǎng)：邊/弧帶權(quán)的圖
-
連通圖（強(qiáng)連通圖）：在無（有）向圖中，若對任何兩個(gè)頂點(diǎn)v，u都存在從v到u的路徑，則G是連通圖（強(qiáng)連通圖）
-
-
子圖相關(guān)術(shù)語
-
連通分量/極大連通子圖：該子圖是G連通子圖，將G的任何不在該子圖的頂點(diǎn)加入，子圖不再連通
強(qiáng)連通分量/極大強(qiáng)連通子圖：該子圖是G強(qiáng)連通子圖，將G的任何不在該子圖的頂點(diǎn)加入，子圖不再強(qiáng)連通
-
極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通
-
生成樹：包含無向圖G所有頂點(diǎn)的極小連通子圖
-
生成森林，對非連通圖，由各個(gè)連通分量的生成樹的集合
-
- 無向完全圖：任意兩個(gè)點(diǎn)都有一條邊
- 有向完全圖：任意兩個(gè)點(diǎn)都有兩條邊
- 稀疏圖：有很少邊或弧的圖（e<nlogn）
- 稠密圖：有較多邊或弧的圖
小結(jié)
圖的存儲結(jié)構(gòu)
鄰接矩陣法
-
概念
- 是指用一個(gè)一位數(shù)組存儲圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組存儲圖中邊的信息（鄰接關(guān)系），二維數(shù)組即鄰接矩陣
- 是指用一個(gè)一位數(shù)組存儲圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組存儲圖中邊的信息（鄰接關(guān)系），二維數(shù)組即鄰接矩陣
-
無向圖
-
-
無向圖的鄰接矩陣是對稱的
-
頂點(diǎn)i的度=第i行（或第i列）中1的個(gè)數(shù)
-
-
-
有向圖
-
-
有向圖的鄰接矩陣可能是不對稱的
-
頂點(diǎn)的出度 = 第i行元素之和
-
頂點(diǎn)的入度 = 第i列元素之和
-
-
- 有向網(wǎng)
-
-
缺點(diǎn)
- 不便于增加和刪除結(jié)點(diǎn)、存稀疏圖浪費(fèi)大量空間（O(n^2)）、統(tǒng)計(jì)一共有多少條邊浪費(fèi)時(shí)間
- 不便于增加和刪除結(jié)點(diǎn)、存稀疏圖浪費(fèi)大量空間（O(n^2)）、統(tǒng)計(jì)一共有多少條邊浪費(fèi)時(shí)間
-
補(bǔ)充
- 鄰接矩陣A的A^n[i][j]等于由頂點(diǎn)i到j(luò)的長度為n的路徑數(shù)量
- 鄰接矩陣A的A^n[i][j]等于由頂點(diǎn)i到j(luò)的長度為n的路徑數(shù)量
小結(jié)
鄰接表法
-
概念
-
圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲，元素包含指向第一個(gè)鄰接點(diǎn)的指針，存儲頂點(diǎn)和頭指針的一維數(shù)組叫頂點(diǎn)表
-
每個(gè)頂點(diǎn)的所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表
-
-
結(jié)構(gòu)
-
-
若為無向圖，則需要存儲兩倍的邊，存儲空間為O(|V|+2|E|)
-
若為有向圖，存儲空間為O(|V|+|E|)，若采用鄰接表法則找出度易，找入度難；若采用逆鄰接表則找入度易，找出度難
-
有向圖鄰接表法中，頂點(diǎn)vi出度為第i個(gè)單鏈表中結(jié)點(diǎn)個(gè)數(shù)；入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i-1的結(jié)點(diǎn)個(gè)數(shù)
-
圖的鄰接表表示不唯一
-
-
-
實(shí)現(xiàn)
-
-
-
頂點(diǎn)表結(jié)點(diǎn)：頂點(diǎn)域+邊表頭指針
-
邊表結(jié)點(diǎn)：鄰接點(diǎn)域+指針域+權(quán)值（若為網(wǎng)）
-
-
-
-
缺點(diǎn)
- 若不構(gòu)建逆鄰接表則找入度麻煩、不方便檢查任意一對頂點(diǎn)之間是否存在邊
-
領(lǐng)接表
-
十字鏈表法（有向圖）
-
概念
- 十字鏈表時(shí)針對有向圖的存儲方式，對應(yīng)于有向圖中的每條弧有一個(gè)結(jié)點(diǎn)，對應(yīng)于每個(gè)頂點(diǎn)也有一個(gè)結(jié)點(diǎn)（有向圖的鄰接表與逆鄰接表的結(jié)合）
-
結(jié)構(gòu)
-
-
頂點(diǎn)結(jié)點(diǎn)域結(jié)構(gòu)
- data域（存放頂點(diǎn)數(shù)據(jù)信息） + firstin域 + firstout域（分別指向以該頂點(diǎn)為弧頭或弧尾的第一個(gè)弧結(jié)點(diǎn)）
-
弧結(jié)點(diǎn)域結(jié)構(gòu)
- 尾域（弧尾）+ 頭域（弧頭）+ hlink域（指向弧頭相同的下一條?。? tlink域（指向弧尾相同的下一條弧）+ info域（弧相關(guān)信息）
-
-
-
圖的十字鏈表不唯一，但一個(gè)十字鏈表表示確定一個(gè)圖
鄰接多重表（無向圖）
-
概念
- 對鄰接表的邊表進(jìn)行改造，得到專門針對存儲無向圖的鄰接多重表
-
結(jié)構(gòu)
-
-
頂點(diǎn)結(jié)點(diǎn)域結(jié)構(gòu)
- data域（存儲該頂點(diǎn)的信息）+ firstedge域（指示第一條依附于該頂點(diǎn)的邊）
-
弧結(jié)點(diǎn)域結(jié)構(gòu)
- 標(biāo)志域（標(biāo)記該邊是否被搜索過）+ ivex域 + jvex域（該邊依附的兩個(gè)頂點(diǎn)在圖中位置）+ ilink域 + jlink域（分別指向下一條依附于頂點(diǎn)ivex、jvex的邊）+ info域（弧相關(guān)信息）
- 標(biāo)志域（標(biāo)記該邊是否被搜索過）+ ivex域 + jvex域（該邊依附的兩個(gè)頂點(diǎn)在圖中位置）+ ilink域 + jlink域（分別指向下一條依附于頂點(diǎn)ivex、jvex的邊）+ info域（弧相關(guān)信息）
-
-
圖的遍歷
廣度優(yōu)先搜索
-
概念
- 類似于二叉樹的層序遍歷算法，多了標(biāo)記數(shù)組，用于確定已訪問的結(jié)點(diǎn)
-
算法思想
-
-
首先訪問起始頂點(diǎn)v（進(jìn)隊(duì)列），由v出發(fā)，依次訪問v的各個(gè)未訪問過的鄰接頂點(diǎn)w1,w2,…,wi（都加入隊(duì)列，起始頂點(diǎn)pop掉）
-
然后依次訪問w1,w2,…,wi的所有未訪問過的鄰接頂點(diǎn)（加入隊(duì)列，并pop訪問過的頂點(diǎn)）
-
再從這些頂點(diǎn)出發(fā)，訪問所有未被訪問過的鄰接頂點(diǎn)，直到遍歷完成（利用隊(duì)列實(shí)現(xiàn)）
-
-
-
性能分析
-
時(shí)間復(fù)雜度
-
鄰接矩陣存儲方式：O(|V|^2)
-
鄰接表存儲方式：O(|V|+|E|)
-
-
空間復(fù)雜度
- BFS需要借助一個(gè)隊(duì)列，n個(gè)頂點(diǎn)均需要入隊(duì)一次，所以最壞情況下n個(gè)頂點(diǎn)在隊(duì)列，O(|V|)
-
-
基于鄰接矩陣的遍歷BFS序列是唯一的，基于鄰接表的遍歷所得到的BFS序列是不唯一的
小結(jié)
深度優(yōu)先搜索
-
概念
- 類似于樹的先序遍歷，搜索策略是盡可能深地搜索一個(gè)圖
-
算法思想
-
-
首先訪問圖中某個(gè)起始頂點(diǎn)v，由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點(diǎn)w1，再訪問與w1鄰接且未訪問的任一頂點(diǎn)，重復(fù)
-
當(dāng)不能繼續(xù)向下訪問，則依次退回到最近被訪問的頂點(diǎn)，若還有鄰接頂點(diǎn)未被訪問，則從該點(diǎn)繼續(xù)DFS，直到所有頂點(diǎn)均被訪問為止（用遞歸實(shí)現(xiàn)）
-
-
-
性能分析
-
時(shí)間復(fù)雜度
-
鄰接矩陣存儲方式：O(|V|^2)
-
鄰接表存儲方式：O(|V|+|E|)
-
-
空間復(fù)雜度
- DFS是一個(gè)遞歸算法，需要工作棧輔助，最多需要圖中所有頂點(diǎn)進(jìn)棧，O(|V|)
-
-
基于鄰接矩陣的遍歷DFS序列是唯一的，基于鄰接表的遍歷所得到的DFS序列是不唯一的
小結(jié)
圖的應(yīng)用
最小生成樹
-
概念
-
生成樹：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖
-
最小生成樹：權(quán)值之和最小的那棵生成樹
-
-
性質(zhì)
-
最小生成樹不是唯一的
-
其對應(yīng)的邊的權(quán)值之和總是唯一的，且是最小的
-
最小生成樹的邊數(shù)=頂點(diǎn)數(shù)-1
-
-
算法
-
算法基于MST性質(zhì)
- 性質(zhì)解釋：n個(gè)頂點(diǎn)分屬已經(jīng)在生成樹上的頂點(diǎn)集U和未在生成樹上的頂點(diǎn)集V-U，接下來應(yīng)在連通U和V-U的邊中選取權(quán)值最小的邊
-
Prim算法
-
概述
- 每次將代價(jià)最小的新頂點(diǎn)加入生成樹
-
實(shí)現(xiàn)
-
開始時(shí)從圖中任取一個(gè)頂點(diǎn)加入樹T
-
之后選擇一個(gè)與當(dāng)前T中頂點(diǎn)集合距離最近的頂點(diǎn)，將該點(diǎn)和對應(yīng)邊加入T，每次操作后T中頂點(diǎn)數(shù)和邊數(shù)都+1
-
以此類推，當(dāng)所有點(diǎn)加入T，必然有n-1條邊，即T就是最小生成樹
-
-
-
Kruskal算法
-
概述
- 每次選一條權(quán)值最小的邊（邊按權(quán)值排序），使其連通（用并查集判斷并實(shí)現(xiàn)）
-
實(shí)現(xiàn)
-
開始時(shí)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T={V,{}}，每個(gè)頂點(diǎn)自成一個(gè)連通分量
-
然后按照邊的權(quán)值由小到大，不斷選取當(dāng)前未被選取過且權(quán)值最小的邊
-
若該邊依附的頂點(diǎn)在兩個(gè)連通分量上，則將邊加入T，否則繼續(xù)選取下一條邊
-
以此類推，直到T中所有頂點(diǎn)都在一個(gè)連通分量上
-
-
-
比較
-
最短路徑
- 在有向網(wǎng)中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，找到一條各邊權(quán)值之和最小的路徑
BFS求無權(quán)圖的單源最短路徑
Dijkstra算法（兩點(diǎn)間最短路徑）
-
概述
-
維護(hù)一個(gè)最短路徑數(shù)組，每次選取最短的頂點(diǎn)加入，更新加入后的最短路徑，直到所有頂點(diǎn)都訪問
-
s[]記錄是否訪問，dist[]記錄源地到各點(diǎn)最短路徑，path[]記錄前驅(qū)結(jié)點(diǎn)
-
-
過程
-
初始化：集合S初始為{0}（源點(diǎn)入集合），dist[]初始值dist[i]=arcs[0][i]（與源點(diǎn)距離）
-
從頂點(diǎn)集合V-S中選出dist[]數(shù)組值最小的，即選最近的點(diǎn)加入
-
修改V0出發(fā)到集合V-S上任一頂點(diǎn)最短路徑長度：若dist[j]+arcs[j][k]<dist[k]，則更新dist[k]=dist[j]+arcs[j][k]
-
重復(fù)步驟2-3，n-1次，直到所有頂點(diǎn)都包含在S中
-
-
時(shí)間復(fù)雜度
- O(|V|^2)
- O(|V|^2)
-
注意
- 適合稠密圖，無負(fù)權(quán)值
- 適合稠密圖，無負(fù)權(quán)值
Floyd算法（各頂點(diǎn)之間最短路徑）
-
概述
- 維護(hù)一個(gè)各頂點(diǎn)間最短路徑二維數(shù)組，不斷試探加入中間結(jié)點(diǎn)，是否縮短距離（三重循環(huán)）
- 維護(hù)一個(gè)各頂點(diǎn)間最短路徑二維數(shù)組，不斷試探加入中間結(jié)點(diǎn)，是否縮短距離（三重循環(huán)）
-
過程
-
初始化：對任意兩個(gè)頂點(diǎn)vi和vj，若存在邊，則二維數(shù)組上最短路徑為權(quán)值（不存在則最短路徑為無窮）
-
逐步嘗試在原路徑上加入頂點(diǎn)k(k = 0,1,…,n-1)為中間結(jié)點(diǎn)
-
若更新后得到路徑比原本路徑長度短，則新路徑代替原本路徑
-
-
時(shí)間復(fù)雜度
-
O(|V|^3)
-
注意
-
允許圖中有帶父權(quán)值的邊，但不允許有包含帶負(fù)權(quán)值的邊組成回路
-
適用于帶權(quán)無向圖
小結(jié)
有向無環(huán)圖的應(yīng)用
-
有向無環(huán)圖：無環(huán)的有向圖，簡稱DAG圖
-
用一個(gè)有向圖表示一個(gè)工程的各子工程及其互相制約關(guān)系
-
AOV網(wǎng)：頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)之間的優(yōu)先制約關(guān)系
-
AOE網(wǎng)：弧表示活動(dòng)，以頂點(diǎn)表示活動(dòng)的開始或結(jié)束事件
-
有向無環(huán)圖描述表達(dá)式
-
-
28題為例
-
操作數(shù)在最下層排成一排
-
按生效順序，加入運(yùn)算符（分層）
-
從底向上檢查同層能否合并
-
-
拓?fù)渑判颍ˋOV網(wǎng)）
-
概述
-
拓?fù)湫蛄?/p>
- 拓?fù)湫蛄惺菍D中所有的頂點(diǎn)，如果存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在排序中頂點(diǎn)A出現(xiàn)在頂點(diǎn)B的前面
-
拓?fù)渑判?/p>
- 對一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程
- 對一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程
-
-
過程
-
從AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并輸出
-
從網(wǎng)中刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊
-
重復(fù)前兩個(gè)步驟，直到當(dāng)前的AOV網(wǎng)為空或當(dāng)前網(wǎng)中不存在無前驅(qū)的頂點(diǎn)為止（后者說明有向圖中存在環(huán)）
-
-
時(shí)間復(fù)雜度
-
鄰接矩陣存儲，O(|V|^2)
-
鄰接表存儲，O(|V|+|E|)
-
-
注意
-
若一個(gè)頂點(diǎn)有多個(gè)直接后繼，則拓?fù)渑判蛲ǔ２晃ㄒ唬ㄈ裘總€(gè)頂點(diǎn)有唯一前驅(qū)后繼，則唯一）
-
若圖的鄰接矩陣是三角矩陣，則存在拓?fù)渑判?，反之不一定成?/p>
-
逆拓?fù)渑判颍ˋOV網(wǎng)）
-
實(shí)現(xiàn)
- DFS算法
- DFS算法
-
過程
-
從AOV網(wǎng)中選擇一個(gè)沒有后繼的頂點(diǎn)并輸出
-
從網(wǎng)中刪除該頂點(diǎn)和所有以它為終點(diǎn)的有向邊
-
重復(fù)前兩個(gè)步驟，直到當(dāng)前的AOV網(wǎng)為空
-
小結(jié)
關(guān)鍵路徑（AOE網(wǎng)）
-
概述
-
關(guān)鍵路徑
- 從源點(diǎn)到匯點(diǎn)的所有路徑中，具有最大路徑長度的路徑
- 從源點(diǎn)到匯點(diǎn)的所有路徑中，具有最大路徑長度的路徑
-
關(guān)鍵活動(dòng)
- 關(guān)鍵路徑上的活動(dòng)
- 關(guān)鍵路徑上的活動(dòng)
-
- 過程
| 項(xiàng)目/信息 | V1 | V2 | V3 | V4 | V5 | V6 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 求所有事件的最早發(fā)生時(shí)間ve() | 0 | 3 | 2 | 6 | 6 | 8 | ||||||||
| 求所有事件的最遲發(fā)生時(shí)間vl() | 0 | 4 | 2 | 6 | 7 | 8 | ||||||||
| 求所有活動(dòng)的最早發(fā)生時(shí)間e() | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 6 | ||||||
| 求所有活動(dòng)的最遲發(fā)生時(shí)間l() | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 | ||||||
| 求所有活動(dòng)的時(shí)間余量d() | 1 | 0 | 1 | 1 | 0 | 3 | 0 | 1 |
- 關(guān)鍵活動(dòng)（d()=0的活動(dòng)就是關(guān)鍵活動(dòng)）：a2、a5、a7
- 關(guān)鍵路徑：V1—>V3—>V4—>V6
表格一：求所有事件的最早發(fā)生時(shí)間ve()和最遲發(fā)生時(shí)間vl()
| 比較項(xiàng)目/存儲結(jié)構(gòu) | V1 | V2 | V3 | V4 | V5 | V6 |
|---|---|---|---|---|---|---|
| 最早發(fā)生時(shí)間ve(k) | 0 | 3 | 2 | 6 | 6 | 8 |
| 最遲發(fā)生時(shí)間vl(k) | 0 | 4 | 2 | 6 | 7 | 8 |
表格二：求所有活動(dòng)的最早發(fā)生時(shí)間e()、最遲發(fā)生時(shí)間l()和時(shí)間余量d()
| 項(xiàng)目/信息 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
|---|---|---|---|---|---|---|---|---|
| 最早發(fā)生時(shí)間e() | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 6 |
| 最遲發(fā)生時(shí)間l() | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 |
| 時(shí)間余量d() | 1 | 0 | 1 | 1 | 0 | 3 | 0 | 1 |
關(guān)鍵活動(dòng)：a2、a5、a7
關(guān)鍵路徑：V1—>V3—>V4—>V6
-
注意
-
關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)，是決定整個(gè)工程的關(guān)鍵因素，因此可通過加快關(guān)鍵活動(dòng)來縮短整個(gè)工程的工期
-
不能任意縮短關(guān)鍵活動(dòng)，因?yàn)橐坏┛s短到一定程度，該關(guān)鍵活動(dòng)可能變成非關(guān)鍵活動(dòng)
-
網(wǎng)中的關(guān)鍵路徑不唯一，只有加快那些包含在所有關(guān)鍵路徑上的關(guān)鍵活動(dòng)才能達(dá)到縮短工期的目的
-
若關(guān)鍵活動(dòng)耗時(shí)增加，則整個(gè)工程的工期增長
-
小結(jié)
代碼
圖的存儲結(jié)構(gòu)
-
鄰接矩陣存儲
- g[a][b]存儲邊a->b
-
鄰接表存儲（數(shù)組模擬）
-
// 對于每個(gè)點(diǎn)k，開一個(gè)單鏈表，存儲k所有可以走到的點(diǎn)。h[k]存儲這個(gè)單鏈表的頭結(jié)點(diǎn) int h[N], e[N], ne[N], idx; // 添加一條邊a->b void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } // 初始化 idx = 0; memset(h, -1, sizeof h); //在頭文件cstring中
-
圖的遍歷
-
DFS
- 上面的代碼思路可以，針對不同題目代碼差異大，不列舉了
-
BFS
-
queue<int> q; //STL中的隊(duì)列容器 st[1] = true; // 表示1號點(diǎn)已經(jīng)被遍歷過 q.push(1); while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; // 表示點(diǎn)j已經(jīng)被遍歷過 q.push(j); } } }
-
最短路徑問題導(dǎo)圖
-
-
樸素Dijkstra（適合稠密圖，無負(fù)權(quán)值）
-
思路文章來源地址http://www.zghlxwxcb.cn/news/detail-851643.html
-
- 初始化（初始化dist，鄰接矩陣）
-
- 循環(huán)n-1次，每次找最短dist[t]，用t更新其它點(diǎn)的距離
-
-
//初始化，b[]標(biāo)記是否已經(jīng)訪問，dist[]表示最短路徑，path[]表示前驅(qū)結(jié)點(diǎn) memset(g,0x3f,sizeof g); memset(dist,0x3f,sizeof dist); g[a][b]=min(c,g[a][b]); //如果有重邊，需要選小的 //Dijkstra bool dijkstra(){ dist[1]=0; for(int i=0;i<n-1;i++){ int t=-1; //找最小的dist for(int j=1;j<=n;j++){ if((t==-1||dist[j]<dist[t])&&!b[j]){ t=j; } } //更新已訪問的點(diǎn) b[t]=1; //更新該點(diǎn)其它距離 for(int j=1;j<=n;j++) dist[j]=min(g[t][j]+dist[t],dist[j]); } if(dist[n]==0x3f3f3f3f) return 0; else return 1; }
-
-
堆優(yōu)化的Dijkstra（適合稀疏圖，無負(fù)權(quán)值）
-
思路
- 在樸素Dijkstra算法的基礎(chǔ)上
初始化（初始化dist，鄰接矩陣）
循環(huán)n-1次，每次找最短dist[t]，用t更新其它點(diǎn)的距離
其中找最短dist[t]需要O(n2)，故利用一個(gè)堆把該步驟降為O(n)
隨之用堆更新的時(shí)間復(fù)雜度上升為O(mlogn)，故適合于稀疏圖
- 在樸素Dijkstra算法的基礎(chǔ)上
-
-
int dijkstra(){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; dist[1]=0; q.push({0,1}); while(q.size()){ pair<int,int> temp=q.top(); q.pop(); if(st[temp.second]) continue; //若已訪問直接跳過，若在下方if語句中判斷時(shí)間差很多 st[temp.second]=1; //更新操作 for(int i=h[temp.second];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j]>temp.first+w[i]){ dist[j]=temp.first+w[i]; q.push({dist[j],j}); } } } if(dist[n]!=0x3f3f3f3f) return dist[n]; else return -1; } -
bellman-ford（負(fù)權(quán)值，若規(guī)定k條邊最短路徑則只能用它，O(nm)）
-
思路
- 思路：(很暴力，邊的存儲僅需要用結(jié)構(gòu)體數(shù)組即可)
for n 次
????用back數(shù)組備份dist，防止串聯(lián)（訪問前幾條邊改變數(shù)據(jù)后影響后面的訪問，會破壞k條邊的條件）
????for 所有邊 a，b，w
???????? dist[b] = min(dist[b], back[a]+w); //松弛操作
三角不等式：dist[b] <= dist[a]+w
補(bǔ)充：如果執(zhí)行n次依然更新了路徑，說明有n條的最短路徑，即有負(fù)權(quán)邊
- 思路：(很暴力，邊的存儲僅需要用結(jié)構(gòu)體數(shù)組即可)
-
struct line{ //定義結(jié)構(gòu)體 int a,b,w; }lines[N]; void bellman_ford(){ dist[1]=0; for(int i=0;i<k;i++){ memcpy(back,dist,sizeof dist); //備份防止串聯(lián) for(int j=0;j<m;j++){ if(dist[lines[j].b]>back[lines[j].a]+lines[j].w){//這里用back dist[lines[j].b]=back[lines[j].a]+lines[j].w; } } } if(dist[n]>0x3f3f3f3f/2) printf("impossible"); else printf("%d",dist[n]); }
-
-
SPFA（bellman-ford優(yōu)化，一般O(m),最壞O(nm)）
-
思路
- 在bellman-ford的基礎(chǔ)上，利用一個(gè)隊(duì)列與廣度優(yōu)先搜索，僅將變小的點(diǎn)加入隊(duì)列中；
-
補(bǔ)充
- 用一個(gè)cnt[]數(shù)組維護(hù)每個(gè)節(jié)點(diǎn)的最短路徑邊數(shù)，若邊數(shù)=n即有負(fù)權(quán)邊。需要考慮圖不連通，故需要初始化時(shí)把所有點(diǎn)加入隊(duì)列，且dist都相等即可。
-
void spfa(){ q.push(1); dist[1]=0; st[1]=1; while(q.size()){ int t=q.front(); q.pop(); st[t]=0; //SPFA與Dijkstra不同僅在于標(biāo)記數(shù)組用于標(biāo)記是否重復(fù)進(jìn)去隊(duì)列而非是否訪問過 for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(dist[j]>dist[t]+w[i]){ dist[j]=dist[t]+w[i]; if(!st[j]){ //改變后進(jìn)行判斷是否需要加入隊(duì)列 st[j]=1; q.push(j); } } } } if(dist[n]==0x3f3f3f3f) printf("impossible"); else printf("%d",dist[n]); }
-
-
Floyd
-
思路
- 三重循環(huán)，用鄰接矩陣存儲
外層循環(huán)每個(gè)要加入的點(diǎn)，雙層循環(huán)兩個(gè)要加入的節(jié)點(diǎn)，如果可加入其中且路徑邊短則更新即可。
- 三重循環(huán)，用鄰接矩陣存儲
-
初始化：
for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // 算法結(jié)束后，d[a][b]表示a到b的最短距離 void floyd() { for (int k = 1; k <= n; k ++ ) //每次要加入的點(diǎn) for (int i = 1; i <= n; i ++ ) //加入點(diǎn)i，j中 for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
-
-
最小生成樹與二分圖導(dǎo)圖
- 樸素Prim算法用于稠密圖，優(yōu)化版Prim和Kruskal算法側(cè)重于稀疏圖，由于堆優(yōu)化代碼長，故一般直接用Kruskal算法
-
-
Prim
-
思路
- 幾乎和dijkstra一樣，區(qū)別在標(biāo)記數(shù)組記錄的是進(jìn)入生成樹的節(jié)點(diǎn)，dist數(shù)組記錄的是各節(jié)點(diǎn)到生成樹的最短路徑；
-
void prim(){ dist[1]=0; for(int i=0;i<n;i++){ int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||dist[t]>dist[j])){ t=j; } } st[t]=1; res+=dist[t]; for(int j=1;j<=n;j++){ if(dist[j]>g[t][j]){ dist[j]=g[t][j]; } } } }
-
-
Kruskal文章來源：http://www.zghlxwxcb.cn/news/detail-851643.html
-
思路
- 用結(jié)構(gòu)體存邊，并排序，從最短的邊找起，若兩點(diǎn)不在一顆樹則連接在一起（并查集思想），直到所有點(diǎn)都用最短的邊連在一起
-
sort(lines,lines+m); //邊排序 for(int i=0;i<m;i++){ int a=find(lines[i].a),b=find(lines[i].b); if(a!=b){ h[b]=a; //若不是一棵樹操作 res+=lines[i].c; cnt++; } }- 并查集中find函數(shù)
-
-
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】考研真題攻克與重點(diǎn)知識點(diǎn)剖析 - 第 6 篇：圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
