標籤: 暫無標籤

一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結點,並且有保持圖連通的最少的邊。

1概述

在一給定的無向圖G = (V, E) 中,(u, v) 代表連接頂點 u 與頂點 v 的邊(即),而 w(u, v) 代表此邊的權重,若存在 T 為 E 的子集(即)且為無循環圖,使得
的 w(T) 最小,則此 T 為 G 的最小生成樹
\omega\left(t\right)=\sum_{\left(u,v\right)\in t}\omega\left(u,v\right)
最小生成樹其實是最小權重生成樹的簡稱。
許多應用問題都是一個求無向連通圖的最小生成樹問題。例如:要在n個城市之間鋪設光纜,主要目標是要使這 n 個城市的任意兩個之間都可以通信,但鋪設光纜的費用很高,且各個城市之間鋪設光纜的費用不同;另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。
最小生成樹

2應用

生成樹和最小生成樹有許多重要的應用。
最小生成樹
【例】網路G表示n個城市之間的通信線路網線路(其中頂點表示城市,邊表示兩個城市之間的通信線路,邊上的權值表示線路的長度或造價)。可通過求該網路的最小生成樹達到求解通信線路或總代價最小的最佳方案。

3性質

證明
為方便說明,先作以下約定:
①將集合U中的頂點看作是紅色頂點,②而V-U中的頂點看作是藍色頂點,③連接紅點和藍點的邊看作是紫色邊,④權最小的紫邊稱為輕邊(即權重最"輕"的邊)。於是,MST性質中所述的邊(u,v)就可簡稱為輕邊。
用反證法證明MST性質:
假設G中任何一棵MST都不含輕邊(u,v)。則若T為G的任意一棵MST,那麼它不含此輕邊。
根據樹的定義,則T中必有一條從紅點u到藍點v的路徑P,且P上必有一條紫邊(u',v')連接紅點集和藍點集,否則u和v不連通。當把輕邊(u,v)加入樹T時,該輕邊和P必構成了一個迴路。刪去紫邊(u',v')后迴路亦消除,由此可得另一生成樹T'。
T'和T的差別僅在於T'用輕邊(u,v)取代了T中權重可能更大的紫邊(u',v')。因為w(u,v)≤w(u',v'),所以
w(T')=w(T)+w(u,v)-w(u',v')≤w(T)
即T'是一棵比T更優的MST,所以T不是G的MST,這與假設矛盾。
所以,MST性質成立。

4演算法描述

求MST的一般演算法可描述為:針對圖G,從空樹T開始,往集合T中逐條選擇並加入n-1條安全邊(u,v),最終生成一棵含n-1條邊的MST。
當一條邊(u,v)加入T時,必須保證T∪{(u,v)}仍是MST的子集,我們將這樣的邊稱為T的安全邊。
A.Prim演算法
procedure 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[i]:=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]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;
C語言代碼
#include<stdio.h>#include<stdlib.h>#include<iostream.h>#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define MAX 1000typedef struct Arcell{        double adj;    }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{        char vexs[MAX_VERTEX_NUM]; //節點數組        AdjMatrix arcs; //鄰接矩陣        int vexnum,arcnum; //圖的當前節點數和弧數    }MGraph;typedef struct Pnode //用於普利姆演算法{        char adjvex; //節點        double lowcost; //權值    }Pnode,Closedge[MAX_VERTEX_NUM]; //記錄頂點集U到V-U的代價最小的邊的輔助數組定義typedef struct Knode //用於克魯斯卡爾演算法中存儲一條邊及其對應的2個節點{        char ch1; //節點1        char ch2; //節點2        double value;//權值    }Knode,Dgevalue[MAX_VERTEX_NUM];//---------------------------------------------------------------------------------int CreateUDG(MGraph & G,Dgevalue & dgevalue);int LocateVex(MGraph G,char ch);int Minimum(MGraph G,Closedge closedge);void MiniSpanTree_PRIM(MGraph G,char u);void Sortdge(Dgevalue & dgevalue,MGraph G);//-------------------------------------------------------------------------------int CreateUDG(MGraph & G,Dgevalue & dgevalue) //構造無向加權圖的鄰接矩陣{        int i,j,k;        cout<<"請輸入圖中節點個數和邊/弧的條數:";        cin>>G.vexnum>>G.arcnum;        cout<<"請輸入節點:";        for(i=0;i<G.vexnum;++i)                cin>>G.vexs[i];        for(i=0;i<G.vexnum;++i)//初始化數組            {                for(j=0;j<G.vexnum;++j)                    {                        G.arcs[i][j].adj=MAX;                    }            }        cout<<"請輸入一條邊依附的定點及邊的權值:"<<endl;        for(k=0;k<G.arcnum;++k)            {                cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;                i = LocateVex(G,dgevalue[k].ch1);                j = LocateVex(G,dgevalue[k].ch2);                G.arcs[i][j].adj = dgevalue[k].value;                G.arcs[j][i].adj = G.arcs[i][j].adj;            }        return OK;    }int LocateVex(MGraph G,char ch) //確定節點ch在圖G.vexs中的位置{        int a ;        for(int i=0; i<G.vexnum; i++)            {                if(G.vexs[i] == ch)                        a=i;            }        return a;    }void MiniSpanTree_PRIM(MGraph G,char u)//普利姆演算法求最小生成樹{        int i,j,k;        Closedge closedge;        k = LocateVex(G,u);        for(j=0; j<G.vexnum; j++)            {                if(j != k)                    {                        closedge[j].adjvex = u;                        closedge[j].lowcost = G.arcs[k][j].adj;                    }            }        closedge[k].lowcost = 0;        for(i=1; i<G.vexnum; i++)            {                k = Minimum(G,closedge);                cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;                closedge[k].lowcost = 0;                for(j=0; j<G.vexnum; ++j)                    {                        if(G.arcs[k][j].adj < closedge[j].lowcost)                            {                                closedge[j].adjvex = G.vexs[k];                                closedge[j].lowcost= G.arcs[k][j].adj;                            }                    }            }    }int Minimum(MGraph G,Closedge closedge) //求closedge中權值最小的邊,並返回其頂點在vexs中的位置{        int i,j;        double k = 1000;        for(i=0; i<G.vexnum; i++)            {                if(closedge[i].lowcost != 0 && closedge[i].lowcost < k)                    {                        k = closedge[i].lowcost;                        j = i;                    }            }        return j;    }void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克魯斯卡爾演算法求最小生成樹{        int p1,p2,i,j;        int bj[MAX_VERTEX_NUM]; //標記數組        for(i=0; i<G.vexnum; i++) //標記數組初始化                bj[i]=i;        Sortdge(dgevalue,G);//將所有權值按從小到大排序        for(i=0; i<G.arcnum; i++)            {                p1 = bj[LocateVex(G,dgevalue[i].ch1)];                p2 = bj[LocateVex(G,dgevalue[i].ch2)];                if(p1 != p2)                    {                        cout<<"("<<dgevalue[i].ch1<<","<<dgevalue[i].ch2<<","<<dgevalue[i].value<<")"<<endl;                        for(j=0; j<G.vexnum; j++)                            {                                if(bj[j] == p2)                                        bj[j] = p1;                            }                    }            }    }void Sortdge(Dgevalue & dgevalue,MGraph G)//對dgevalue中各元素按權值按從小到大排序{        int i,j;        double temp;        char ch1,ch2;        for(i=0; i<G.arcnum; i++)            {                for(j=i; j<G.arcnum; j++)                    {                        if(dgevalue[i].value > dgevalue[j].value)                            {                                temp = dgevalue[i].value;                                dgevalue[i].value = dgevalue[j].value;                                dgevalue[j].value = temp;                                ch1 = dgevalue[i].ch1;                                dgevalue[i].ch1 = dgevalue[j].ch1;                                dgevalue[j].ch1 = ch1;                                ch2 = dgevalue[i].ch2;                                dgevalue[i].ch2 = dgevalue[j].ch2;                                dgevalue[j].ch2 = ch2;                            }                    }            }    }void main(){        int i,j;        MGraph G;        char u;        Dgevalue dgevalue;        CreateUDG(G,dgevalue);        cout<<"圖的鄰接矩陣為:"<<endl;        for(i=0; i<G.vexnum; i++)            {                for(j=0; j<G.vexnum; j++)                        cout << G.arcs[i][j].adj<<" ";                cout<<endl;            }        cout<<"=============普利姆演算法===============\n";        cout<<"請輸入起始點:";        cin>>u;        cout<<"構成最小代價生成樹的邊集為:\n";        MiniSpanTree_PRIM(G,u);        cout<<"============克魯斯科爾演算法=============\n";        cout<<"構成最小代價生成樹的邊集為:\n";        MiniSpanTree_KRSL(G,dgevalue);    }

5pascal

program didi;
var
a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:array[0..10000] of longint;
n,i,j,x,y,z:longint;
tot,ans:longint;
count,xx:longint;
procedure quick(l,r:longint);
var
i,j,x,y,t:longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2].len;
repeat
while x>a[i].len do inc(i);
while x<a[j].len do dec(j);
if i<=j then
begin
y:=a[i].len;a[i].len:=a[j].len;a[j].len:=y;
y:=a[i].s;a[i].s:=a[j].s;a[j].s:=y;
y:=a[i].t;a[i].t:=a[j].t;a[j].t:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then quick(i,r);
if l<j then quick(l,j);
end;
function find(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=find(fa[x]);
find:=fa[x];
end;
procedure union(x,y:longint);{啟髮式合併}
var
t:longint;
begin
x:=find(x);
y:=find(y);
if r[x]>r[y] then
begin
t:=x;x:=y;y:=t;
end;
if r[x]=r[y] then inc(r[x]);
fa[x]:=y;
end;
begin
readln(xx,n);
for i:=1 to xx do fa[i]:=i;
for i:=1 to n do
begin
read(x,y,z);
inc(tot);
a[tot].s:=x;
a[tot].t:=y;
a[tot].len:=z;
end;
quick(1,tot);{將邊排序}
ans:=0;
count:=0;
i:=0;
while count<=x-1 do{count記錄加邊的總數}
begin
inc(i);
with a[i] do
if find(s)<find(t) then
begin
union(s,t);
ans:=ans+len;
inc(count);
end;
end;
write(ans);
end.
Prim
var
m,n:set of 1..100;
s,t,min,x,y,i,j,k,l,sum,p,ii:longint;
a:array[1..100,1..100]of longint;
begin
readln(p);
for ii:=1 to p do
begin
k:=0; sum:=0;
fillchar(a,sizeof(a),255);
readln(x);
m:=[1];
n:=[2..x];
for i:=1 to x do
begin
for j:=1 to x do
begin
read(a[i,j]);
if a[i,j]=0
then a[i,j]:=maxlongint;
end;
readln;
end;
for l:=1 to x-1 do
begin
min:=maxlongint;
for i:=1 to x do
if i in m
then begin
for j:=1 to x do
begin
if (a[i,j]<min)and(j in n)
then begin
min:=a[i,j];
s:=i;
t:=j;
end;
end;
end;
sum:=sum+min;
m:=m+[t];
n:=n-[t];
inc(k);
end;
writeln(sum);
end;
end.

相關評論

同義詞:暫無同義詞