圖論演算法理論實現及
① 圖論演算法matlab實現問題
參考樓上給的鏈接，稍微做了一點修改，供參考。
修改的地方包括：
1、原程序為函數，提供了鄰接矩陣和關聯矩陣的雙向轉換，這里針對樓主的需求改為腳本，直接運行即可將鄰接矩陣轉為關聯矩陣。
2、部分語句修改更符合MATLAB的通行寫法，如：
sum(sum(F))改為sum(F(:))，
W(i,k)=1; W(j,k)=1;改為W([i j],k)=1;
3、考慮到鄰接矩陣為對稱陣，第二個for循環改為只針對半個矩陣，減少計算量（對於樓主的這個具體作用微乎其微）。
4、原程序有錯誤，在else分支fprint為fprintf之誤（其實我看到該程序的第一眼就注意到了這個錯誤，擔心還存在其它問題，所以進行了改寫）。
F=[0 1 1 1;1 0 1 1;1 1 0 1;1 1 1 0]; % 鄰接矩陣
m = sum(F(:))/2; % 圖的邊數
n = size(F,1); % 頂點數
W = zeros(n,m);
k=1;
for i = 1:n
for j = 1:i
if F(i,j)~=0
W([i j],k)=1;
k = k + 1;
end
end
end
W
② 簡介圖論演算法
圖論101
圖論是數學的一個非常廣泛哪譽的分支，非常適用於現實世界中的問題。 最初，圖論是"發明"來解決現實問題的，此後，它像所有其他數學分支一樣，被抽象數學家所劫持。
在本教程和後續教程中，我們將介紹一些圖論演算法及其在python中的實現。 現在，回到主題。
簡而言之，圖是一組頂點/節點和邊。 如果您對" set"不滿意，請用collection代替。
在上圖中，頂點/節點將是人物。
頂點是圖的基本單位。 它幾乎可以代表任何實體，通常以圓圈表示。
在上圖中，連接襲緩陪人的線是邊。
頂點之間的線或連接稱為邊。 它可以表示頂點之間的任何類型的關系。
邊上具有方向的圖稱為有向圖。 它可以用來顯示與前輩（從父母到孩子的箭頭）或祖先（從孩子到父母的箭頭）的關系。
邊上沒有方向的邊的圖稱為無向圖。 它可用於顯示雙向道路。
邊上帶有數字的圖形，代表交易成本，旅途公平，城市之間的距離等。它可以具有任何類型的邊。
沒有循環的無向圖是一棵樹。 在這里，循環意味著只有一種方法可以通過跟隨給定其他節點的邊緣來到達節點。
一棵樹的所有節點都通過一條邊連接到其他某個節點，並且有N個節點的N-1個邊。
表示圖形的方法有很多，最常見的兩種是：
假設圖中有N個節點。 我們可以使用具有N行和N列的矩陣來表示它，其中該矩陣的行和列將代表一個節點，並且其中的條目代表有向邊（有或沒有權重）。
它們形成代錶行的節點到代表列的節點。 通常，0或無窮大用於表示節點之間沒有邊緣。 在Python中，鄰接矩陣可以表示為：
類似地，對於拍蠢N個節點的圖，我們可以使用鄰接表來表示該圖，其中節點的所有邊都保留在元組列表（節點，權重）中。 在python中，它可以表示為：
我使用嵌套字典（這就是我所說的）和帶集合的字典（如果節點沒有權重的邊）來表示圖。
在下一篇文章中，我將使用不同的方法發布精心設計的圖類的Python代碼，我們將使用該代碼來實現圖演算法。
(本文翻譯自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，參考：https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)
③ 求圖論的生成子圖演算法，要求生成盡可能多的子圖
在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。20世紀80-90年代曾邦哲的綜合系統論（結構論）觀將「四色猜想」命題轉換等價為「互鄰面最大的多面體是四面體」。四色猜想有一段有趣的歷史。每個地圖可以導出一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連接。所以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數拓撲圖論等分支的發展起到推動作用。 （下圖是在上下對折再左右對折以後形成一個輪胎形狀，有7個區域兩兩相連，就是說在一個環面上作圖，需要7種顏色，外國數學家構造林格證明：Np=[(7+√1+48p)/2]，p=1，N1=7。
圖論中最著名的四色猜想解決辦法 韓世君利用三角形性質和數學歸納法解決了四色猜想 摘要：將平面圖的不相連點使其相連（這樣增加著色難度），形成有許多三角形相連的平面圖，根據三角形的穩定性，利用數學歸納法，平面圖進行著色最多需4種顏色。 定理：在平面圖中,對不同頂點進行著色,相鄰頂點著不同顏色,不相鄰頂點著相同顏色,則最多需4種顏色。 證明：在平面圖中，不在同一直線上的三點決定一個平面，那麼三點構成的三角形是平面圖中最基本、最簡單、最穩定、密閉的圖形。 由於在對地圖著色過程中不考慮圖的具體形狀只考慮點是否相鄰，將平面圖的不相連點使其相連（這樣增加著色難度），形成有許多三角形相連的平面圖（三點以下肯定成立）。如圖1：添加輔助線（不相鄰的點使其相鄰，這樣就增加了著色的色數，有利於證明），將圖1分解為4個△ABC。 在平面圖中的無數點中，任取相鄰三點構成各點相鄰的△ABC（見圖2），則需3種顏色A B C,在平面圖中再任取一點 D 與 A B C 三點相鄰,同時D又與A B C三點相連後形成三角形。任取一點E與 A、B、C、D四色相連，E必與四色之一色相同即E點在△ABD中與C色相同、在△ACD中與B色相同、在△BCD中與A色相同、在△ABC外與D色相同，E與另外三色相連形成新的三角形。 在三角形的三點之外任取一點只有在三角形的內部和外部兩種情況且這兩種情況的點不會相鄰，該點最多與三角形的三點相連且又形成新的三角形。 繼續選取一點進行著色，該點同樣最多與三角形的三點相連且又形成新的三角形，該點至少為四色中的一色。逐點（第n點）著色至將所有點（第n+1點）著色只須A、B、C、D四色其中一色。 圖的著色方法：任意一張地圖，將孤立的點用一種顏色著色（A色），不能形成密閉圖形的相連的點用兩種顏色（A、B色）。將剩餘的點不相連的用虛線使其相連形成許多三角形，完全不相連的圖不進行相連。任取相連三點著三種顏色（A、B、C色），再取與其相連的點，如果與A、B、C三色的點都相連著D色，否則著與其不相連的其中一色，用虛線相連的點可以用同一種顏色也可以用兩種顏色，依次取與著色的點相連的點用以上方法進行著色。這樣對所有的點進行著色最多用四色（A、B、C、D色）。 圖論的廣泛應用，促進了它自身的發展。20世紀40-60年代，擬陣理論、超圖理論 、極圖理論，以及代數圖論、拓撲圖論等都有很大的發展 拓撲學在泛函分析、李群論、微分幾何、微分方程和其他許多數學分支中都有廣泛的應用。 （右圖是：下面的三叉安在上面的環面上，就是有3個洞的9個兩兩相連區域，上面的圖上下對折再左右對折就是一個輪胎形狀環面圖2）
左圖是虧格為4時10個兩兩相連區域構造，上圖上下對折，再左右對折，形成一個輪胎形狀，再把下面的四叉按照A,B,C,D編號安上，就是有4個洞的兩兩相連區域圖3（王曉明構造）。
④ 圖論演算法的介紹
圖論演算法在計算機科學中扮演著很重要的角色，它提供了對很多問題都有效的一種簡單而系統的建模方式。很多問題都可以轉化為圖論問題，然後用圖論的基本演算法加以解決。遺傳演算法是解優化問題的有效演算法，而並行遺傳演算法是遺傳演算法研究中的一個重要方向，受到了研究人員的高度重視。
⑤ 圖論演算法及其MATLAB實現的圖書目錄
第1章 圖論的基礎知識1
1.1圖論的起源1
1.2著名的圖論學者——歐拉1
1.3圖2
1.4特殊圖類3
1.5有向圖4
1.6圖的矩陣表示5
1.6.1鄰接矩陣5
1.6.2關聯矩陣5
1.7圖論的基本性質和定理6
1.8計算有向圖的可達矩陣的演算法及其MATLAB實現6
1.9關聯矩陣和鄰接矩陣的相互轉換演算法及其MATLAB實現7
習題一11
第2章 最短路12
2.1路12
2.2最短路問題13
2.3求連通圖最短距離矩陣的演算法及其MATLAB實現14
2.4求兩點間最短路的Dijkstra演算法及其MATLAB實現15
2.4.1 Dijkstra演算法16
2.4.2 Dijkstra演算法的MATLAB實現16
2.5求兩點間最短路的改進的Dijkstra演算法及其MATLAB實現18
2.5.1 Dijkstra矩陣演算法Ⅰ18
2.5.2 Dijkstra矩陣演算法Ⅱ18
2.6 求兩點間最短路的WarshallFloyd演算法及其MATLAB實現21
2.6.1 Floyd演算法的基本思想22
2.6.2 Floyd演算法的基本步驟22
2.6.3 WarshallFloyd演算法的MATLAB實現22
2.7求任意兩點間最短路的演算法及其MATLAB實現25
2.8求從一固定點到其他所有點最短路的演算法及其MATLAB實現27
2.9求必須通過指定兩個點的最短路的演算法及其MATLAB實現29
2.10求圖的兩頂點間最短路與次短路的演算法及其MATLAB實現32
2.11求最大可靠路的演算法及其MATLAB實現34
2.12求最大期望容量路的演算法及其MATLAB實現36
習題二38
第3章 連通圖40
3.1判斷圖的連通性演算法及其MATLAB實現40
3.2連通圖的中心和加權中心的演算法及其MATLAB實現42
3.3連通無向圖一般中心的演算法及其MATLAB實現44
習題三46
第4章 樹48
4.1樹及其性質48
4.2割點、割邊、割集50
4.3二元樹與Huffman樹51
4.3.1有序二元樹51
4.3.2 Huffman樹51
4.4求Huffman樹及其MATLAB實現52
4.5廣度優先搜索演算法及其MATLAB實現55
4.6深度優先搜索演算法及其MATLAB實現57
4.7求割點演算法及其MATLAB實現61
4.8生成樹及其個數65
4.9求無向圖的生成樹演算法及其MATLAB實現67
4.10求有向圖的生成樹演算法及其MATLAB實現69
4.11求有向連通圖的外向樹與內向樹數目的演算法及其MATLAB實現71
4.12最小生成樹問題73
4.13求最小生成樹的Kruskal演算法及其MATLAB實現74
4.13.1 Kruskal演算法的基本思想74
4.13.2 Kruskal演算法的MATLAB實現74
4.14求最小生成樹的Prim演算法及其MATLAB實現76
4.14.1 Prim演算法的基本思想76
4.14.2 Prim演算法的MATLAB實現77
習題四79
第5章Euler圖和Hamilton圖81
5.1 Euler圖81
5.2「一筆畫」問題及其理論81
5.3中國郵遞員問題82
5.4 Fleury演算法及其MATLAB實現82
5.4.1 Fleury演算法的步驟82
5.4.2 Fleury演算法的MATLAB實現82
5.5 Hamilton圖87
5.6旅行售貨員問題88
5.7改良圈演算法及其MATLAB實現89
習題五92
第6章 匹配問題及其演算法93
6.1問題起源——婚配問題93
6.2二分圖的有關知識93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5應用案例——BernolliEuler錯放信箋問題95
6.6尋求圖的一個較大基數匹配演算法及其MATLAB實現95
6.7人員分配問題97
6.8匈牙利演算法及其MATLAB實現97
6.8.1匈牙利演算法基本步驟97
6.8.2匈牙利演算法的MATLAB實現98
6.8.3案例及其MATLAB實現100
6.9最優分配問題101
6.10 KuhnMunkres演算法及其MATLAB實現101
6.10.1 KuhnMunkres演算法的基本思想101
6.10.2利用可行頂點標記求最佳匹配的KuhnMunkras演算法步驟102
6.10.3 KuhnMunkres演算法的MATLAB實現102
6.10.4簡單實驗105
習題六107
第7章 網路流的演算法108
7.1網路、流和割108
7.1.1網路和流108
7.1.2割109
7.2網路的最大流問題110
7.3最大流最小割定理110
7.4 FordFulkerson標號演算法及其MATLAB實現111
7.4.1 FordFulkerson標號演算法的基本步驟111
7.4.2 FordFulkerson 標號演算法的MATLAB實現112
7.4.3案例及其MATLAB實現113
7.5 Dinic演算法及其MATLAB實現114
7.5.1 Dinic演算法的基本思想114
7.5.2 Dinic演算法的MATLAB實現115
7.5.3案例
⑥ 基於圖論的最小多邊形自動搜索演算法
圖是由點集和邊集所構成的抽象概念，圖的性質實質上可以表現為拓撲關系。如圖4.8b所示，點集由分叉點構成(4個分叉點，分別是1，2，3，4)，邊集則由地層線構成(7條地層線，分別是①，②，③，④，⑤，⑥，⑦)。需要說明的是，這里的邊是廣義上的邊，可能是直線段，也可能是多線段。
最小多邊形的自動搜索在GIS的空間分析中應用較多，搜索可分為無拓撲和含拓撲兩類。無拓撲自動搜索則完全依靠幾何計算來判斷，如夾角變化趨勢的多邊形自動搜索演算法(梁曉文等，2005)，該演算法主要依靠弧段間夾角計算來判斷，通過「左轉」或「右轉」的方法能夠唯一確定最小多邊形，原理簡單，但程序設計過程極其煩瑣。採用圖論的方法來實現，原理相對復雜，需要掌握數據結構知識，但程序代碼設計過程比較簡潔，具有擴展性。
為了簡單起見，以圖4.8b中地層線①為例，說明搜索過程。從分叉點1開始，沿地層線①在分叉點2與地層線②和③鄰接，地層線②和③又分別在分叉點3和4與兩地層線鄰接。整個鄰接關系可以用一個樹(tree)型結構來表示(圖4.10)，終止條件是回到分叉點1，形成閉合迴路或者出現自相交，則停止搜索。這樣，產生4條有意義的多邊形為：1-①-2-②-3-⑥-1，1-①-2-②-3-④-4-⑤-1，1-①-2-③-4-④-3-⑥-1，1-①-2-③-4-⑤-1。
圖4.10 分叉點1沿①為起始方向的連通圖
在上述4條連通多邊形中，面積最小者對應的就是一個最小多邊形(周秋生，1996)。若多邊形點對為(x1，y1)，(x2，y2)，…，(xn，yn)，面積可採用下式來計算：
S=
最終，得到3個最小多邊形。從圖論的觀點來看，所研究的圖是一個連通的平面圖。若圖有n個分叉點，m條廣義邊，p個最小多邊形，則平面圖的面數(包括外部面)f=p+1。
根據歐拉公式(孫家廣，1998)：
f+m-n=2 (4.2)
可以得到最小多邊形數目為
p=m-n+1 (4.3)
見圖4.4b中，m=7，n=5，則p=7-5+1=3。據此可以作為搜索結果正確與否的判斷方式之一。
⑦ 圖論演算法及其MATLAB實現的圖書前言
圖論演算法廣泛應用於物理、化學、運籌學、計算機科學、電子學、資訊理論、控制論、網路理論、管理科學、社會科學等眾多學科領域。隨著這些學科的發展，特別是計算機科學的快速發展，又大大促進了圖論和其他學科的發展。
圖論演算法是計算機科學的核心。近幾年，隨著強有力的MATLAB等數學軟體的迅速發展，圖論演算法在數學和計算機等各學科方面的應用越來越廣泛，從而使各學科的研究者越來越多地重視圖論演算法及其MATLAB實現和典型案例，而市場上又缺少這方面的指導性書籍。
本書將圖論的基礎知識、圖論的著名問題以及相應的MATLAB程序代碼和簡單實例完美地結合在一起，力求語言簡潔易懂，問題廣泛有趣，演算法科學，實例淺顯，增強MATLAB實現的技巧性和操作性。讀者可以通過簡單案例，把圖論的重要演算法與MATLAB編程完美結合。
本書力求內容豐富，各章節相互聯系，具備指導性書籍的系統性、科學性、實用性和引導性；同時，各章又相對獨立，自成體系，為讀者提供極大方便。
本書的創新之處在於，每一章均以著名實際問題為引入點，以圖論演算法為指導線，運用簡單案例達到與MATLAB實現的完美結合，真正讓各層次的讀者學會運用圖論理論解決實際問題，從而培養讀者的圖論思維，使讀者驚嘆圖論方法的美妙與魅力。最後還為讀者提供了當今圖論標號方面等未解決的問題。
本書將在每一章節中給出著名圖論的演算法步驟及其一般MATLAB程序；同時，緊隨每個案例分析，均給出解決問題的MATLAB源程序，這樣對於初學者來說，具有很強的編程操作性。
本書是在中國地質大學（北京）王海英多年專業講義的基礎上重新修訂編寫而成，其中，山東體育學院體育運動學校的李傳濤完成了本書程序的編寫工作；中國科學院數學與系統科學院的黃強完成了本書全部程序的調試、修改和圖形繪制等工作，