離散數(shù)學(xué)最小生成樹(shù)實(shí)驗(yàn)報(bào)告

1、1、 實(shí)驗(yàn)?zāi)康模赫莆請(qǐng)D的存儲(chǔ)表示和以及圖的最小生成樹(shù)算法。二、實(shí)驗(yàn)內(nèi)容：1. 實(shí)現(xiàn)圖的存儲(chǔ)，并且讀入圖的內(nèi)容。2. 利用克魯斯卡爾算法求網(wǎng)絡(luò)的最小生成樹(shù)。3. 實(shí)現(xiàn)構(gòu)造生成樹(shù)過(guò)程中的連通分量抽象數(shù)據(jù)類型。4. 以文本形式輸出對(duì)應(yīng)圖的最小生成樹(shù)各條邊及權(quán)值。三、實(shí)驗(yàn)要求：1 在上機(jī)前寫出全部源程序；2 能在機(jī)器上正確運(yùn)行程序；3 用戶界面友好。需求分析：1、利用克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)；2、以用戶指定的結(jié)點(diǎn)為起點(diǎn),分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列；3、輸入為存在邊的頂點(diǎn)對(duì)，以及它們之間的權(quán)值；輸出為所得到的鄰接矩陣以及按權(quán)排序后的邊和最后得到的最小生成樹(shù)；克魯斯卡爾算法：假設(shè) WN=(V,

2、E) 是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)，按照構(gòu)造最小生成樹(shù)的過(guò)程為：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)，而邊集為空的子圖，之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù)，則將其加入子圖，反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹(shù)上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至只有一棵樹(shù)，也即子圖中含有 n-1條邊為止。 測(cè)試數(shù)據(jù)： 自行指定圖進(jìn)行運(yùn)算四、詳細(xì)設(shè)計(jì) 源程序#include<stdio.h>#include<stdlib.h>#define M 20#define MAX 20typedef struct int begin;

3、int end; int weight;edge;typedef struct int adj; int weight;AdjMatrixMAXMAX;typedef struct AdjMatrix arc; int vexnum, arcnum;MGraph;void CreatGraph(MGraph *); void sort(edge* ,MGraph *);void MiniSpanTree(MGraph *);int Find(int *, int );void Swapn(edge *, int, int);void CreatGraph(MGraph *G) int i, j

4、,n, m; printf("請(qǐng)輸入邊數(shù)和頂點(diǎn)數(shù):"); scanf("%d %d",&G->arcnum,&G->vexnum); for (i = 1; i <= G->vexnum; i+) for ( j = 1; j <= G->vexnum; j+) G->arcij.adj = G->arcji.adj = 0; for ( i = 1; i <= G->arcnum; i+) printf("n請(qǐng)輸入有邊的2個(gè)頂點(diǎn)"); scanf("

5、;%d %d",&n,&m); while(n < 0 | n > G->vexnum | m < 0 | n > G->vexnum) printf("輸入的數(shù)字不符合要求 請(qǐng)重新輸入:"); scanf("%d%d",&n,&m); G->arcnm.adj = G->arcmn.adj = 1; getchar(); printf("n請(qǐng)輸入%d與%d之間的權(quán)值:", n, m); scanf("%d",&G-&

6、gt;arcnm.weight); printf("鄰接矩陣為:n"); for ( i = 1; i <= G->vexnum; i+) for ( j = 1; j <= G->vexnum; j+) printf("%d ",G->arcij.adj); printf("n"); void sort(edge edges,MGraph *G) int i, j; for ( i = 1; i < G->arcnum; i+) for ( j = i + 1; j <= G->

7、arcnum; j+) if (edgesi.weight > edgesj.weight) Swapn(edges, i, j); printf("權(quán)排序之后的為:n"); for (i = 1; i < G->arcnum; i+) printf("<< %d, %d >> %dn", edgesi.begin, edgesi.end, edgesi.weight); void Swapn(edge *edges,int i, int j) int temp; temp = edgesi.begin; edg

8、esi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; void MiniSpanTree(MGraph *G) int i, j, n, m; int k = 1; int parentM; edge edgesM; for ( i = 1; i < G->vexnum;

9、 i+) for (j = i + 1; j <= G->vexnum; j+) if (G->arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = G->arcij.weight; k+; sort(edges, G); for (i = 1; i <= G->arcnum; i+) parenti = 0; printf("最小生成樹(shù)為:n"); for (i = 1; i <= G->arcnum; i+) n = Find(parent, ed

10、gesi.begin); m = Find(parent, edgesi.end); if (n != m) parentn = m; printf("<< %d, %d >> %dn", edgesi.begin, edgesi.end, edgesi.weight); int Find(int *parent, int f) while ( parentf > 0) f = parentf; return f;int main(void) MGraph *G; G = (MGraph*)malloc(sizeof(MGraph); if (

11、G = NULL) printf("memory allcation failed,goodbye"); exit(1); CreatGraph(G); MiniSpanTree(G); system("pause"); return 0;運(yùn)行結(jié)果:五、實(shí)驗(yàn)總結(jié)（結(jié)果分析和體會(huì)）在編程時(shí)，因?yàn)榭紤]的情況比較多，所以容易造成錯(cuò)誤和遺漏，為了避免這些問(wèn)題的出現(xiàn)，可以先用筆把所有的程序在紙上，然后再根據(jù)列表編寫程序，這樣不僅簡(jiǎn)單易懂，還避免了一些不必要的錯(cuò)誤。編寫完程序后進(jìn)行調(diào)試，發(fā)現(xiàn)有很多錯(cuò)誤，其中也不乏一些基本的小錯(cuò)誤，所以程序?qū)懲旰筮M(jìn)行靜態(tài)檢查是必不可少的，其次是邏輯上的錯(cuò)誤，對(duì)于這些錯(cuò)誤，只能再認(rèn)真檢查整個(gè)程序，這就要求我們?cè)诰幊虝r(shí)考慮要周到，或者可以請(qǐng)其他同學(xué)幫忙檢查。通過(guò)這次對(duì)算術(shù)表達(dá)式求值的設(shè)計(jì)，讓我自己對(duì)克魯斯卡爾算法的運(yùn)用更深刻，能