徐州工程学院数据结构最小生成树实验文档

实验九图的最小生成树算法的实现

实验预备知识：

1．理解图最小生成树的意义和相应算法。 2．掌握带权图的存储结构。 一、实验目的

1．使学生熟悉最小生成树的算法实现。 2．掌握带权图的存储结构和处理方法。 二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C； 三、实验要求

1．能够独立完成带权图的存储和最小生成树的生成 四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。

3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树

#include #include #define INF 50

typedef struct ArcNode{

int adjvex; //该弧所指向的顶点位置 struct ArcNode *nextarc; //下一个临接点 int weight; //弧的权重 }ArcNode; //表结点

typedef struct VNode{ char data; //顶点信息 ArcNode *firstarc; //指向下一个结点 }VNode,AdjList[6];

typedef struct{ AdjList LH; //创建头结点数组 int vexnum; //图的点的个数 int arcnum; //图的边的个数 }Graph;

typedef struct{ char nextvex; int lowcost; int know;

}Auxiliary_array; //辅助数组结构体

void main (void){ void buildtu (Graph*); void printgraph(Graph*); void prim( Graph *G, char u);

char u; Graph UDG; Graph *G = &UDG; buildtu(G); printgraph(G); //打印图 printf(\请输入起始顶点：\\n\ while(getchar()!='\\n'); u = getchar();

prim(G ,u); }

void buildtu (Graph *G) { //建图 int search(Graph *G,char a); int i,n1,n2,w; char a,b; ArcNode *p, *q;

printf(\请输入顶点个数和边的条数：\\n\ scanf(\ printf(\请输入顶点信息\\n\ for (i = 0; i < G->vexnum; ++i){ while (getchar()!='\\n'); scanf(\ G->LH[i].firstarc = NULL; }

printf(\请输入有关系的结点和该边的权重:\\n\ for(i=0;iarcnum;++i){ while (getchar()!='\\n');

scanf(\ n1=search(G,a); n2=search(G,b); p=G->LH[n1].firstarc; if(p == NULL){ p=G->LH[n1].firstarc=(ArcNode *) malloc (sizeof(ArcNode)); } else{ while( p->nextarc !=NULL ){ p=p->nextarc; } p=p->nextarc=(ArcNode *) malloc (sizeof(ArcNode)); } q=G->LH[n2].firstarc; if(q == NULL){ q=G->LH[n2].firstarc=(ArcNode *) malloc (sizeof(ArcNode)); } else{

while( q->nextarc !=NULL ){ q=q->nextarc; } q=q->nextarc=(ArcNode *) malloc (sizeof(ArcNode)); } p->adjvex=n2; p->weight=w; p->nextarc=NULL; q->adjvex=n1; q->weight=w; q->nextarc=NULL; } }

int search (Graph *G,char a){ //确定顶点a在头结点数组中的位置 int i; for(i=0;ivexnum;++i){ if(G->LH[i].data==a){ return i; } } }

void printgraph(Graph *G){ //打印图 int i;

ArcNode *p; for (i=0 ; i < G->vexnum; ++i) { p=G->LH[i].firstarc; printf(\ while(p!=NULL){ printf(\ p=p->nextarc; } printf(\ } }

void prim( Graph *G, char u){//用prim算法实现最小生成树 int search (Graph *G,char a); int minimize(Graph *G, Auxiliary_array[]); void printtable(Auxiliary_array[]);

Auxiliary_array A[6]; //创建辅助数组 int i,j,seat; int location; ArcNode *p ; for (i = 0; i < G->vexnum; ++i) { A[i].nextvex = '0'; A[i].know = 0; A[i].lowcost = INF; }

location = search(G ,u);//确定u元素在头结点数组中的位置 for (p=G->LH[location].firstarc ; p != NULL; p=p->nextarc ){ i = p->adjvex; A[i].nextvex = G->LH[location].data; A[i].lowcost = p->weight; A[i].know = 0; } A[location].know = 1; A[location].lowcost = 0; A[location].nextvex = '0';

for(j=0;jvexnum-1;++j){ seat = minimize( G,A ); printf(\ A[seat].know = 1; p=G->LH[seat].firstarc; for (p; p != NULL; p=p->nextarc){ i=p->adjvex; if(A[i].know == 0 && p->weight < A[i].lowcost){ A[i].nextvex = G->LH[seat].data; A[i].lowcost = p->weight; } } }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库徐州工程学院数据结构最小生成树实验文档在线全文阅读。