數學模組化圖論算法學習總結
圖論基本知識
B站視訊：
https://www.bilibili.com/video/av18374161/?p=35
https://www.bilibili.com/video/av37498689/?p=7
圖論中的圈與塊：
https://wenku.baidu.com/view/44777a20a5e9856a5612604a.html
一、Dijkstra& Floyd求解最短路徑
1.1 Dijkstra (MATLAB C#)
采用貪心算法（Greedy Algorithm）範式進行設計
B站MATLAB實作：https://www.bilibili.com/video/av20238704/?p=6
C#實作：https://www.cnblogs.com/mingjiatang/p/5974451.html
1.2 Floyd (MATLAB) Bellman-Ford
用于計算帶權有向圖中單源最短路徑。
采用動态規劃（Dynamic Programming）進行設計
B站MATLAB實作：https://www.bilibili.com/video/av20238704/?p=6
總結：到問題，轉化為帶權鄰接矩陣，然後輸入程式。數學模組化時可以用不同算法比較分析，更有說服力。
二、Kruskal& Prim求解最小生成樹
B站視訊，講的特别好！
https://www.bilibili.com/video/av47042691?from=search&seid=4115249733910833698
2.1最小生成樹
生成樹：
i. 不能有環
ii. 必須連接配接圖中的全部頂點
是以最小生成樹的任意兩個頂點之間可以連通，對于有N個頂點的樹，其邊的個數為N-1。
最小生成樹：
對于一個圖，可以有很多生成樹，邊的權值相加最小的就是最小生成樹。
應用：
如幾個城市之間鋪設光纜，按最小生成樹鋪設，就可以實作幾個城市之間都能連通，所需成本又最小。
2.2 Kruskal
上面B站視訊截圖：
算法思想：
i. 把圖中所有邊按權值從小到大排列。
ii. 每次選擇權值最小的邊放入圖中。如果沒有形成環，那麼這條邊就是最小生成樹中的一條邊，否則，丢棄它，繼續選擇剩下的最小的邊嘗試。
iii. 直到選擇了N-1條邊，結束。
C語言實作：
https://www.cnblogs.com/skywang12345/p/3711496.html
2.3 Prim
上面B站視訊截圖：
算法思想：
i. 從一個頂點開始，選擇與該頂點相連的權值最小的邊，将這條邊的另一個頂點納入已選集合。
ii. 找出已選集合所有頂點和未選集合所有頂點之間的相連的權值最小的邊，将該邊和與其相連的頂點加入已選集合。
iii. 循環ii，結束。
實作：（有很多，網上搜）
https://www.cnblogs.com/ITgaozy/p/5198119.html
https://cloud.tencent.com/developer/article/1051931
三、最大流
管道網絡中每條邊的最大通過能力（容量）是有限的，實際流量不超過容量。
最大流問題(maximum flow problem)，一種組合最優化問題，就是要讨論如何充分利用裝置的能力，使得運輸的流量最大，以取得最好的效果。
基本概念：
https://baike.baidu.com/item/最大流問題/19144252?fr=aladdin
算法：FF算法、EK算法、dinic算法
https://blog.csdn.net/qq_41357771/article/details/79416899
EK算法：BFS找增廣路
https://www.bilibili.com/video/av18567992/?p=1
dinic算法
https://www.bilibili.com/video/av18800207?from=search&seid=15254823874702529609
四、二分比對，匈牙利算法
https://www.bilibili.com/video/av16362938?from=search&seid=12661245930214840970
二分圖
找增廣路