《数据结构开发性试验》由会员分享，可在线阅读，更多相关《数据结构开发性试验（17页珍藏版）》请在金锄头文库上搜索。
1、UMVERHTV OF SCIENCE tTEGHhFOLXKY图论相关算法的设计与实现开放性实验报告专业计算机科学与技术班级计算机科学与技术092学号姓名指导教师信息与电子工程学院2010年12月最小生成树#include #include #include #include #include typedef int Status;typedef int VRType;#define MAX_VERTEX_NUM 20#define INT_MAX 32768#define OK 1#define ERROR -1typedef structVRType adj;ArcCell,AdjMat
2、rixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structchar vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph,*ZMGraph;typedef structchar adjvex;int lowcost;closedgeMAX_VERTEX_NUM;int LocateVex(ZMGraph Gchar v)int i;for(i=0;ivexnum;i+)if(v=G-vexsi)break;return i;int CreateMGraph(ZMGraph &G)int i,j,k
3、,w;char v1,v2;G =(ZMGraph)malloc(sizeof(MGraph);printf(输入顶点总数:， scanf(%d”,&G-vexnum);printf(输入弧总数:，scanf(%d”,&G-arcnum);for(i=0;ivexnum;i+)printf(输入第d个顶点字符:”,i+1);getchar();scanf(%c”,&G-vexsi);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INT_MAX;for(k=0;karcnum;k+)getchar();printf(输入第d个弧的顶点跟权值
4、:”,k+1);scanf(%c%*c%c%d”,&v1,&v2,&w);i=LocateVex(Gv1);j=LocateVex(Gv2);G-arcsji.adj=G-arcsij.adj= w;return OK;int Minimum(closedge array,int n)int i=0,k,weight;while(arrayi.lowcost=0)i+;k=i;weight=arrayi.lowcost;for(i=0;in;i+)if(arrayi.lowcost!=0 & arrayi.lowcostweight)k=i;weight=arrayi.lowcost;retu
5、rn k;void MinSpanTree_PRIM(ZMGraph Gchar u)int k,i,j,min=0;closedge assitmatrix;k = LocateVex(Gu);for(j=0;jvexnum;j+)if(j!=k)assitmatrixj.adjvex=u;assitmatrixj.lowcost=G-arcskj.adj;assitmatrixk.adjvex=u;assitmatrixk.lowcost = 0;for(i=1;ivexnum;+i)k = Minimum(assitmatrix,G-vexnum);printf(%ccn”,assitm
6、atrixk.adjvex,G-vexsk);min=min+assitmatrixk.lowcost;assitmatrixk.lowcost = 0;for(j=0;jvexnum;+j)if(G-arcskj.adjvexsk;assitmatrixj.lowcost=G-arcskj.adj;printf(最小权值是:4d”,min);int main()ZMGraph G;char u;CreateMGraph(G);getchar();printf(输入起始顶点:， scanf(%c”,&u);printf(-最后的路径是:， MinSpanTree_PRIM(Gu);return
7、 0; DA专业课数捱结构商建文件夫Debug煽小生成棚球已 aaahhccceJgoj Jgoj Jgoj Jgojy-v-Ky-v-n-.Ax-LT.-T-LT.-T-LT.-T-LT.-T-LT.-T-LT.-T-LT.T.-LT.T.-LT.T.艮 艮艮艮艮艮艮艮艮艮CHz!. nTK nTK nTK nTK nTK nTK nTK nTK nTK JJ1I 适座aa-a付点点点点点点点点点败亥L占罟罟罟罟罟g的的的的的的的的：乳E-6 MXXXXX子顶顶顶顶顶顶顶顶顶切1 rzTrTT . . . . ,BI I - -M-123456123456789 lHX-HTK顶普第第第第第
8、第第第第第第第第第第起的T拓扑排序#include#include#include#define MAX_VEXTEX_NUM 20#define STACK_INIT_SIZE 100#define OK 1#define ERROR 0#define OVERFLOW 0 typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;char *info;ArcNode;typedef struct VNodechar data;ArcNode *firstarc;VNode,AdjListMAX_VEXTEX_NUM;typedef s
9、tructAdjList vertices;int vexnum, arcnum;ALGraph;typedef struct /* 构建栈 */char *base;char *top;int stacksize;SqStack;int LocateVex(ALGraph G,char v)int i;for(i=0;iG.vexnum;i+)if(v=G.verticesi.data) return i;return -1;int InitStack(SqStack &S)/ 初始化栈S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if
10、(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack S) / 判栈是否为空 if(S.base=S.top)return 1;return 0; int Push(SqStack &S,int e) / 兀素 e 入栈 *S.top+=e;return OK;/栈顶元素出栈，由变量e返回其值int Pop(SqStack &S,int &e) if(S.base=S.top) return ERROR;e=*-S.top;return OK;int F
11、indInDegree(ALGraph G,int *indegree) / 求图 G 中各顶点的入度 int i;ArcNode *p;for(i=0;iG.vexnum;i+) / 初始化数组 indegree【】indegreei=0;for(i=0;iadjvex+;p=p-nextarc;return OK;int CreateDG(ALGraph &G) int v,e,i,j,t;ArcNode *p,*q; char tail,head;printf(输入顶点的数量:， scanf(%d”,&v);if(v0) return ERROR;G.vexnum=v;printf(输入
12、弧的数目:， scanf(%d”,&e);if(e0) return ERROR;G.arcnum=e;printf(构造有向图G:n);for(t=0;tG.vexnum;t+)fflush(stdin);printf(输入顶点d的信息:,t+1);scanf(%c,&Gverticest.data);G.verticest.firstarc=NULL;for(t=0;t弧头:,t+1);scanf(%c%*c%c”,&tail,&head);i=LocateVex(Gtail);j=LocateVex(Ghead);if(i=-1|j=-1|i=j) return ERROR;p=(ArcNode *)malloc(sizeof(ArcNode);if(!G.verticesi.firstarc)G.verticesi.firstarc=p;elsefor(q=G.verticesi.firstarc;q-nextarc;q=q-nextarc); q-nextarc=p;p-adjvex=j;p-nextarc=NULL;p-info=NULL;return OK;int TopologicalSort(ALGraph G)int i,k,count;int indegreeMAX_VEXTEX_NUM;A
