matlab最小生成樹演算法
1. MATLAB及圖論程序
這個我做過, 其實你要做的是把每個節點先標號, 無論abcdefg也好, 還是1234567, 一一標號,
然後用一個二維數組做存路徑用,
無向圖的話, 例如1 到 2之間, 那麼就 path(1,1) = 1, path(1,2) =2; 3 和2 之間 也是path(2,1)=2, path(2,2)= 3; 可以左邊小,右邊大, 這樣檢索起來比較方便;
然後有向圖的話就是左邊是起始點,右邊是end就行了~
如果有權值的話,就用三維的, 例如 2, 3 ,10 ; 那麼就是2和3之間的權是10, 有向的話可以表示為2到3的權等於10
2. 圖的相關演算法（二）：最小生成樹演算法
在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，並使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。
例如，對於上圖中的連通網可以有多棵權值總和不相同的生成樹。
克魯斯卡爾（Kruskal）演算法，是用來求加權連通圖的最小生成樹的演算法。
基本思想 ：按照權值從小到大的順序選擇n-1條邊，並保證這n-1條邊不構成迴路。
具體做法 ：首先構造一個只含n個頂點的森林，然後依照權值從小到大從連通網中選擇邊加入到森林羨冊乎中，並使得森林不產生迴路，直到森林變成一棵樹為止。
以圖G4為例（更詳細的可以參考《演算法導論》p367），對Kruskal進行演示（假設，用數組R保存最小生成樹結果）。
第1步 ：將邊<E,F>加入R中。
邊<兄悉E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步 ：將邊<C,D>加入R中。
上一步操作之後，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步 ：將邊<D,E>加入R中。
上一步操作之後，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步 ：將邊<B,F>加入R中。
上一步操作之後，邊<C,E>的權值最小，但<C,E>會和已有的邊構成迴路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果R中。
第5步 ：將邊<E,G>加入R中。
上一步操作之後，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步 ：將邊<A,B>加入R中。
上一步操作之後，邊<F,G>的權值最小，但<F,G>會和已有的邊構成迴路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果R中。
此時，最小生成樹構造完成！它包括的邊依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。
根據前面介紹的克魯斯卡爾演算法的基本思想和做法，我們能夠了解到，克魯斯卡爾演算法重點需要解決的以下兩個問題：
問題一 對圖的所有邊按照權值大小進行排序。
問題二 將邊添加到最小生成樹中時，怎麼樣判斷是否形成了迴路。
問題一用排序演算法排序即可。
問題二，處理方式：記錄頂點在「最小生成樹」中的終點，頂點的終點是「在最小生成樹中與它連通的最大頂點"(關於這一點，後面會通過圖片給出說明)。然後每次需要將一條邊添加到最小生成樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。 以下圖來進行說明：
在將<E,F> <C,D> <D,E>加入到最小生成樹R中之後，這幾條邊的頂點就都有了終點：
關於終點，姿跡就是將所有頂點按照從小到大的順序排列好之後；某個頂點的終點就是"與它連通的最大頂點"。 因此，接下來，雖然<C,E>是權值最小的邊。但是C和E的重點都是F，即它們的終點相同，因此，將<C,E>加入最小生成樹的話，會形成迴路。這就是判斷迴路的方式。
普里姆（Prim）演算法，也是求加權連通圖的最小生成樹的演算法。
基本思想
對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。從所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有頂點）的邊中選取權值最小的邊（u，v），將頂點v加入U中，將邊（u,v）加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，此時集合T中包含了最小生成樹中的所有邊。
以上圖G4為例，來對普里姆進行演示(從第一個頂點A開始通過普里姆演算法生成最小生成樹)。
初始狀態 ：V是所有頂點的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：將頂點A加入到U中。
此時，U={A}。
第2步 ：將頂點B加入到U中。
上一步操作之後，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權值最小。將頂點B添加到U中；此時，U={A,B}。
第3步 ：將頂點F加入到U中。
上一步操作之後，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權值最小。將頂點F添加到U中；此時，U={A,B,F}。
第4步 ：將頂點E加入到U中。
上一步操作之後，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權值最小。將頂點E添加到U中；此時，U={A,B,F,E}。
第5步 ：將頂點D加入到U中。
上一步操作之後，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權值最小。將頂點D添加到U中；此時，U={A,B,F,E,D}。
第6步 ：將頂點C加入到U中。
上一步操作之後，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權值最小。將頂點C添加到U中；此時，U={A,B,F,E,D,C}。
第7步 ：將頂點G加入到U中。
上一步操作之後，U={A,B,F,E,D,C}, V-U={G}；因此，邊(F,G)的權值最小。將頂點G添加到U中；此時，U=V。
此時，最小生成樹構造完成！它包括的頂點依次是：A B F E D C G。
3. 貪心演算法中的matlab演算法怎麼做
1.數論演算法
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
求兩數的最小公倍數
function lcm(a,b:integer):integer;
begin
if a< b then swap(a,b);
lcm:=a;
while lcm mod b >0 do inc(lcm,a);
end;
素數的求法
A.小范圍內判斷一個數是否為質數：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then
begin
prime:=false; exit;
end;
prime:=true;
end;
B.判斷longint范圍內的數是否為素數（包含求50000以內的素數表）：
procere getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i< 50000 do
begin
if p then
begin
j:=i*2;
while j< 50000 do
begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p then
begin
inc(l);
pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr >=x then break
else if x mod pr=0 then exit;
prime:=true;
end;{prime}
2．
3．
4.求最小生成樹
A.Prim演算法：
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do
begin
lowcost:=cost[v0,i];
closest:=v0;
end;
for i:=1 to n-1 do
begin
{尋找離生成樹最近的未加入頂點k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]< min) and (lowcost[j]< >0) then
begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {將頂點k加入生成樹}
{生成樹中增加一條新的邊k到closest[k]}
{修正各點的lowcost和closest值}
for j:=1 to n do
if cost[k,j]< lwocost[j] then
begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}
B.Kruskal演算法：(貪心)
按權值遞增順序刪去圖中的邊，若不形成迴路則將此邊加入最小生成樹。
function find(v:integer):integer; {返回頂點v所在的集合}
var i:integer;
begin
i:=1;
while (i< =n) and (not v in vset) do inc(i);
if i< =n then find:=i
else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=;{初始化定義n個集合，第I個集合包含一個元素I}
p:=n-1; q:=1; tot:=0; {p為尚待加入的邊數，q為邊集指針}
sort;
{對所有邊按權值遞增排序，存於e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個頂點的序號，e[I].len為第I條邊的長度}
while p >0 do
begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i< >j then
begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
5.最短路徑
A.標號法求解單源點最短路徑：
var
a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn] of integer; {b指頂點i到源點的最短路徑}
mark:array[1..maxn] of boolean;
procere bhf;
var
best,best_j:integer;
begin
fillchar(mark,sizeof(mark),false);
mark[1]:=true; b[1]:=0;{1為源點}
repeat
best:=0;
for i:=1 to n do
If mark then {對每一個已計算出最短路徑的點}
for j:=1 to n do
if (not mark[j]) and (a[i,j] >0) then
if (best=0) or (b+a[i,j]< best) then
begin
best:=b+a[i,j]; best_j:=j;
end;
if best >0 then
begin
b[best_j]:=best；mark[best_j]:=true;
end;
until best=0;
end;{bhf}
B.Floyed演算法求解所有頂點對之間的最短路徑：
procere floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0;
{p[I,j]表示I到j的最短路徑上j的前驅結點}
for k:=1 to n do {枚舉中間結點}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]< a[i,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;
C. Dijkstra 演算法：
類似標號法，本質為貪心演算法。
var
a:array[1..maxn,1..maxn] of integer;
b,pre:array[1..maxn] of integer; {pre指最短路徑上I的前驅結點}
mark:array[1..maxn] of boolean;
procere dijkstra(v0:integer);
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to n do
begin
d:=a[v0,i];
if d< >0 then pre:=v0 else pre:=0;
end;
mark[v0]:=true;
repeat {每循環一次加入一個離1集合最近的結點並調整其他結點的參數}
min:=maxint; u:=0; {u記錄離1集合最近的結點}
for i:=1 to n do
if (not mark) and (d< min) then
begin
u:=i; min:=d;
end;
if u< >0 then
begin
mark:=true;
for i:=1 to n do
if (not mark) and (a[u,i]+d< d) then
begin
d:=a[u,i]+d;
pre:=u;
end;
end;
until u=0;
end;
D.計算圖的傳遞閉包
Procere Longlink;
Var
T:array[1..maxn,1..maxn] of boolean;
Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
For I:=1 to n do
For j:=1 to n do
T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
End;
4. 最小生成樹的演算法時間復雜度最小是多少
不同的演算法時間復雜度不一樣，普里姆演算法O(n^2)，克魯斯卡爾演算法O(eloge)