最小生成樹Kruskal算法報告

沈陽航空航天大學課程設計報告課程設計名稱：數(shù)據(jù)結(jié)構(gòu)課程設計課程設計題目：最小生成樹Kruskal算法院〔系〕：計算機學院專業(yè)：計算機科學與技術(shù)目錄1課程設計介紹11.1課程設計內(nèi)容11.2課程設計要求12課程設計原理22.1課設題目粗略分析22.2原理圖介紹32.2.1功能模塊圖32.2.2流程圖分析33數(shù)據(jù)結(jié)構(gòu)分析93.1存儲結(jié)構(gòu)93.2算法描述94調(diào)試與分析114.1調(diào)試過程11程序執(zhí)行過程11參考文獻13附錄〔關(guān)鍵局部程序清單〕141課程設計介紹1.1課程設計內(nèi)容設計程序，編寫算法能建立帶權(quán)圖，并能夠用Kruskal算法求該圖的最小生成樹，系統(tǒng)主要功能如下：最小生成樹能夠選擇圖上的任意一頂點做根結(jié)點；最小生成樹輸出不必采用圖形方式，可按父結(jié)點和子女結(jié)點集的形式輸出。1.2課程設計要求頂點信息用字符串，數(shù)據(jù)可自行設定；參考相應的資料，獨立完成課程設計任務；交標準課程設計報告和軟件代碼。2課程設計原理2.1課設題目粗略分析根據(jù)課設題目要求，擬將整體程序分為五大模塊。此五個模塊相互聯(lián)系，有嵌套調(diào)用的情況，以下是五個模塊的大體分析：創(chuàng)立模塊，建立無向連通圖，創(chuàng)立圖的總信息；發(fā)現(xiàn)模塊，用Kruscal算法求最小生成樹并調(diào)用search()函數(shù);尋找模塊，找出最小邊(路徑)，使各連通分量相統(tǒng)一，輸出最小生成樹對應邊及對應結(jié)點并調(diào)用change()函數(shù)；改變模塊，改變兩個結(jié)點間的權(quán)值，使下一次尋找時不至于重復；選擇模塊，選擇最小生成樹的根結(jié)點并按父親節(jié)點和子女結(jié)點的形式輸出最小生成樹。2.2原理圖介紹2.2.1功能模塊圖最小生成樹最小生成樹Kruskal算法選擇模塊改變模塊尋找模塊發(fā)現(xiàn)模塊創(chuàng)立模塊圖功能模塊圖2.2.2流程圖分析創(chuàng)立模塊，建立無向連通圖，創(chuàng)立圖的總信息，流程圖如下：圖2.2創(chuàng)立塊流程圖發(fā)現(xiàn)模塊，用Kruscal算法求最小生成樹并調(diào)用search()函數(shù)，流程圖如下：圖2.3發(fā)現(xiàn)模塊流程圖尋找模塊，找出最小邊(路徑)，使各連通分量相統(tǒng)一，輸出最小生成樹對應邊及對應結(jié)點并調(diào)用change()函數(shù)，具體流程圖如下：圖2.4尋找模塊流程圖圖2.5尋找模塊流程圖改變模塊，改變兩個結(jié)點間的權(quán)值，使下一次尋找時不至于重復，具體流程圖如下：圖2.6改變模塊流程圖選擇模塊，選擇最小生成樹的根結(jié)點并按父親節(jié)點和子女結(jié)點的形式輸出最小生成樹法，具體流程圖如下：圖2.7選擇模塊流程圖3數(shù)據(jù)結(jié)構(gòu)分析3.1存儲結(jié)構(gòu)定義結(jié)構(gòu)體數(shù)組建立整個圖的信息，包括圖的各個結(jié)點的名稱及對應的數(shù)字編號，連接兩結(jié)點的邊的權(quán)值，建立存在互相連通的兩結(jié)點之間的聯(lián)系且采用從頭插入的鏈表連接方式，并且每個結(jié)點建立對應的鄰接表，都采用頭插入的方式，相互連接的兩結(jié)點都存有對應的邊的權(quán)值，存儲代碼如下：typedefstructlink{intconnect;//結(jié)點編號intfee;//權(quán)值structlink*next;}edgenode;typedefstructnode{ charname[10];//結(jié)點名稱 edgenode*link;}jiedian;typedefstruct{jiedianvex[MAXSIZE];intjiedian_n,jiedian_e;//結(jié)點個數(shù)，邊數(shù)(路徑數(shù))}jiedian_graph;3.2算法描述1.建立兩結(jié)點間聯(lián)系，采用從頭插入的方式，其中p,q分別為兩項鏈結(jié)點的編號，簡單算法說明如下：p->next=ga->vex[a].link;//建立兩個結(jié)點間的聯(lián)系ga->vex[a].link=p;q->next=ga->vex[b].link; ga->vex[b].link=q;2.尋找所建圖中最小權(quán)值所在邊對應的兩個結(jié)點，如果尋找過那么重新標記為一個統(tǒng)一的更大權(quán)值，以防止下次尋找時影響尋找的結(jié)果，簡單算法說明如下：for(j=1;j<ga->jiedian_n+1;j++)//找權(quán)值最少的兩個結(jié)點 { p=ga->vex[j].link;//記下當前結(jié)點，以便在此結(jié)點的聯(lián)系鏈中找到此鏈下的最小權(quán)值邊(路徑) while(p!=NULL) {if((p->fee<min)&&(p->fee!=100)) { min=p->fee; min_sign=p->connect; min_record=j; } p=p->next; }}3.修改找到最小權(quán)值的邊的權(quán)值，使其賦予更大的權(quán)值，簡單算法說明如下：while(p!=NULL) { if(p->connect==min_b) p->fee=100; q=p;p=p->next; }輸出結(jié)點所連接的各個結(jié)點的的名稱，運用啦信息表建立的頭插入方式的鄰接表，簡單算法說明如下：while(p!=NULL){ if(Mother[p->connect]!=0) { printf("%s",ga->vex[p->connect].name); Mother[p->connect]=0; } p=p->next;}4調(diào)試與分析4.1調(diào)試過程在調(diào)試程序是主要遇到一下幾類問題：鄰接表的建立采用了頭插入的方式，對應結(jié)點的插入順序不應錯誤。各個連通分量之間到達統(tǒng)一，此結(jié)果的實現(xiàn)采用了對不同連通分量所對應的結(jié)點運用不同的但有一定規(guī)律的數(shù)字進行標記，各種情況下標記數(shù)的是否相同代表著不同的情況，進行結(jié)果不同的處理。對所見圖中最小權(quán)值的尋找，運用了對尋找過得邊的權(quán)值進行重新賦予新的統(tǒng)一的更大的權(quán)值，以防止此后再次尋找對結(jié)果的干擾。輸出結(jié)點所連接的各個結(jié)點的的名稱，按照父親結(jié)點子女結(jié)點的方式輸出，運用啦信息表建立的頭插入方式的鄰接表。程序執(zhí)行過程**********歡送進入最小生成樹Kruskal算法**********進入最小生成樹算法系統(tǒng)，選擇相應的數(shù)字以進入對應模塊，執(zhí)行結(jié)果如下：進入系統(tǒng)連通圖的建立，輸入各個結(jié)點的信息和邊的信息輸入和執(zhí)行結(jié)果如下：輸入信息輸出路徑及對應結(jié)點名和權(quán)值，計算出總的權(quán)值，具體操作結(jié)果如下：輸出信息選擇根結(jié)點并根據(jù)根結(jié)點按照父親結(jié)點子女結(jié)點的形式輸出圖中的結(jié)點具體操作結(jié)果如下：輸出結(jié)果選擇退出選項，推車系統(tǒng)，操作結(jié)果如下：參考文獻[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學出版社，2007.[2]張長海，陳娟.C程序設計[M].北京：高等教育出版社，2004.[3]譚浩強.C程序設計[M].北京：清華大學出版社，2005.[4]殷人昆等.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++描述).清華大學出版，2005.，2007.附錄〔關(guān)鍵局部程序清單〕程序代碼#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE100#defineX33#defineY10typedefstructlink{intconnect;//結(jié)點編號intfee;//權(quán)值structlink*next;}edgenode;typedefstructnode{ charname[10];//結(jié)點名稱 edgenode*link;}jiedian;typedefstruct{jiedianvex[MAXSIZE];intjiedian_n,jiedian_e;//結(jié)點個數(shù)，邊數(shù)(路徑數(shù))}jiedian_graph;jiedian_graphga;inttotal_fee=0;//記錄總費用intmenu(){ inta;intb=0;printf("1:建立圖的信息\n");printf("2:找出最小生成樹及所對應邊\n");printf("3:選擇根結(jié)點編號\n");printf("4:退出\n");printf("請輸入1-4選項\n");do { scanf("%d",&a);if(a>0&&a<5)b=1;elseprintf("輸入錯誤，請重新輸入1-4選項\n"); }while(b==0);return(a);}voidcreat(jiedian_graph*ga)//創(chuàng)立圖的總信息{ inti=0,a,b;edgenode*q; edgenode*p;printf("請輸入結(jié)點個數(shù):");//結(jié)點的個數(shù)scanf("%d",&ga->jiedian_n);printf("請輸入連接結(jié)點路徑的總個數(shù):");//邊(路徑)個數(shù)scanf("%d",&ga->jiedian_e); for(i=1;i<ga->jiedian_n+1;i++)//建立信息表 { printf("請輸入第%d個結(jié)點名稱:",i); scanf("%s",ga->vex[i].name); ga->vex[i].link=NULL; }for(i=0;i<ga->jiedian_e;i++)//結(jié)點聯(lián)系表(頭插法) {printf("請輸入第%d組兩個結(jié)點的編號",i+1);//還沒有處理數(shù)據(jù)，比方輸入的是超出規(guī)定范圍的數(shù)據(jù) p=(edgenode*)malloc(sizeof(edgenode)); q=(edgenode*)malloc(sizeof(edgenode));scanf("%d%d",&a,&b); printf("請輸入兩個結(jié)點間的權(quán)值：");//兩個結(jié)點間路程的權(quán)值 scanf("%d",&p->fee); q->fee=p->fee; p->connect=b; q->connect=a; p->next=ga->vex[a].link;//建立兩個結(jié)點間的聯(lián)系ga->vex[a].link=p;q->next=ga->vex[b].link; ga->vex[b].link=q; }}jiedian_graph*change(jiedian_graph*ga,intmin_a,intmin_b)//改變兩個結(jié)點間的權(quán)值{ edgenode*p,*q,*t,*t1; p=ga->vex[min_a].link; q=ga->vex[min_a].link; t1=ga->vex[min_b].link; while(p!=NULL) { if(p->connect==min_b) { p->fee=100; } q=p;p=p->next; } t=ga->vex[min_b].link;while(t!=NULL) { if(t->connect==min_a) { t->fee=100; } t1=t; t=t->next; } returnga;}inth=1;jiedian_graph*search(jiedian_graph*ga,inti,intFather[10])//找出最小邊(路徑)，使各連通分量相統(tǒng)一并輸出最小生成樹對應邊及對應結(jié)點{edgenode*p,*q;intj,min,min_sign,min_record;intk,g,m1,m2;m1=m2=1;q=ga->vex[i].link;min=q->fee;min_sign=q->connect;min_record=i;for(j=1;j<ga->jiedian_n+1;j++)//找權(quán)值最少的兩個結(jié)點 { p=ga->vex[j].link;//記下當前結(jié)點，以便在此結(jié)點的聯(lián)系鏈中找到此鏈下的最小權(quán)值邊(路徑) while(p!=NULL) {if((p->fee<min)&&(p->fee!=100)) { min=p->fee; min_sign=p->connect; min_record=j; } p=p->next; } }//各個連通分量之間到達統(tǒng)一for(k=1;k<Y;k++){ g=k*X;if(Father[min_record]!=g) m1++; }for(k=1;k<Y;k++){ g=k*X; if(Father[min_sign]!=g) m2++; } if(m1==Y&&m2==Y) { printf("%s%s%d\n",ga->vex[min_record].name,ga->vex[min_sign].name,min);//輸出建設邊(路徑)total_fee=total_fee+min; Father[min_record]=h*X; Father[min_sign]=h*X; h++; } else { if(m1!=Y&&m2!=Y) { if(Father[min_sign]!=Father[min_record]) { printf("%s%s%d\n",ga->vex[min_record].name,ga->vex[min_sign].name,min);//輸出建設邊(路徑)total_fee=total_fee+min; for(j=1;j<ga->jiedian_n+1;j++)if(Father[j]==Father[min_sign]) Father[j]=Father[min_record];Father[min_sign]=Father[min_record]; } } else { if(m1!=Y&&m2==Y) { printf("%s%s%d\n",ga->vex[min_record].name,ga->vex[min_sign].name,min);//輸出建設邊(路徑)total_fee=total_fee+min; Father[min_sign]=Father[min_record]; } if(m1==Y&&m2!=Y) { printf("%s%s%d\n",ga->vex[min_record].name,ga->vex[min_sign].name,min);//輸出建設邊(路徑)total_fee=total_fee+min;Father[min_record]=Father[min_sign]; } } }if(min!=100)//把費用為0的濾去〔因為在改變權(quán)值時把原來的權(quán)值給置成了0，以便判斷哪些邊(路徑)是比擬過的〕ga=change(ga,min_record,min_sign);//改變兩個結(jié)點間的權(quán)值，以便區(qū)分returnga;}voidfind(jiedian_graph*ga)//Kruscal算法求最小生成樹并調(diào)用函數(shù){ inti,k; intFather[10]; for(k=0;k<=10;k++) Father[k]=k; printf("\n\n以下是路徑\n\n");printf("結(jié)點名結(jié)點名權(quán)值\n\n");for(i=1;i<=ga->jiedian_n;i++) { ga=search(ga,i,Father);//調(diào)用函數(shù)找全部路徑中最小權(quán)值的結(jié)點 }printf("\n總權(quán)值=%d\n\n",total_fee);}voidchoice(jiedian_graph*ga)//選擇最小生成樹的根結(jié)點并按父親節(jié)點和子女結(jié)點的形式輸出最小生成樹{ edgenode*p; intk,n,i;intMother[10]; for(k=0;k<=10;k++) Mother[k]=k;printf("\n輸入根結(jié)點編號:");scanf("%d",&n); printf("\n根結(jié)點為:\n%s\n",ga->vex[n].name);printf("\n以下是最小生成樹結(jié)點(根結(jié)點為父親結(jié)點)\n"); printf("\n父親結(jié)點名子女結(jié)點名:\n\n");p=ga->vex[n].link; printf("\n%s",ga->vex[n].name);Mother[n]=0; while(p!=NULL) { if(Mother[p->connect]!=0) { printf("%s",ga->vex[p->connect].name); Mother[p->connect]=0; } p=p->next; } for(i=1;i<ga->jiedian_n+1;i++) { p=ga->vex[i].link;if(Mother[i]!=0) { printf("%s",ga->vex[i].name);Mother[i]=0; } while(p!=NULL) { if(Mother[p->connect]!=0) { printf("%s",ga->vex[p->connect].name); Mother[