數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---prim算法

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：21 大小：197.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩20頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)報(bào)告　　題目：prim算法 　　五．算法設(shè)計(jì)　　程序流程圖　　算法用到的抽象數(shù)據(jù)類型定

2、義：　　1．ADT Graph{　　數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。　　數(shù)據(jù)關(guān)系R：R={VR}　　VR={<v,w>|v,w屬于V且P(v,w)表示從v到w的弧，謂詞p(v,w)定義了弧<v,w>的意義或信息}</

3、p>　　基本操作：　　LocateVex(G,u)；初始條件：圖G存在，u和G頂點(diǎn)有相同特征。操作結(jié)果：若G中存在頂點(diǎn)u,則返回頂點(diǎn)在圖中位置；否則返回其他信息。　　DestroyGrapch(&G)；初始條件：圖G存在。操作結(jié)果：銷毀圖G。<

4、p>　　GetVex(G,v)；初始條件：圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果：返回v的值。　　PutVex(&G，v,value)；初始條件：圖G存在，V是G中某個頂點(diǎn)。操作結(jié)果：對v賦值value。　　FirstAdjVex(G,v)；初始條件：圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果：返回v的第一個鄰接頂點(diǎn)。若頂點(diǎn)在G中沒有鄰

5、接頂點(diǎn)，則返回“空”。　　NextAdjVex(G,v,w);初始條件：圖G存在，v是G中某個頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的下一個鄰接頂點(diǎn)。若w是v的最后一個鄰接頂點(diǎn)，則返回“空”。　　IsertVex(&G,v)；初始條件：圖G存在v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中增添新頂點(diǎn)v。<p&g

6、t;　　DeleteVex(&G,v);初始條件：圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的弧。　　InsertArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個頂點(diǎn)。操作結(jié)果：在G中增添弧<v,w>,若G是無向的，則還增添對稱弧<w,v>。　　DeleteArc(&G

7、,v,w);初始條件：圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果：在G中刪除弧<v,w>,若G是無向的，則還刪除對稱弧<w,v>。　　DFSTraverse（G，Visit（））；初始條件：圖G存在，在Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖進(jìn)行深度優(yōu)先遍歷。在遍歷過程中對每個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失敗，則操作失敗。

8、　　BFSTraverse（G，Visit（））；初始條件：圖G存在，在Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對圖進(jìn)行深度優(yōu)先遍歷。在遍歷過程中對每個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失敗，則操作失敗。　　}ADT Graph　　算法中函數(shù)編號及功能要求：　　int

9、LocateVex(MGraph G,VertexType u)：初始條件:圖G存在,u和G中頂點(diǎn)有相同特征，操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1。　　Status CreateFAG(MGraph *G)：采用數(shù)組(鄰接矩陣)表示法,由文件構(gòu)造沒有相關(guān)信息的無向圖G。　　Status CreateDG(MGraph *G)：

10、采用數(shù)組(鄰接矩陣)表示法,構(gòu)造有向圖G。　　Status CreateDN(MGraph *G)：采用數(shù)組(鄰接矩陣)表示法,構(gòu)造有向網(wǎng)G。　　Status CreateAG(MGraph *G)：采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向圖G。　　Status CreateAN(MGraph *G)：采用數(shù)組(鄰接

11、矩陣)表示法,構(gòu)造無向網(wǎng)G。　　Status CreateGraph(MGraph *G)：采用數(shù)組(鄰接矩陣)表示法,構(gòu)造圖G。　　void DestroyGraph(MGraph *G)：初始條件: 圖G存在。操作結(jié)果: 銷毀圖G　　Status PutVex(MGraph *G,VertexType v,V

12、ertexType value)：初始條件: 圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果: 對v賦新值value。　　int FirstAdjVex(MGraph G,VertexType v)：初始條件: 圖G存在,v是G中某個頂點(diǎn)，操作結(jié)果: 返回v的第一個鄰接頂點(diǎn)的序號。若頂點(diǎn)在G中沒有鄰接頂點(diǎn),則返回-1。　　int NextAdjVex(MGraph

13、 G,VertexType v,VertexType w)：初始條件: 圖G存在,v是G中某個頂點(diǎn),w是v的鄰接頂點(diǎn)，操作結(jié)果: 返回v的(相對于w的)下一個鄰接頂點(diǎn)的序號，若w是v的最后一個鄰接頂點(diǎn),則返回-1。　　void InsertVex(MGraph *G,VertexType v)：初始條件: 圖G存在,v和圖G中頂點(diǎn)有相同特征，操作結(jié)果: 在圖G中增添新頂點(diǎn)v(不增添與頂點(diǎn)相關(guān)的弧

14、,留待InsertArc()去做)。　　Status DeleteVex(MGraph *G,VertexType v)：初始條件: 圖G存在,v是G中某個頂點(diǎn)。操作結(jié)果: 刪除G中頂點(diǎn)v及其相關(guān)的弧。　　Status InsertArc(MGraph *G,VertexType v,VertexType w)：初始條件: 圖G存在,v和W是G中兩個頂點(diǎn)

15、，操作結(jié)果: 在G中增添弧<v,w>,若G是無向的,則還增添對稱弧<w,v>。　　Status DeleteArc(MGraph *G,VertexType v,VertexType w)：初始條件: 圖G存在,v和w是G中兩個頂點(diǎn)，操作結(jié)果: 在G中刪除弧<v,w>,若G是無向的,則還刪除對稱弧<w,v>。

16、;　　void DFS(MGraph G,int v)：從第v個頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。　　void DFSTraverse(MGraph G,Status(*Visit)(VertexType))：初始條件: 圖G存在,Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果: 從第1個頂點(diǎn)起,深度優(yōu)先遍歷圖G,并對每個頂點(diǎn)調(diào)用函數(shù)Visit，一次且僅一次。一旦Visit()失敗,則操作失敗。</p

17、>　　Status InitQueue(LinkQueue *Q)：構(gòu)造一個空隊(duì)列Q，　　Status DestroyQueue(LinkQueue *Q)：銷毀隊(duì)列Q(無論空否均可)。　　Status ClearQueue(LinkQueue *Q)：將Q清為空隊(duì)列。　　Status

18、 QueueEmpty(LinkQueue Q)：若Q為空隊(duì)列,則返回TRUE,否則返回FALSE。　　int QueueLength(LinkQueue Q)：求隊(duì)列的長度。　　Status GetHead_Q(LinkQueue Q,QElemType ：若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR。&l

19、t;p>　　Status EnQueue(LinkQueue *Q,QElemType e)：插入元素e為Q的新的隊(duì)尾元素。　　Status DeQueue(LinkQueue *Q,QElemType *e)：若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR。　　Status QueueTraverse(LinkQueu

20、e Q,void(*vi)(QElemType))：從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素調(diào)用函數(shù)vi()。一旦vi失敗,則操作失敗。　　void BFSTraverse(MGraph G,Status(*Visit)(VertexType))：初始條件: 圖G存在,Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果: 從第1個頂點(diǎn)起,按廣度優(yōu)先非遞歸遍歷圖G,并對每個頂點(diǎn)調(diào)用函數(shù)，Visit一次且僅一次。一旦V

21、isit()失敗,則操作失敗，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。　　void Display(MGraph G)：輸出鄰接矩陣G。　　int minimum(minside SZ,MGraph G)：求closedge.lowcost的最小正值。　　void MiniSpanTree_PRIM(MGra

22、ph G,VertexType u)：用普里姆算法從第u個頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊。　　函數(shù)之間的調(diào)用關(guān)系（子程序編號見上）：　　主函數(shù)可調(diào)用子程序6，30　　子程序2可調(diào)用子程序1　　子程序3可調(diào)用子程序1

23、　　子程序4可調(diào)用子程序1　　子程序5可調(diào)用子程序1　　子程序6可調(diào)用子程序1　　子程序7可調(diào)用子程序3,4,5,6　　子程序9可調(diào)用子程序1　　子程序10可調(diào)用子程序1　　子程序11可調(diào)

24、用子程序1　　子程序13可調(diào)用子程序1　　子程序14可調(diào)用子程序1　　子程序15可調(diào)用子程序1　　子程序27可調(diào)用子程序24,25　　六．C語言實(shí)現(xiàn)的程序清單　　/* 實(shí)現(xiàn)算法7.9的程序

25、 */　　/////////////////////////////　　#include<string.h>　　#include<ctype.h>　　#include<malloc.h> /* malloc()等 */

26、;　　#include<limits.h> /* INT_MAX等 */　　#include<stdio.h> /* EOF(=^Z或F6),NULL */　　#include<stdlib.h> /* atoi() */　　#include<io.

27、h> /* eof() */　　#include<math.h> /* floor(),ceil(),abs() */　　#include<process.h> /* exit() */　　/* 函數(shù)結(jié)果狀態(tài)代碼 */　　#define TR

28、UE 1　　#define FALSE 0　　#define OK 1　　#define ERROR 0　　#define INFEASIBLE -1　　/* #define OVERFLOW -2 因?yàn)樵趍ath.h中已定義OV

29、ERFLOW的值為3,故去掉此行 */　　typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */　　typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */　　typedef int VRType;</

30、p>　　typedef char InfoType;　　#define MAX_NAME 3 /* 頂點(diǎn)字符串的最大長度+1 */　　#define MAX_INFO 20 /* 相關(guān)信息字符串的最大長度+1 */　　typedef char VertexType[MAX_NAME];

31、　　////////////////////////////////////　　/* 圖的數(shù)組(鄰接矩陣)存儲表示 */　　#define INFINITY INT_MAX /* 用整型最大值代替∞ */　　#define MAX_VERTEX_NUM 20 /* 最大頂

32、點(diǎn)個數(shù) */　　typedef enum{DG,DN,AG,AN}GraphKind; /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */　　typedef struct　　{　　VRType adj; /* 頂點(diǎn)關(guān)系類型。對無權(quán)圖，用1

33、(是)或0(否)表示相鄰否； */　　/* 對帶權(quán)圖，c則為權(quán)值類型 */　　InfoType *info; /* 該弧相關(guān)信息的指針(可無) */　　}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];　　typedef

34、 struct　　{　　VertexType vexs[MAX_VERTEX_NUM]; /* 頂點(diǎn)向量 */　　AdjMatrix arcs; /* 鄰接矩陣 */　　int vexnum,arcnum; /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

35、 */　　GraphKind kind; /* 圖的種類標(biāo)志 */　　}MGraph;　　/////////////////////////　　/* bo7-1.c 圖的數(shù)組(鄰接矩陣)存儲(存儲結(jié)構(gòu)由c7-1.h定義)的基本操作(2

36、0個) */　　int LocateVex(MGraph G,VertexType u)　　{ /* 初始條件:圖G存在,u和G中頂點(diǎn)有相同特征 */　　/* 操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1 */　　int i;<

37、/b>　　for(i=0;i<G.vexnum;++i)　　if(strcmp(u,G.vexs[i])==0)　　return i;　　return -1;

38、}　　Status CreateFAG(MGraph *G)　　{ /* 采用數(shù)組(鄰接矩陣)表示法,由文件構(gòu)造沒有相關(guān)信息的無向圖G */　　int i,j,k;　　char filename[13];　　V

39、ertexType va,vb;　　FILE *graphlist;　　printf("請輸入數(shù)據(jù)文件名(f7-1.dat)：");　　scanf("%s",filename);　　graphlist=fopen(filename,

40、"r");　　fscanf(graphlist,"%d",&(*G).vexnum);　　fscanf(graphlist,"%d",&(*G).arcnum);　　for(i=0;i<(*G).vexnum;++i) /* 構(gòu)造頂

41、點(diǎn)向量 */　　fscanf(graphlist,"%s",(*G).vexs[i]);　　for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */　　for(j=0;j<(*G).vexnum;++j)<b&

42、gt;　　{　　(*G).arcs[i][j].adj=0; /* 圖 */　　(*G).arcs[i][j].info=NULL; /* 沒有相關(guān)信息 */　　}　　for(k=0;k<(*G).arcnu

43、m;++k)　　{　　fscanf(graphlist,"%s%s",va,vb);　　i=LocateVex(*G,va);　　j=LocateVex(*G,vb);

44、(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 無向圖 */　　}　　fclose(graphlist);　　(*G).kind=AG;　　return OK;<

45、;p>　　}　　Status CreateDG(MGraph *G)　　{ /* 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造有向圖G */　　int i,j,k,l,IncInfo;　　char s[MAX_INFO],*info;<

46、;/p>　　VertexType va,vb;　　printf("請輸入有向圖G的頂點(diǎn)數(shù),弧數(shù),弧是否含其它信息(是:1,否:0): ");　　scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);</p&

47、gt;　　printf("請輸入%d個頂點(diǎn)的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);　　for(i=0;i<(*G).vexnum;++i) /* 構(gòu)造頂點(diǎn)向量 */　　scanf("%s",(*G).vexs[i]);<

48、;p>　　for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */　　for(j=0;j<(*G).vexnum;++j)　　{　　(*G).arcs[i][j].adj=0; /* 圖 */

49、　　(*G).arcs[i][j].info=NULL;　　}　　printf("請輸入%d條弧的弧尾弧頭(以空格作為間隔): \n",(*G).arcnum);　　for(k=0;k<(*G).arcnum;++k)<

50、;p>　　{　　scanf("%s%s%*c",va,vb); /* %*c吃掉回車符 */　　i=LocateVex(*G,va);　　j=LocateVex(*G,vb);　　(*G).arcs[i][

51、j].adj=1; /* 有向圖 */　　if(IncInfo)　　{　　printf("請輸入該弧的相關(guān)信息(<%d個字符): ",MAX_INFO);　　gets(s);</b&g

52、t;　　l=strlen(s);　　if(l)　　{　　info=(char*)malloc((l+1)*sizeof(char));　　strcpy(i

53、nfo,s);　　(*G).arcs[i][j].info=info; /* 有向 */　　}　　}　　}　　(*G

54、).kind=DG;　　return OK;　　}　　Status CreateDN(MGraph *G)　　{ /* 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造有向網(wǎng)G */　　int i,j,k,w

55、,IncInfo;　　char s[MAX_INFO],*info;　　VertexType va,vb;　　printf("請輸入有向網(wǎng)G的頂點(diǎn)數(shù),弧數(shù),弧是否含其它信息(是:1,否:0): ");　　scanf("%d,%d,%d&quo

56、t;,&(*G).vexnum,&(*G).arcnum,&IncInfo);　　printf("請輸入%d個頂點(diǎn)的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);　　for(i=0;i<(*G).vexnum;++i) /* 構(gòu)造頂點(diǎn)向量 */<

57、;p>　　scanf("%s",(*G).vexs[i]);　　for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */　　for(j=0;j<(*G).vexnum;++j)　　{<

58、p>　　(*G).arcs[i][j].adj=INFINITY; /* 網(wǎng) */　　(*G).arcs[i][j].info=NULL;　　}　　printf("請輸入%d條弧的弧尾弧頭權(quán)值(以空格作為間隔): \n",(*G).arcnum)

59、;　　for(k=0;k<(*G).arcnum;++k)　　{　　scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回車符 */　　i=LocateVex(*G,va);&

60、lt;/p>　　j=LocateVex(*G,vb);　　(*G).arcs[i][j].adj=w; /* 有向網(wǎng) */　　if(IncInfo)　　{　　printf("請輸入該弧的相關(guān)信息(

61、<%d個字符): ",MAX_INFO);　　gets(s);　　w=strlen(s);　　if(w)　　{<

62、p>　　info=(char*)malloc((w+1)*sizeof(char));　　strcpy(info,s);　　(*G).arcs[i][j].info=info; /* 有向 */　　}　　}&l

63、t;/b>　　}　　(*G).kind=DN;　　return OK;　　}　　Status CreateAG(MGraph *G)</p&g

64、t;　　{ /* 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向圖G */　　int i,j,k,l,IncInfo;　　char s[MAX_INFO],*info;　　VertexType va,vb;　　printf("請輸入無向圖G的頂點(diǎn)數(shù),

65、邊數(shù),邊是否含其它信息(是:1,否:0): ");　　scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);　　printf("請輸入%d個頂點(diǎn)的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);<

66、;/p>　　for(i=0;i<(*G).vexnum;++i) /* 構(gòu)造頂點(diǎn)向量 */　　scanf("%s",(*G).vexs[i]);　　for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */　　for(j=0;j&l

67、t;(*G).vexnum;++j)　　{　　(*G).arcs[i][j].adj=0; /* 圖 */　　(*G).arcs[i][j].info=NULL;　　}&l

68、t;p>　　printf("請輸入%d條邊的頂點(diǎn)1 頂點(diǎn)2(以空格作為間隔): \n",(*G).arcnum);　　for(k=0;k<(*G).arcnum;++k)　　{　　scanf("%s%s%*c",va,vb)

69、; /* %*c吃掉回車符 */　　i=LocateVex(*G,va);　　j=LocateVex(*G,vb);　　(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 無向圖 */　　if(IncInfo)

70、　　{　　printf("請輸入該邊的相關(guān)信息(<%d個字符): ",MAX_INFO);　　gets(s);　　l=strlen(s);<b&

71、gt;　　if(l)　　{　　info=(char*)malloc((l+1)*sizeof(char));　　strcpy(info,s);　　(*G).arcs[i][j].info=(*G).arcs[j][

72、i].info=info; /* 無向 */　　}　　}　　}　　(*G).kind=AG;　　return OK;

73、　　}　　Status CreateAN(MGraph *G)　　{ /* 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng)G。算法7.2 */　　int i,j,k,w,IncInfo;　　char

74、s[MAX_INFO],*info;　　VertexType va,vb;　　printf("請輸入無向網(wǎng)G的頂點(diǎn)數(shù),邊數(shù),邊是否含其它信息(是:1,否:0): ");　　scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,

75、&IncInfo);　　printf("請輸入%d個頂點(diǎn)的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);　　for(i=0;i<(*G).vexnum;++i) /* 構(gòu)造頂點(diǎn)向量 */　　scanf("%s",(*G).vex

76、s[i]);　　for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */　　for(j=0;j<(*G).vexnum;++j)　　{　　(*G).arcs[i][j].adj=INFINITY;

77、/* 網(wǎng) */　　(*G).arcs[i][j].info=NULL;　　}　　printf("請輸入%d條邊的頂點(diǎn)1 頂點(diǎn)2 權(quán)值(以空格作為間隔): \n",(*G).arcnum);　　for(k=0;k&l

78、t;(*G).arcnum;++k)　　{　　scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回車符 */　　i=LocateVex(*G,va);　　j=LocateVex(*G

79、,vb);　　(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 無向 */　　if(IncInfo)　　{　　printf("請輸入該邊的相關(guān)信息(<%d個字符): "

80、;,MAX_INFO);　　gets(s);　　w=strlen(s);　　if(w)　　{　　info=(char

81、*)malloc((w+1)*sizeof(char));　　strcpy(info,s);　　(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 無向 */　　}

82、　}　　}　　(*G).kind=AN;　　return OK;　　}　　Status CreateGraph(MGraph *G)&

83、lt;/p>　　{ /* 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造圖G。算法7.1 */　　printf("請輸入圖G的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3): ");　　scanf("%d",&(*G).kind);　　swit

84、ch((*G).kind)　　{　　case DG: return CreateDG(G); /* 構(gòu)造有向圖 */　　case DN: return CreateDN(G); /* 構(gòu)造有向網(wǎng) */　　case AG: return

85、 CreateAG(G); /* 構(gòu)造無向圖 */　　case AN: return CreateAN(G); /* 構(gòu)造無向網(wǎng) */　　default: return ERROR;　　}　　}&

86、lt;/p>　　void DestroyGraph(MGraph *G)　　{ /* 初始條件: 圖G存在。操作結(jié)果: 銷毀圖G */　　int i,j;　　if((*G).kind<2) /* 有向 */<p&

87、gt;　　for(i=0;i<(*G).vexnum;i++) /* 釋放弧的相關(guān)信息(如果有的話) */　　{　　for(j=0;j<(*G).vexnum;j++)　　if((*G).arcs[i][j].adj==1&&(*G).kind==

88、0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1) /* 有向圖的弧||有向網(wǎng)的弧 */　　if((*G).arcs[i][j].info) /* 有相關(guān)信息 */　　{　　free((*G).arcs[i][j].

89、info);　　(*G).arcs[i][j].info=NULL;　　}　　}　　else /* 無向 */　　for(i=0;i<(*G).ve

90、xnum;i++) /* 釋放邊的相關(guān)信息(如果有的話) */　　for(j=i+1;j<(*G).vexnum;j++)　　if((*G).arcs[i][j].adj==1&&(*G).kind==2||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3) /* 無向圖的邊||

91、無向網(wǎng)的邊 */　　if((*G).arcs[i][j].info) /* 有相關(guān)信息 */　　{　　free((*G).arcs[i][j].info);　　(*G).arcs[i][j].info=(*G).arcs[j][i].

92、info=NULL;　　}　　(*G).vexnum=0;　　(*G).arcnum=0;　　}　　VertexType* GetVex(MGraph G

93、,int v)　　{ /* 初始條件: 圖G存在，v是G中某個頂點(diǎn)的序號。操作結(jié)果: 返回v的值 */　　if(v>=G.vexnum||v<0)　　exit(ERROR);　　return &G.vexs[v];<p&g

94、t;　　}　　Status PutVex(MGraph *G,VertexType v,VertexType value)　　{ /* 初始條件: 圖G存在，v是G中某個頂點(diǎn)。操作結(jié)果: 對v賦新值value */　　int k;<

95、/p>　　k=LocateVex(*G,v); /* k為頂點(diǎn)v在圖G中的序號 */　　if(k<0)　　return ERROR;　　strcpy((*G).vexs[k],value);　　ret

96、urn OK;　　}　　int FirstAdjVex(MGraph G,VertexType v)　　{ /* 初始條件: 圖G存在,v是G中某個頂點(diǎn) */　　/* 操作結(jié)果: 返回v的第一個鄰接頂點(diǎn)的序號。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)

97、,則返回-1 */　　int i,j=0,k;　　k=LocateVex(G,v); /* k為頂點(diǎn)v在圖G中的序號 */　　if(G.kind==DN||G.kind==AN) /* 網(wǎng) */　　j=INFINITY;　　for

98、(i=0;i<G.vexnum;i++)　　if(G.arcs[k][i].adj!=j)　　return i;　　return -1;　　}　　i

99、nt NextAdjVex(MGraph G,VertexType v,VertexType w)　　{ /* 初始條件: 圖G存在,v是G中某個頂點(diǎn),w是v的鄰接頂點(diǎn) */　　/* 操作結(jié)果: 返回v的(相對于w的)下一個鄰接頂點(diǎn)的序號, */　　/* 若w是v的最后一個鄰接頂點(diǎn),則返回-1

100、 */　　int i,j=0,k1,k2;　　k1=LocateVex(G,v); /* k1為頂點(diǎn)v在圖G中的序號 */　　k2=LocateVex(G,w); /* k2為頂點(diǎn)w在圖G中的序號 */　　if(G.kind==DN||G.kind==AN) /* 網(wǎng) *

101、/　　j=INFINITY;　　for(i=k2+1;i<G.vexnum;i++)　　if(G.arcs[k1][i].adj!=j)　　return i;　　return -1;&l

102、t;/p>　　}　　void InsertVex(MGraph *G,VertexType v)　　{ /* 初始條件: 圖G存在,v和圖G中頂點(diǎn)有相同特征 */　　/* 操作結(jié)果: 在圖G中增添新頂點(diǎn)v(不增添與頂點(diǎn)相關(guān)的弧,留待InsertAr

103、c()去做) */　　int i;　　strcpy((*G).vexs[(*G).vexnum],v); /* 構(gòu)造新頂點(diǎn)向量 */　　for(i=0;i<=(*G).vexnum;i++)　　{</b&

104、gt;　　if((*G).kind%2) /* 網(wǎng) */　　{　　(*G).arcs[(*G).vexnum][i].adj=INFINITY; /* 初始化該行鄰接矩陣的值(無邊或弧) */　　(*G).arcs[i][(*G).v

105、exnum].adj=INFINITY; /* 初始化該列鄰接矩陣的值(無邊或弧) */　　}　　else /* 圖 */　　{　　(*G).arcs[(*G).vexnum][i].adj=0;

106、 /* 初始化該行鄰接矩陣的值(無邊或弧) */　　(*G).arcs[i][(*G).vexnum].adj=0; /* 初始化該列鄰接矩陣的值(無邊或弧) */　　}　　(*G).arcs[(*G).vexnum][i].info=NULL; /* 初始化相關(guān)信息指針 *

107、/　　(*G).arcs[i][(*G).vexnum].info=NULL;　　}　　(*G).vexnum+=1; /* 圖G的頂點(diǎn)數(shù)加1 */　　}

108、　　Status DeleteVex(MGraph *G,VertexType v)　　{ /* 初始條件: 圖G存在,v是G中某個頂點(diǎn)。操作結(jié)果: 刪除G中頂點(diǎn)v及其相關(guān)的弧 */　　int i,j,k;　　VRType m=0;　　k=LocateVex(*G,v);

109、 /* k為待刪除頂點(diǎn)v的序號 */　　if(k<0) /* v不是圖G的頂點(diǎn) */　　return ERROR;　　if((*G).kind==DN||(*G).kind==AN) /* 網(wǎng) */　　m=INFINITY;

110、　　for(j=0;j<(*G).vexnum;j++)　　if((*G).arcs[j][k].adj!=m) /* 有入弧或邊 */　　{　　if((*G).arcs[j][k].info) /* 有相關(guān)信息 */　　fre

111、e((*G).arcs[j][k].info); /* 釋放相關(guān)信息 */　　(*G).arcnum--; /* 修改弧數(shù) */　　}　　if((*G).kind==DG||(*G).kind==DN) /* 有向 */　　for(j

112、=0;j<(*G).vexnum;j++)　　if((*G).arcs[k][j].adj!=m) /* 有出弧 */　　{　　if((*G).arcs[k][j].info) /* 有相關(guān)信息 */　　free((*G).ar

113、cs[k][j].info); /* 釋放相關(guān)信息 */　　(*G).arcnum--; /* 修改弧數(shù) */　　}　　for(j=k+1;j<(*G).vexnum;j++) /* 序號k后面的頂點(diǎn)向量依次前移 */　　str

114、cpy((*G).vexs[j-1],(*G).vexs[j]);　　for(i=0;i<(*G).vexnum;i++)　　for(j=k+1;j<(*G).vexnum;j++)　　(*G).arcs[i][j-1]=(*G).arcs[i][j]; /* 移動待刪除頂點(diǎn)之后的矩陣元素 */<

115、;/p>　　for(i=0;i<(*G).vexnum;i++)　　for(j=k+1;j<(*G).vexnum;j++)　　(*G).arcs[j-1][i]=(*G).arcs[j][i]; /* 移動待刪除頂點(diǎn)之下的矩陣元素 */　　(*G).vexnum--; /

116、* 更新圖的頂點(diǎn)數(shù) */　　return OK;　　}　　Status InsertArc(MGraph *G,VertexType v,VertexType w)　　{ /* 初始條件: 圖G存在,v和W是G中兩個頂點(diǎn) */<

117、/p>　　/* 操作結(jié)果: 在G中增添弧<v,w>,若G是無向的,則還增添對稱弧<w,v> */　　int i,l,v1,w1;　　char *info,s[MAX_INFO];　　v1=LocateVex(*G,v); /* 尾 */&

118、lt;p>　　w1=LocateVex(*G,w); /* 頭 */　　if(v1<0||w1<0)　　return ERROR;　　(*G).arcnum++; /* 弧或邊數(shù)加1 */　　if((*G).kind%2) /* 網(wǎng) */</p&g

119、t;　　{　　printf("請輸入此弧或邊的權(quán)值: ");　　scanf("%d",&(*G).arcs[v1][w1].adj);　　}&l

120、t;p>　　else /* 圖 */　　(*G).arcs[v1][w1].adj=1;　　printf("是否有該弧或邊的相關(guān)信息(0:無 1:有): ");　　scanf("%d%*c",&i);

121、　　if(i)　　{　　printf("請輸入該弧或邊的相關(guān)信息(<%d個字符)：",MAX_INFO);　　gets(s);　　l=strlen(s

122、);　　if(l)　　{　　info=(char*)malloc((l+1)*sizeof(char));　　strcpy(info,s);　　(*G).

123、arcs[v1][w1].info=info;　　}　　}　　if((*G).kind>1) /* 無向 */　　{<p&

124、gt;　　(*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;　　(*G).arcs[w1][v1].info=(*G).arcs[v1][w1].info; /* 指向同一個相關(guān)信息 */　　}　　return OK;

125、　　}　　Status DeleteArc(MGraph *G,VertexType v,VertexType w)　　{ /* 初始條件: 圖G存在,v和w是G中兩個頂點(diǎn) */　　/* 操作結(jié)果: 在G中刪除弧<v,w>,若G是無向的,則還

126、刪除對稱弧<w,v> */　　int v1,w1;　　v1=LocateVex(*G,v); /* 尾 */　　w1=LocateVex(*G,w); /* 頭 */　　if(v1<0||w1<0) /* v1、w1的值不合法 */</p&g

127、t;　　return ERROR;　　if((*G).kind%2==0) /* 圖 */　　(*G).arcs[v1][w1].adj=0;　　else /* 網(wǎng) */　　(*G).arcs[v1][w1].adj=INFINITY;</p&

128、gt;　　if((*G).arcs[v1][w1].info) /* 有其它信息 */　　{　　free((*G).arcs[v1][w1].info);　　(*G).arcs[v1][w1].info=NULL;

129、;　　}　　if((*G).kind>=2) /* 無向,刪除對稱弧<w,v> */　　{　　(*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;<p&g

130、t;　　(*G).arcs[w1][v1].info=NULL;　　}　　(*G).arcnum--;　　return OK;　　}　　Boolean v

131、isited[MAX_VERTEX_NUM]; /* 訪問標(biāo)志數(shù)組(全局量) */　　Status(*VisitFunc)(VertexType); /* 函數(shù)變量 */　　void DFS(MGraph G,int v)　　{ /* 從第v個頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。算法7.5 */

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---prim算法

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---prim算法

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載