目錄

1.回路的判斷：

2.普利姆-最小生成樹

3.克魯斯特卡爾-最小生成樹

4.迪杰斯特拉-最短路徑

5.圖的最長路徑(不走重復(fù)路)

6.有向無環(huán)圖的關(guān)鍵路徑

---

1.回路的判斷：

用深度優(yōu)先遍歷，在有向圖中如果遍歷過程中重復(fù)訪問到已經(jīng)訪問過的點，那么這個有向圖就是就是有回路；如果是無向圖，重復(fù)訪問到了祖先結(jié)點那么這個無向圖就存在回路。

2.普利姆-最小生成樹

需要輸入一個開始結(jié)點，新建一個對象數(shù)組arr [ size?]?(nodeIndex,lowcost)? ，其中nodeIndex指的是結(jié)點在鄰接矩陣或者鄰接表的數(shù)組下標(biāo),其中arr[ i ] 表示? nodeIndex 到 i 的 是最短路徑,消耗是lowcost。

對新加入的結(jié)點進行遍歷邊，比對 arr[i] ,如果新的邊比arr[i]更小那么就重新覆蓋 arr[i]的值，然后再旋轉(zhuǎn)lowcost最小的點，再進行進行加入。反復(fù)執(zhí)行次操作。

?

1.假設(shè)剛開始輸入是A ，那么遍歷 A 的邊 ,初始化最小值 ,得到最小的邊是（A,C)，.然后把C 加入到集合

2 遍歷新結(jié)點C的所有邊,其中(C,B)要比原來的(A,B)要小?；(C,E)，(C,F)要比原先的(A,E)? (A,F)要小，覆蓋值，不斷重復(fù)步驟2，直到遍歷n次(結(jié)點總數(shù))

次數(shù)\結(jié)點	A	B	C	D	E	F	已加入的點	最小結(jié)點	備注
1	(null)	（A,6）	（A,1）	(A,5)	(A,∞)	(A,∞)	（A）	C	把C加入到集合
2	(null)	(C,5)	(null)	(A,5)	(C,6)	(C,4)	(A,C)	F	(C,B)比原來的（A,B）小，覆蓋
3	(null)	(C,5)	(null)	(F,2)	(C,6)	(null)	(A,C,F)	D	(F,D)比(A,D)小
4	(null)	(C,5)	(null)	(null)	(C,6)	(null)	(A,C,F,D)	B	D的邊沒有原來的小
5	(null)	(null)	(null)	(null)	(B,3)	(null)	(A,C,F,D,B)	E	(B,E)比(C,E)小
6	(null)	(null)	(null)	(null)	(null)	(null)	(A,C,F,D,B,E)	結(jié)束	總共6個結(jié)點,共遍歷6次

3.克魯斯特卡爾-最小生成樹

? 剛開始,每個結(jié)點為各立為一組連通分量。連通分量之間選出最短的邊，同通過最短的邊，來合并連通分量，反復(fù)直到所有結(jié)點在同一個連通分量中，結(jié)束,或者無可以連接的邊結(jié)束。當(dāng)添加最短邊時出現(xiàn)回路則選下一條邊

對邊進行從小到大排序:

(A,C,1)(D,F,2)(B,E,3)(C,F,4)(A,D,5)(B,C,5)(C,D,5)(A,B,6)(C,E,6)(E,F,6)

初始連通分量組	A	B	C	D	E	F
第1小邊(A,C)	(A,C)		B	D	E	F
第2小邊(D,F)	(A,C)		B	(D,F)		E
第3小邊(B,E)	(A,C)		(B,E)		(D,F)
第4小邊(C,F)	(A,C,D,F)				(B,E)
第5小邊(A,D),已在同一集合中,形成回路	(A,C,D,F)				(B,E)
第6小邊(B,C)	(A,C,D,F,B,E)
全部結(jié)點在同一集合中，結(jié)束	?	?	?	?	?	?

4.迪杰斯特拉-最短路徑

? ? 目標(biāo)：輸入一個起始結(jié)點,求起始結(jié)點到其他結(jié)點的最短路徑和代價。需要提前初始化好鄰接矩陣 adjacencyMatrix_。

假設(shè)輸入起始點A，當(dāng)前路徑?A? (也是已訪問的點)，

對象數(shù)組的對象元素 時? ?（最小代價 lowcost_，和 最短路徑? pathIndex_）

1.求到所有點的代價(A,C,10) (A,E,30) ,(A,F,100) ,選取最小代價的直接目標(biāo)結(jié)點currentPathIndex(C)。加入到當(dāng)前路徑currentPath (A,C)? 代價lowestCost為10.

2.即

currentPath= lowestPaths[currentPathIndex].pathIndex_ + currentPathIndex ; lowestCost=lowestPaths[currentPathIndex].lowcost_

3.遍歷LowestPaths[0....j...n]? (排除在CurrentPath的點)

if (lowestCost+ adjacencyMatrix_[currentPathIndex][j] <lowestPaths[j].lowcost_) {lowestPaths[j].lowcost_= lowestCost+ adjacencyMatrix_[currentPathIndex][j] ;lowestPaths[j].pathIndex_=currentPath; }

? 重復(fù) 2，3

求解步驟：

?

5.圖的最長路徑(不走重復(fù)路)

? ? ?不管是有向圖或者無向圖都適用的遞歸方法，建議使用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu),當(dāng)圖是有向無環(huán)圖的時候，求的是關(guān)鍵路徑。主要思想是:當(dāng)已知源節(jié)點到目標(biāo)結(jié)點的前繼結(jié)點的最長路徑時， 就可求得??源節(jié)點到目標(biāo)結(jié)點的最長路徑..

加入求 結(jié)點V0 到 Vn 的最長路徑。那么首先要列出Vn的前驅(qū)結(jié)點集(Vxi,Vxi....)?

有遞歸函數(shù)fun(V0,Vn) 表示V0到Vn的最長路徑?。其值? =Max(fun(V0,Vxi)+arc[Vxi][Vn]).通過次方法找到最長路徑。找最短路徑也可以參考此方法

函數(shù)格式? ? ? double fun( src , target , vector<int> & hasVisits)

提前初始化鄰接矩陣 arc[][]。

0.如果源結(jié)點和目標(biāo)結(jié)點相同則返回0。

1.已訪問的結(jié)點集 hasVisits為引用形參，把目標(biāo)結(jié)點target 加入進該集合。

2.尋找還未訪問的目標(biāo)結(jié)點的前繼結(jié)點。

3.判斷鄰接矩陣arc[源結(jié)點][目標(biāo)結(jié)點] 的是否是∞，如果為真初始化最大路徑maxValue為最小浮點值,如果為假? maxValue為設(shè)置為arc[源結(jié)點][目標(biāo)結(jié)點]。

4..拷貝hasVisits出一個副本,遍歷前繼結(jié)點集合，

value = fun(源結(jié)點，某個前繼結(jié)點,hasVisits的副本引用) + arc[某個前繼結(jié)點][目標(biāo)結(jié)點]

，如果value大于maxvalue時，maxvalue賦值成value且 hasVisit賦值成hasVisits的副本引用。最后遞歸結(jié)束時hasVisits就是最大路徑，返回值就是最大代價。

6.有向無環(huán)圖的關(guān)鍵路徑

主要思想就是 找出 最早開始時間和最晚結(jié)束時間相等的結(jié)點

起始結(jié)點的最早開始時間是 0 ,把代價當(dāng)作時間。

每個結(jié)點最早開始時間 =? ?max(前繼結(jié)點的最早開始時間+ arc[前繼結(jié)點][當(dāng)前結(jié)點])

終點結(jié)點的最晚結(jié)束時間=終點結(jié)點的最早開始時間。

每個結(jié)點最晚結(jié)束時間 =? ? min((后繼結(jié)點的最晚結(jié)束時間? ?-? arc[當(dāng)前結(jié)點][后繼結(jié)點])?

最早開始時間和最晚結(jié)束時間相等的結(jié)點就是關(guān)鍵結(jié)點，通路就是關(guān)鍵路徑

總結(jié)

以上是生活随笔為你收集整理的C++ 数据结构-图相关操作的算法思路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。