圖系列
－ 圖存盤
圖
基于矩陣實作－－－適合稠密圖
基于鄰接鏈表實作－－－適合稀疏圖
設結點數為N
設邊數為M
稀疏還是稠密主要依據M和N*N關系界定．
一般M<N*N/2可界定為稀疏．M>=N*N/2可界定為稠密．
－ 圖演算法：深度搜索
演算法：單一結點深度訪問
演算法描述：
對結點ｐ的深度訪問：
訪問ｐ
按分治方式對結點每個未被訪問孩子執行深度訪問
演算法：圖的深度訪問
演算法描述：
回圈迭代：
從圖中未被訪問結點中選出一個ｐ，對ｐ執行單一結點深度訪問
回圈迭代的終止：
無法選出未被訪問結點
演算法解決的問題＆性質：
單一結點深度訪問時，可完成所有從結點可達結點的訪問
且訪問程序是下降，
下降到底依次上升一層執行兄弟結點訪問這樣一個動態程序
－ 圖演算法：廣度搜索
演算法：單一結點廣度訪問
演算法描述：
對結點ｐ的廣度訪問：
ｐ入佇列
回圈迭代：
出佇列得到ｑ．
對ｑ訪問．對ｑ所有可達且尚未訪問結點ｔ執行入佇列．
回圈迭代的終止：
無結點可出佇列
演算法:圖的廣度訪問
演算法描述：
回圈迭代：
從圖中未被訪問結點中選出一個ｐ，對ｐ執行單一結點廣度訪問
回圈迭代的終止：
無法選出未被訪問結點
演算法解決的問題＆性質：
單一結點廣度訪問時，可完成所有從結點可達結點的訪問
且訪問程序是一層一層，訪問完一層，再訪問下一層這樣一個動態程序
－ 圖演算法：最小生成樹
最小生成樹－－prim和kruskal
prim基于結點迭代，更適合用于稠密圖
kruskal基于邊迭代，更適合用于稀疏圖
演算法：稠密圖下用prim實作最小生成樹求取演算法
演算法描述：
選擇一個結點作為樹的根結點
選擇結點ｐ已經在最小生成樹中
對所有ｐ可達結點更新結點距離最小生成樹的距離
回圈迭代：
從不在最小生成樹的結點中選出距離樹距離最小的結點ｔ
對ｔ可達且不在最小生成樹中的結點更新其與最小生成樹的距離
回圈迭代的終止：
無法選出ｔ或選出ｔ到最小生成樹的距離為無限
演算法解決的問題＆性質：
最小生成樹用代價最小的邊集合得到一個連通圖中任意兩點的方案
最小生成樹演算法存在的意義在于為無向連通圖
找出一個代價最小的可連通圖中任意兩個頂點的方案
對不連通圖，運行結果是回傳失敗
－ 圖演算法：指定結點ｐ到其余所有結點的最短路徑Dijstra
指定結點到其余所有結點的最短路徑
Dijstra演算法，基于結點迭代
演算法描述：
給定結點ｐ
設ｐ到ｐ的最短路徑為０
更新所有ｐ可達且到ｐ最短路徑尚未確定結點到ｐ的能達到的最短路徑
回圈迭代：
選擇到ｐ最短路徑尚未確定結點中
到ｐ能達到的最短路徑最小的那個ｔ．
ｔ到ｐ的最短路徑變為確定．
對ｔ可達且所有到ｐ最短路徑尚未確定結點
進行到ｐ的能達到的最短路徑的檢測＆更新
回圈迭代的終止：
無法選出ｔ
演算法解決的問題＆性質：
求取ｐ到其余所有結點最短路徑解決的是權重非負圖，
ｐ到每個結點一條最短路徑
Dijstra演算法產生的背景是為路由器充當結點的計算機網路中路由器
確定到其他路由器的最短路徑并據此設定路由器的轉發表
也屬于基于結點的迭代
－ 圖演算法：拓撲排序
演算法描述：
對每個結點計算其入度
入度為０結點單獨存入一個集合Ａ
回圈迭代：
選出一個入度為０結點ｐ
更新所有從ｐ可達且尚未處理結點ｐ的入度，若入度變為０放入集合Ａ
回圈迭代終止：
無法選出入度為０節點
演算法解決的問題＆性質
如果結束時，所有結點已被處理，則按結點處理順序產生的序列中，
前面結點可能有到達后面結點的路徑，
而后面結點不可能有到達前面結點路徑
如果結束時，仍有結點未被處理，則剩余未處理結點存在環路
拓撲排序可用于有向圖的環路檢測，
結點的可達與不可達性質也可用于解決特定問題
－ 圖演算法：適合稀疏圖的鄰接表存盤及求取最小生成樹的Kruskal演算法
圖的鄰接表存盤－－－適合稀疏圖
對稀疏圖求解最小生成樹更適合用Kruskal[基于邊迭代]
對邊按權重升序排序
依次處理每條邊
若邊的兩個結點屬于不同集合，執行集合合并．邊被標記為選中．
若邊的兩個結點屬于同一集合，略過
處理結束
若選中邊數為N-1．
所有結點均屬于同一集合．
求得最小生成樹．
否則，無法求得最小生成樹．
－ 圖演算法：關鍵路徑＆關鍵結點
略
特定條件圖，
對每個結點從ｓ到ｅ廣度搜索得到每個結點最早完成時間
特定條件圖逆轉，
對從ｅ到ｓ每個結點廣度搜索得到每個結點最晚完成時間
最早完成時間與最晚完成時間一致結點為關鍵結點．
關鍵結點間路徑為關鍵路徑．
排序
－ 歸并排序
劃分，對劃分后子問題執行歸并排序
對兩個有序子問題執行合并
時間效率穩定為O(Nlog(N))
－ 快速排序
選出主元，按主元進行劃分
劃分后兩個子問題執行快速排序
可能退化到O(N^2)
平均效率為O(Nlog(N))
－ 基數排序
分配收集
［從最低位，
按最低位值對所有元素進行桶分配，按桶有序收集元素．
對收集后元素，
按次低位進行桶分配，再次按次低位的桶進行元素收集．
回圈迭代，最高位收集完畢即完成排序］
適用場景受限，沒有特殊需要使用快速排序／歸并排序作元素排序即可
效率優化
－ 動態規劃
是針對運用分治的演算法中，存在重復求解子問題現象下，
對已經求解的子問題進行記錄，
求解一個子問題時，
先查詢此問題是否已被求解，
來避免重復求解同一子問題的效率優化方法
－ 貪心演算法
是適合在每一步有多種選擇，
每種選擇后得到一個規模更小的同類問題．
可以嘗試每種選擇并得到一個結果，在歸并選出最終結果．
但若問題滿足某種性質，利用此性質，
可以在每一步只嘗試一種選擇，
這樣的情況稱為貪心演算法．
數學
數學：
求素數：只能被１和其自身整除的數
最小公倍數，最大公約數
對ａ，ｂ
有ａ＊ｂ＝ａｂ的最大公約數＊ａｂ的最小公倍數
求解ａｂ的最大公約數[a >= b]
int temp1 = a;
int temp2 = b;
temp1 = b;
temp2 = a % b;
回圈迭代的終止：
temp2為０
temp1為ａｂ的最大公約數
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262027.html
標籤：其他
上一篇：絕對差不超過限制的最長連續子陣列