西安電子科技大學(xué)離散數(shù)學(xué)大作業(yè)西安電子科技大學(xué)離散數(shù)學(xué)大作業(yè)西安電子科技大學(xué)離散數(shù)學(xué)大作業(yè)西安電子科技大學(xué)離散數(shù)學(xué)大作業(yè)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:離散數(shù)學(xué)大作業(yè)班級(jí)：021231學(xué)號(hào)：02123120姓名：題目：編程實(shí)現(xiàn)賦權(quán)有向圖的最小生成樹摘要求解圖的最小生成樹有三種算法，分別為Prim算法、Kruskal算法和Boruvka算法。這三種算法都是貪心算法。所以本次實(shí)驗(yàn)分別使用Kruskal算法和Prim算法實(shí)現(xiàn)賦權(quán)有向圖的最小生成樹。Kruskal算法基本思想為：為使生成樹上總的權(quán)值之和達(dá)到最小，則應(yīng)使每一條邊上的權(quán)值盡可能地小，自然應(yīng)從權(quán)值最小的邊選起，直至選出n-1條互不構(gòu)成回路的權(quán)值最小邊為止。具體作法如下：首先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇不使森林中產(chǎn)生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網(wǎng)的最小生成樹。Prim算法基本思想是：首先選取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后繼續(xù)往生成樹中添加頂點(diǎn)w，則在頂點(diǎn)w和頂點(diǎn)v之間必須有邊，且該邊上的權(quán)值應(yīng)在所有和v相鄰接的邊中屬最小。關(guān)鍵詞：鄰接矩陣；鄰接表；Kruskal算法；Prim算法；最小生成樹一、最小生成樹的研究進(jìn)展最小生成樹可以使用Kruskal算法和Prim算法。下面具體介紹這兩種算法。Kruskal算法求加權(quán)連通圖的最小生成樹的算法。kruskal算法總共選擇n-1條邊，（共n條邊）所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。kruskal算法分e步，其中e是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。該算法的時(shí)間復(fù)雜度為O(elge);Kruskal算法的時(shí)間主要取決于邊數(shù),它較適合于稀疏圖。Kruskal算法構(gòu)造最小生成樹的過程圖解:Prim算法Prim算法可以說是所有MST算法中最簡(jiǎn)單的，比較適用于稠密圖。以圖中任意一個(gè)頂點(diǎn)S開始，選擇與之相關(guān)連的邊中權(quán)值最小的邊加入到MST中，假設(shè)這條邊的終點(diǎn)為T，則MST初始化為(S,T)，稱之為“當(dāng)前MST”。接下來在剩余的邊中選擇與當(dāng)前MST中s所有頂點(diǎn)相關(guān)連的邊中權(quán)值最小的邊，并添加到當(dāng)前MST中。這一過程一直迭代到圖中所有頂點(diǎn)都添加到MST中為止。從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)u0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v)，將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把該邊加入到生成樹的邊集TE中，把它的頂點(diǎn)加入到集合U中。如此重復(fù)執(zhí)行，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向連通圖，T(U，TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集。prim算法適合稠密圖，其時(shí)間復(fù)雜度為O(n^2)，其時(shí)間復(fù)雜度與邊得數(shù)目無關(guān)，而kruskal算法的時(shí)間復(fù)雜度為O(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。二、最小生成樹的實(shí)現(xiàn)Kruskal算法關(guān)鍵部分的實(shí)現(xiàn)Kruskal算法的計(jì)算流程大致如下：1.將無向圖的邊按距離長(zhǎng)短遞增式排序，放到集合中2.遍歷該集合，找出最短的邊，加入到結(jié)果生成樹的集合中3.如果結(jié)果生成樹出現(xiàn)回路，則放棄這條邊4.重新執(zhí)行步驟2，直至所有頂點(diǎn)被遍歷可以看出在每次遍歷過程中采用了貪心算法Kruskal算法代碼如下：dj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=;++i)acrvisited[i]=0;for(j=0;j!=;++j){m=10000;for(i=0;i!=;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}buf=find(acrvisited,x);edf=find(acrvisited,y);edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}dj=int_max;[i][j].info=NULL;}for(intk=0;k!=;++k){cout<<"輸入一條邊依附的頂點(diǎn)和權(quán):例如abc(a,b表示頂點(diǎn)，c表示權(quán))"<<endl;cin>>v1>>v2>>w;dj=w;[j][i].adj=w;}cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;return;}intvisited[max];ata=[i];[i].firstarc=NULL;}for(i=0;i!=;++i){for(j=0;j!=;++j){if[i].firstarc==NULL){if[i][j].adj!=int_max&&j!={arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while[i][j].adj!=int_max&&j!={tem=(arcnode*)malloc(sizeof(arcnode));tem->adjvex=j;[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if[i][j].adj!=int_max&&j!={arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}=;=;return1;}intfirstadjvex(algraphgra,vnodev)dj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=;++i)acrvisited[i]=0;for(j=0;j!=;++j){m=10000;for(i=0;i!=;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}buf=find(acrvisited,x);edf=find(acrvisited,y);edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}dj;cout<<"prim:"<<endl;prim(g,d);break;case1:cout<<"kruscal:"<<endl;kruscal_arc(G,gra);