#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G)/* 构件图 */
{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex[MAXVEX]; /* 保存相关顶点下标 */
int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */
lowcost[0] = 0;/* 初始化第一个权值为0,即v0加入生成树 */
/* lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
adjvex[0] = 0; /* 初始化第一个顶点下标为0 */
for(i = 1; i < G.numVertexes; i++) /* 循环除下标为0外的全部顶点 */
{
lowcost[i] = G.arc[0][i]; /* 将v0顶点与之有边的权值存入数组 */
adjvex[i] = 0; /* 初始化都为v0的下标 */
}
for(i = 1; i < G.numVertexes; i++)
{
min = INFINITY; /* 初始化最小权值为∞, */
/* 通常设置为不可能的大数字如32767、65535等 */
j = 1;k = 0;
while(j < G.numVertexes) /* 循环全部顶点 */
{
if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
{
min = lowcost[j]; /* 则让当前权值成为最小值 */
k = j; /* 将当前最小值的下标存入k */
}
j++;
}
printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
for(j = 1; j < G.numVertexes; j++) /* 循环所有顶点 */
{
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
adjvex[j] = k; /* 将下标为k的顶点存入adjvex */
}
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return 0;
}
分享到:
相关推荐
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义...
山东大学数据结构课设-基于prim算法生成最小生成树的可视化展示程序(下载即用).zip山东大学数据结构课设-基于prim算法生成最小生成树的可视化展示程序(下载即用).zip山东大学数据结构课设-基于prim算法生成最小...
用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。
头歌数据结构图的最小生成树算法 第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)...
用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
运用Prim算法或Kruskal算法构造图的最小生成树。 输入格式(无向图的邻接矩阵): 8 10, 0 5, 6, 0 0, 3, 13, 0 二、实验目的 掌握图的存储方法、Prim算法或Kruskal算法。 三、实验内容及要求 1、构造图的存储结构。...
天大数据结构课 作业 编译通过 好用 源代码
数据结构教程实验--用Prim算法构造最小生成树
山东大学数据结构课设-基于prim算法生成最小生成树的可视化展示程序 - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,...
使用Prim算法编写的最小生成树(C语言),为更好地学习数据结构
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
分别利用prim算法和kruskal算法实现求图的最小生成树 C++描述
一个完整的数据结构课程设计,使用qt编写,有完整的工程文件和文档,可直接下载使用。
主要是创建最小生成树,通过对数据结构的掌握,来创建树,并读取获得最小生成树。。
数据结构课程设计,利用prim算法求解最小生成树C++
(1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
实现构造最小生成树的Prim算法
#include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 //最大顶点数为20// typedef int VRType; typedef int InfoType; typedef char VerTexType;...typedef struct ArcCell // 邻接...
prim算法最小生成树flash演示版
报告内容:要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济建设这个通信网,是一个网的最小生成树。可利用kruskal算法和prim算法来实现求最小生成树的权值,报告含两种算法具体实现源代码。