最小生成樹的幾個(gè)算法

1、 最小生成樹的幾個(gè)算法。一、Prim 算法:1、將圖中頂點(diǎn)分為兩個(gè)集合，其中集合X包含圖的一個(gè)頂點(diǎn)V0,集合Y包含除v0外的其它所有頂點(diǎn);2、將跨接這兩個(gè)集合的權(quán)值最小的邊加入圖中，并將其依附在集合Y中的頂點(diǎn)v1從Y中移入集合X中;3、反復(fù)過程2,直到集合Y為空，所得生成子圖即為最小生成樹。、Kruskal 算法:1、將圖中所有邊按權(quán)值從小到大排序;2、取權(quán)值最小的邊，加入圖中，判斷是否形成了回路，若無，則保留此邊，否則去掉該邊，重取權(quán)值較小的邊；3、反復(fù)過程2,直到全部頂點(diǎn)均連通為止。 TOC o 1-5 h z AFCDABBEFEEDBC三、破圈法:2、去掉該回路中權(quán)值最大的邊;1、在圖

2、中找到一個(gè)回路;2、去掉該回路中權(quán)值最大的邊;四、去邊法:1、將圖中所有邊按權(quán)值從大到小排序;2、去掉權(quán)值最大的邊，若圖不再連通則保留此邊，再選取下一權(quán)值較大的邊去掉;3、反復(fù)此過程，直到圖中只剩下n-1條邊為止。下面的程序是實(shí)現(xiàn)Prim、去邊法、Kruskal算法的。弄好了久好久，出現(xiàn)了很多Bug，很多 地方方法也可能不夠簡。可能還有很多Bug，但先收手了。第四次上機(jī)作業(yè)輸入無向圖的鄰接矩陣，使用前面講過的任意三種方法求該圖的最小代價(jià)生成樹，并分析各自的時(shí)間復(fù)雜度。#include#includeusing namespace std;/*基本上共用的大模塊（結(jié)構(gòu)定義，鄰接矩陣輸入）*/#d

3、efine MAX_VERTEX_NUM 20typedef struct /存放連接矩陣權(quán)值的一個(gè)結(jié)點(diǎn)int weight;Adj,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct 連接矩陣AdjMatrix arc; /存權(quán)值的域int vexnum; 節(jié)點(diǎn)個(gè)數(shù)int edge; /邊的個(gè)數(shù)MGraph;typedef struct Node /傭鏈表表示int v1; /v1, v2為邊的兩個(gè)結(jié)點(diǎn)int v2;int weight;struct Node *next; /指向下一個(gè)結(jié)點(diǎn)Node;typedef Node *NODEP

4、TR;void CreateMGraph(MGraph &M)/*創(chuàng)建一個(gè)鄰接矩陣表示有權(quán)圖*/coutM.vexnum;M.edge=0;cout請輸入該圖的鄰接矩陣:endl;for(int i=1;i=M.vexnum;i+)for(int j=1;jM.arcij.weight;if(M.arcij.weight)M.edge+;/*查找最小生成樹的Prim/*查找最小生成樹的Prim算法*/struct Closedgeint adjvex;int lowcost;struct Closedge closedgeMAX_VERTEX_NUM;/附設(shè)一個(gè)輔助數(shù)組，以記錄從 V-U 具有

5、最小代價(jià)的邊。/*尋找closedeg數(shù)組里的最小權(quán)值(除去0以外的)*/int minimun(struct Closedge closedge,MGraph m)int node=-1,min;for(int i=1;i=m.vexnum;i+)if(closedgei.lowcost!=0)min=closedgei.lowcost;node=i;/先找到第一個(gè)break;i+;for(;i=m.vexnum;i+)/再 作比較找更小的if(closedgei.lowcost!=0&closedgei.lowcostmin) min=closedgei.lowcost;node=i;re

6、turn node;/返回的是這個(gè)最小權(quán)值的在closedge的位置，即為下一個(gè)歸入的結(jié)點(diǎn)void print(struct Closedge closedge,MGraph m) /用來觀察closedge數(shù)組的變化的for(int i=1;i=m.vexnum;i+)coutv=closedgei.adjvex lowcost=closedgei.lowcostendl;/*這個(gè)程序中是每一結(jié)點(diǎn)都是對應(yīng)closedge的下標(biāo)，所以書本的下標(biāo)和長度有點(diǎn)出入*/void MiniSpanTree_PRIM(MGraph m,int u)int total=0;cout ”從第1個(gè)結(jié)點(diǎn)開始?xì)w并:

7、endl;for(int j=1;j=m.vexnum;j+)if(m.arcuj.weight)closedgej.adjvex=u;closedgej.lowcost=m.arcuj.weight;elseclosedgej.lowcost=10000;closedgeu.lowcost=0;/print(closedge,m);for(int i=1;i=m.vexnum;i+)int k=minimun(closedge,m);if(k=-1)/當(dāng)所有的結(jié)點(diǎn)都?xì)w并后，就沒有找到結(jié)點(diǎn)。程序結(jié)束。cout最小生成樹的長度為:totalendl;return;cout并入的結(jié)點(diǎn)是:k”權(quán)值為

8、:closedgek.lowcostendl; /輸出生成樹的邊total=total+closedgek.lowcost;closedgek.lowcost=0;for(j=1;j=m.vexnum;j+)if(m.arckj.weight!=0&m.arckj.weightclosedgej.lowcost)closedgej.adjvex=k;/新的結(jié)點(diǎn)并入后重新查找最小的邊 closedgej.lowcost=m.arckj.weight;/ print(closedge,m);/*查找最小生成樹的-去邊法算法*/*/NODEPTR CreateList(MGraph M)/*把鄰接矩

9、陣安從大到小的順序組成鏈表，用于去邊法使用。*/NODEPTR head=NULL,last=NULL,pre,cur;for(int i=1;i=M.vexnum;i+)for(int j=i;jv1=i;cur-v2=j;cur-weight=M.arcij.weight;if(!head)/頭結(jié)點(diǎn)為空時(shí)，直接加入。head=cur;head-next=NULL;elsepre=head;while(pre) /排序插入。if(pre-weightweight)if(!last) /插在頭結(jié)點(diǎn)的位置。cur-next=pre;head=cur;elselast-next=cur;cur-n

10、ext=pre;break;last=pre;pre=pre-next;if(!pre) /插在尾結(jié)點(diǎn)的位置。last-next=cur;cur-next=NULL;/*打印出鏈表，看看是否連接有誤。cout組成的鏈表為:endl;NODEPTR tmp=head;while(tmp)coutv1 v2(weight;tmp=tmp-next;coutendl;*/return head;/*用了廣度優(yōu)先搜索的思想，判斷是否連通，連通返回true*/bool Connectivity_BFS(MGraph m)queue q;bool visaMAX_VERTEX_NUM;/之前先初始化為 f

11、alse int count=0; memset(visa,0,sizeof(visa);q.push(1);while(!q.empty()int v=q.front();visav=true;q.pop();count+;for(int i=1;i=m.vexnum;i+)/把與v連通并且沒有被訪問過的結(jié)點(diǎn)壓進(jìn)隊(duì)列里面。if(m.arcvi.weight)if(!visai)q.push(i);visai=true;/標(biāo)志被訪問過。if(count=m.vexnum)/如果壓進(jìn)棧的結(jié)點(diǎn)個(gè)數(shù)剛好等于總結(jié)點(diǎn)的個(gè)數(shù)，則連通。return true;return false;void FindPa

12、th_DeletEdge(NODEPTR head,MGraph M)MGraph map;for(int i=1;i=M.vexnum;i+) 為了保持原來矩陣的完整性，所以把整個(gè)圖復(fù)制再刪減邊。for(int j=1；j=M.vexnum;j+)map.arcij.weight=M.arcij.weight;map.edge=M.edge;map.vexnum=M.vexnum;int count=1;cout依次刪去的邊是:v1head-v2.weight=0;map.archead-v2head-v1.weight=0;if(!Connectivity_BFS(map) /如果刪去邊之

13、后不連通的話，就要恢復(fù)原樣。map.archead-v1head-v2.weight=head-weight;map.archead-v2head-v1.weight=head-weight;elsecoutv1 v2(weight)next;/*輸出減邊之后的鄰接矩陣*/cout最小路徑的圖為:endl;int total=0;for (i=1;i=map.vexnum;i+)for(int j=1;j=map.vexnum;j+)coutmap.arcij.weight”;total=total+map.arcij.weight;coutendl;cout最小路徑的長度是:total/2n

14、ext;newhead-next=NULL;while(head)NODEPTR temp=head-next;head-next=newhead;newhead=head;head=temp;head=newhead;/*為了弄好這個(gè)找回路的函數(shù)，都快要哭了要弄到的東西一大堆。有向圖還比較好弄一 點(diǎn)。*/void Circle_DFS(MGraph m,int v,int pre,int vx,int dep,bool &flag)/用pre來記錄當(dāng)前vx的前一個(gè)，因?yàn)槭菬o向圖，所以很容易走回頭路dep記錄深度flag 是是否有解，傳引用。if(dep1&vx=v)flag=true;ret

15、urn;elsefor(int i=1;i=m.vexnum;i+)if(m.arcvxi.weight&i!=pre)/i!=pre 是以免走回頭路。Circle_DFS(m,v,vx,i,+dep,flag);return;/*遍歷head鏈表表示的帶權(quán)圖，創(chuàng)建path鏈表存放查找的過程中添加的結(jié)點(diǎn)和路徑。*/void FindPath_KRUSKAL(NODEPTR head,MGraph M)MGraph map;for(int i=1;i=M.vexnum;i+)for(int j=1;j=M.vexnum;j+)map.arcij.weight=0;map.vexnum=M.vex

16、num;map.edge=M.edge;cout依次添加的邊是:v1head-v2.weight=head-weight;map.archead-v2head-v1.weight=head-weight;count+;bool flag=false;Circle_DFS(map,head-v1,head-v1,head-v1,1,flag);if(flag)/如果添加邊之后是有回路的話，則不能添加。map.archead-v1head-v2.weight=0;map.archead-v2head-v1.weight=0;count-;elsecoutv1 v2(weight)next;/*輸出減邊之后的鄰接矩陣*/cout最小路徑的圖為:endl;int total=0;for (i=1;i=map.vexnum;i+)for(int j=1;j=map.vexnum;j+)coutmap.arcij.weight”;total=total+map.arcij.weight;coutendl;cout最小路徑的長度是:total/2next;free(head);head=tmp;head=NULL;int main() MG