/***************************************
title:普利姆算法求连通图最小生成树
author: jay chang
date: 2009.7.12
****************************************/
#include<iostream>
using namespace std;
#define MAX 9999
#define MAXSIZE 99
#define FALSE 0
#define TRUE 1
typedef char VertexData;
typedef int AdjType;
typedef struct VertexNode
{
VertexData vertexData;
}VertexNode;
typedef struct ArcNode
{
AdjType adj; //弧的权值
}ArcNode;
typedef struct AdjMatrix
{
VertexNode vertexNodes[MAXSIZE+1];
ArcNode arcNodes[MAXSIZE+1][MAXSIZE+1];
int vertexNum,arcNum;
}AdjMatrix;
typedef struct ClosedgeNode
{
VertexData vertexData;
AdjType adj;
}ClosegdeNode,Closedge[MAXSIZE];
/**********************************************************************************
Function Name:LocateGraph
Return Type: int
Function Description: 查询在图中是否存在结点信息为vertexData的结点,存在返回结
点位置,否则返回FALSE。
**********************************************************************************/
int LocateGraph(AdjMatrix* g,VertexData vertexData)
{
int iIndex;
for(iIndex=1;iIndex<=g->vertexNum;iIndex++)
{
if(vertexData==g->vertexNodes[iIndex].vertexData)
return iIndex;
}
return FALSE;
}
/**********************************************************************************
Function Name:CreateAdjMatrix
Return Type: void
Function Description: 创建连通图
**********************************************************************************/
void CreateAdjMatrix(AdjMatrix* g)
{
cout<<"******************************************************************\n";
cout<<" 普里姆算法求连通图最短路径\n";
cout<<"******************************************************************\n";
cout<<"输入连通图的顶点数,弧数:\n";
cin>>g->vertexNum>>g->arcNum;
cout<<"输入顶点信息"<<endl;
int iCount,start,end,adj;char arcStart,arcEnd;
for(int iIndex=1;iIndex<=g->vertexNum;iIndex++)
{
for(int jIndex=1;jIndex<=g->vertexNum;jIndex++)
{
g->arcNodes[iIndex][jIndex].adj=MAX;
}
}
for(iCount=1;iCount<=g->vertexNum;iCount++)
{
cout<<"结点"<<iCount<<"的信息"<<endl;
cin>>g->vertexNodes[iCount].vertexData;
}
for(iCount=1;iCount<=g->arcNum;iCount++)
{
cout<<"输入第"<<iCount<<"条弧的起始,终点,弧的权值"<<endl;
cin>>arcStart>>arcEnd>>adj;
start=LocateGraph(g,arcStart);end=LocateGraph(g,arcEnd);
g->arcNodes[start][end].adj=adj;
g->arcNodes[end][start].adj=adj;
}
}
/**********************************************************************************
Function Name:Minimun
Return Type: int
Function Description: 求U,V-U集合中的,两个顶点间权值最小的边
**********************************************************************************/
int Minimum(Closedge closedge,AdjMatrix* g)
{
int iCount,flag=FALSE,min=MAX;
for(iCount=1;iCount<=g->vertexNum;iCount++)
{
if(closedge[iCount].adj!=0&&closedge[iCount].adj<min)
{
min=closedge[iCount].adj;
}
}
for(iCount=1;iCount<=g->vertexNum;iCount++)
{
if(closedge[iCount].adj!=0&&closedge[iCount].adj==min)
{
flag=iCount;
break;
}
}
return flag;
}
/**********************************************************************************
Function Name:Print
Return Type: void
Function Description: 打印边
**********************************************************************************/
inline void Print(AdjMatrix* g,VertexData u0,VertexData v0)
{
int start,end;
start=LocateGraph(g,u0);end=LocateGraph(g,v0);
cout<<u0<<"到"<<v0<<"的权值为"<<g->arcNodes[start][end].adj<<endl;
}
/**********************************************************************************
Function Name:Prime
Return Type: void
Function Description: 普里姆算法求连通图的最小生成树
**********************************************************************************/
void Prime(AdjMatrix* g,Closedge closedge,VertexData vertexData)
{
int iIndex,first;VertexData u0,v0;
first=LocateGraph(g,vertexData); //取结点vertexData顶点的位置
closedge[first].adj=0; //将结点vertexData并入U集合
for(iIndex=1;iIndex<=g->vertexNum;iIndex++) //初始化closedge
{
if(iIndex!=first)
{
closedge[iIndex].vertexData=vertexData;
closedge[iIndex].adj=g->arcNodes[first][iIndex].adj;
}
}
for(iIndex=1;iIndex<=g->vertexNum-1;iIndex++)
{
int k0=Minimum(closedge,g),varI;
u0=closedge[k0].vertexData;
v0=g->vertexNodes[k0].vertexData;
Print(g,u0,v0);
varI=LocateGraph(g,v0);
closedge[varI].adj=0; //将结点v0并入U集合
for(int jIndex=1;jIndex<=g->vertexNum;jIndex++)
{
if(g->arcNodes[varI][jIndex].adj<closedge[jIndex].adj)
{
closedge[jIndex].adj=g->arcNodes[varI][jIndex].adj;
closedge[jIndex].vertexData=v0;
}
}
}
}
int main()
{
AdjMatrix* g=(AdjMatrix*)malloc(sizeof(AdjMatrix));
Closedge closedge;
CreateAdjMatrix(g);
Prime(g,closedge,g->vertexNodes[1].vertexData);
return 0;
}
分享到:
相关推荐
用普里姆(Prim)算法构造最小生成树 数据结构树与图的经典编程题。优秀的代码哦。
数据结构的课程设计。用普里姆算法求图的最小生成树
用普利姆算法求最小生成树 包含WORD .PPT ..和CPP文件。 都是我们小组自己做的哦
通过PRIM的基本算法思想求解出最小生成树,而最小生成树是指在连通网的所有生成树中,边上的权值之和最小的生成树,在这里我们就可以采用将顶点逐个连通步骤,把顶点加入到已连通顶点集合U中,最后使U成为最小生成树
对任意给定的网和起点,用PRIM算法的基本思想求解出所有的最小生成树。
用普利姆算法构造最小生成树,数据结构(C语言版)课程,C语言实现,cin/cout输入输出,请用Dev C++编译
本程序是C语言实现的最小生成树源代码,使用word文档格式
克鲁斯卡尔算法,普利姆算法,算法有点错误,可以初步画图
本程序用普利姆算法求图的最小生成树。 int n,k; cout请输入图的点数 n="; cin>>n; cout请输入图的边数 k="; cin>>k;
普里姆(Prim)算法构造最小生成树 编译通过版本 可以直接运行使用
用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
最小生成树 C语言 普利姆算法,,,有需要可以给我EMAIL,也用克鲁斯卡尔算法写了一下
最小生成树的构造,以及求最小生成树的 普利姆算法和克鲁斯卡尔算法,C++实现算法
Prim算法是一种求解最小生成树问题的贪心算法。其基本原理是:每次从未被选择的顶点中选择一个距离当前生成树最近的顶点加入生成树,直到所有的顶点都被选择。 以下是Prim算法的详细步骤: 初始化:选取图中的任一...
一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。 当用联通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的...
在G的所有生成树中,耗费最小的生成树称为G的最小生成树。 贪心选择策略: 每次都选择到下一顶点权最小的边。 基本步骤: 1.置顶点集合S={1}; 2.只要S是V的真子集,就作如下的贪心选择:选取满足条件i∈S,j∈V...
数据结构Prim(普利姆)算法求最小生成树c++代码描述。。。代码有注释,并有test case
本资料是数据结构课程设计中最小生成树普利姆算法的实现
实现度约束为2的最小生成树算法,基于普利姆算法
本程序使用MFC可视化界面实现的,用普里姆算法实现最小生成树,在MFC上显示出来