数据结构开发性试验_最小生成树关键路径拓扑排序.doc
文本预览下载声明
图论相关算法的设计与实现
开放性实验报告
专 业 计算机科学与技术
班 级 计算机科学与技术092
学 号
姓 名
指导教师
信息与电子工程学院
2010年12月
最小生成树
#include math.h
#include stdio.h
#include string.h
#include stdlib.h
#include limits.h
typedef int Status;
typedef int VRType;
#define MAX_VERTEX_NUM 20
#define INT_MAX 32768
#define OK 1
#define ERROR -1
typedef struct
{
VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph,*ZMGraph;
typedef struct
{
char adjvex;
int lowcost;
}closedge[MAX_VERTEX_NUM];
int LocateVex(ZMGraph G,char v)
{
int i;
for(i=0;iG-vexnum;i++)
if(v==G-vexs[i])
break;
return i;
}
int CreateMGraph(ZMGraph G)
{
int i,j,k,w;
char v1,v2;
G =(ZMGraph)malloc(sizeof(MGraph));
printf(输入顶点总数:);
scanf(%d,G-vexnum);
printf(输入弧总数:);
scanf(%d,G-arcnum);
for(i=0;iG-vexnum;i++)
{
printf(输入第%d个顶点字符:,i+1);
getchar();
scanf(%c,G-vexs[i]);
}
for(i=0;iG-vexnum;i++)
{
for(j=0;jG-vexnum;j++)
{
G-arcs[i][j].adj=INT_MAX;
}
}
for(k=0;kG-arcnum;k++)
{
getchar();
printf(输入第%d个弧的顶点跟权值:,k+1);
scanf(%c%*c%c%d,v1,v2,w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G-arcs[j][i].adj=G-arcs[i][j].adj= w;
}
return OK;
}
int Minimum(closedge array,int n)
{
int i=0,k,weight;
while(array[i].lowcost==0)
{
i++;
}
k=i;
weight=array[i].lowcost;
for(i=0;in;i++)
{
if(array[i].lowcost!=0 array[i].lowcostweight)
{
k=i;
weight=array[i].lowcost;
}
}
return k;
}
void MinSpanTree_PRIM(ZMGraph G,char u)
{
int k,i,j,min=0;
closedge assitmatrix;
k = LocateVex(G,u);
for(j=0;jG-vexnum;j++)
{
if(j!=k)
{
assitmatrix[j].adjvex=u;
assitmatrix[j].lowcost=G-arcs[k][j].
显示全部