prim算法_范文大全网

范文一：prim算法

prim 算法构造最小生成树

构造赋权图 (, , ) G V E W =, 其中 12n {, , , }V v v v = 为顶点集合 , 其中 i v 表示第 i 个顶点, (E 为边的集合) , () ij n n W w ?=为邻接矩阵,其中

i j i j ij i j v v v v w v v ∈??=?∞??顶点与之间的距离,当(, )

E , 与之间没有边时

prim 算法如下:

(1)初始化,构造 1{}P v =,即选中顶点 1v 作为构造最小生成树的起点,构

造空集 Q 。

(2)找出权重最小的边 pv ,其中 , V P p P v ∈∈-; 把选中的顶点 v 加入集合 P , {}P P v =+; 把选中的边 pv 加入集合 Q , {}Q Q pv =+ ;

(3)当 P V =时终止,否则转入(2)

已知 9个村庄之间的两两距离见表 5, 要架设通讯线路把 9个村庄连接起来, 求所需要通讯线的最小长度。

129{, , , }V v v v = 为顶点集合 , 其中 i v 表示第 i 个村庄, E 为边的集合, 99() ij W w ?=为邻接矩阵,其中

i j i j ij i j v v v v w v v ∈??=?∞??村庄与之间的距离,当(, )

E , 与之间没有通讯路线时

利用 prim 算法求解出最小生成树 :

(1)初始化,构造 1{}P v =,即选中村庄 1v 作为构造最小生成树的起点,构造空集 Q 。

(2)找出距离最小的通讯线路 pv ,其中 , V P p P v ∈∈-; 把选中的顶点 v 加入集合 P , {}P P v =+; 把选中的边 pv 加入集合 Q , {}Q Q pv =+ ;

(3)当 P V =时终止,否则转入(2)

通过 Matlab 程序画出 9个村庄之间的连通图如图 1, Node i 表示第 i 个村

通过 Matlab 计算,各村庄之间的最短通讯线的最小长度 L = 45.6401km。

一、连通图程序

clc,clear

a=zeros(9); %邻接矩阵初始化

a=xlsread('data.xls','B2:J10');

a(isnan(a))=0;

a=a'; b=sparse(a) %变成下三角矩阵,并转化为稀疏矩阵

h=biograph(b,[],'ShowWeights','on','ShowArrows','off') %生成图形对象

%Matlab2014B 和 2015A,'ShowWeights' 有 bug, 属性值为 'off' 时没有问题, 属性值为 'on' 时出错, 但图形显示是正确的

set(h,'LayoutType','equilibrium'); %设置属性 :图形的布局是平衡的 view(h) %显示图形

二、最小生成树程序

clc, clear

a=zeros(9);

a=xlsread('data.xls' , 'B2:J10');

a(isnan(a))=0;

a=a';

a=sparse(a);

b=graphminspantree(a,'Method' , 'Prim' )

L=sum(sum(b))

cu='′?×ˉ'

cz=repmat(cu,9,1)

v=cellstr([cz,int2str([1:9]')]) %未改完

view(biograph(b,v,'ShowArrows' , 'off' , 'ShowWeights' , 'on' ))

范文二：prim算法的实现

prim算法的实现

/************************************************************

作者: 黄位富 04281190 记科0407.

工具: VC++ 6.0.

题目:

创建时间: 2006年11月26日.

修改时间: 2006年11月30日.

/**********************************************************/

#include

#define MAXVEVERTEXNUM 6//图的点数

#define MAXIMUMCOST 100 //两点间不相邻距离为100 int truev[MAXVEVERTEXNUM];

//truev[v]=1代表v是V集合的点 truev[v]=0是S-V集合的点

initadjmatrix(int Matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM],int

truev[MAXVEVERTEXNUM])

//初始化邻接矩阵不相邻边的权为MAXIMUMCOST

{

int matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM]=

{

{MAXIMUMCOST,6,1,5,MAXIMUMCOST,MAXIMUMCOST},//v1到其他点的距离

{6,MAXIMUMCOST,5,MAXIMUMCOST,3,MAXIMUMCOST},//v2到其他点的距离

{1,5,MAXIMUMCOST,5,6,4}, //v3到其他点的距离

{5,MAXIMUMCOST,5,MAXIMUMCOST,MAXIMUMCOST,2},//v4到其他点的距离

{MAXIMUMCOST,3,6,MAXIMUMCOST,MAXIMUMCOST,6},//v5到其他点的距离

{MAXIMUMCOST,MAXIMUMCOST,4,2,6,MAXIMUMCOST} //v6到其他点的距离

};

//图的初始化

int i=0,j;

while(i

{

truev[i]=0;//初始时V集合为空

i++;

}

for( i=0;i

for ( j=0;j

{

Matrix[i][j]=matrix[i][j];

printf("%4d",matrix[i][j]);

if(j!=0&&j%(MAXVEVERTEXNUM-1)==0)

printf("\n");

}

//打印邻接矩阵

return 1;

}

int minimum(int truve[MAXVEVERTEXNUM],int temp1[MAXVEVERTEXNUM],int temp2[MAXVEVERTEXNUM],int N)

{

//找出权最小的边并把对应的结点放到V集合中

int Temp1,Temp2;

int i,min;

min=temp1[0];

Temp2=temp2[0];//默认为第一个

for (i=0;i<=n;i++)>

{

if(temp1[i]

{

Temp1=min;min=temp1[i];temp1[i]=Temp1;

Temp2=temp2[i];//最小权的下标

}

printf("%d!!\n",Temp2+1);

truev[Temp2]=1;//放入V集合中

return 1;

}

prim(int count,int matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM],int truve[MAXVEVERTEXNUM])

{

int temp1[(MAXVEVERTEXNUM/2)*((MAXVEVERTEXNUM+1)/2)]; int temp2[(MAXVEVERTEXNUM/2)*((MAXVEVERTEXNUM+1)/2)]; int i,j;

int N=0;

if(count==MAXVEVERTEXNUM-1) return 1;

for(i=0;i

{

for(j=0;j

{

if(truev[i]==1&&truev[j]==0&&matrix[i][j]

temp1[N]=matrix[i][j];

//V中的点和S-V中的点如果相邻依此保存其权

temp2[N]=j; //在S-V中找出与V中相连的点并保存

N++;

}

minimum(truve,temp1,temp2,N-1);

//求得V与S-V之间的最短路径及其所对应的结点 count++;

prim(count,matrix,truve);

}

void main()

{

int Map[MAXVEVERTEXNUM][MAXVEVERTEXNUM];//图 int v0,count=0; //当count=MAXVEVERTEXNUM时结束递归

initadjmatrix(Map,truev);//图的初始化

printf("图的结点是从1开始.\n");

printf("请输入开始结点:");

scanf("%d",&v0); //取v0

if(v0<1||v0>MAXVEVERTEXNUM) printf("v0<1或者 v0="">MAXVEVERTEXNUM!!ERROR\n");//数据不对 else

{

v0--; //图的结点从1开始

truev[v0]=1; //v0进V集合

printf("过程:\n");

printf("%d!!\n",v0+1);//v0

prim(count,Map,truev);

}//主要算法

}

范文三：（转载）prim算法

转的一个很不错的Prim算法。。

#include

#define MAX 100

#define MAXCOST 0x7fffffff

int graph[MAX][MAX];

int Prim(int graph[][MAX], int n)

{

/* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */

int lowcost[MAX];

/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */

int mst[MAX];

int i, j, min, minid, sum = 0;

/* 默认选择1号节点加入生成树，从2号节点开始初始化 */

for (i = 2; i <= n;="" i++)="">

{

/* 最短距离初始化为其他节点到1号节点的距离 */

lowcost[i] = graph[1][i];

/* 标记所有节点的起点皆为默认的1号节点 */

mst[i] = 1;

}

/* 标记1号节点加入生成树 */

mst[1] = 0;

/* n个节点至少需要n-1条边构成最小生成树 */

for (i = 2; i <= n;="" i++)="">

{

min = MAXCOST;

minid = 0;

/* 找满足条件的最小权值边的节点minid */

for (j = 2; j <= n;="" j++)="">

{

/* 边权值较小且不在生成树中 */

if (lowcost[j] < min="" &&="" lowcost[j]="" !="">

{

min = lowcost[j];

minid = j;

}

/* 输出生成树边的信息:起点，终点，权值 */

printf("%c %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);

/* 累加权值 */

sum += min;

/* 标记节点minid加入生成树 */

lowcost[minid] = 0;

/* 更新当前节点minid到其他节点的权值 */

for (j = 2; j <= n;="" j++)="">

{

/* 发现更小的权值 */

if (graph[minid][j] < lowcost[j])="">

{

/* 更新权值信息 */

lowcost[j] = graph[minid][j];

/* 更新最小权值边的起点 */

mst[j] = minid;

}

/* 返回最小权值和 */

return sum;

}

int main()

{

int i, j, k, m, n;

int x, y, cost;

char chx, chy;

printf("enter the numbers of vertex and edge：");

/* 读取节点和边的数目 */

scanf("%d%d", &m, &n);

printf("enter the network:\n");

getchar();

/* 初始化图，所有节点间距离为无穷大 */

for (i = 1; i <= m;="" i++)="">

{

for (j = 1; j <= m;="" j++)="">

{

graph[i][j] = MAXCOST;

}

/* 读取边信息 */

for (k = 0; k < n;="" k++)="">

{

scanf("%c %c %d", &chx, &chy, &cost);

getchar();

i = chx - 'A' + 1;

j = chy - 'A' + 1;

graph[i][j] = cost;

graph[j][i] = cost;

}

printf("the MST is:\n");

/* 求解最小生成树 */

cost = Prim(graph, m);

/* 输出最小权值和 */

printf("Total:%d\n", cost);

return 0;

}

范文四：最小生成树prim算法

#include"malloc.h"

#include"stdlib.h"

#include"stdio.h"

#include

#define MAX_VERTEX_NUM 20 // 最大顶点个数

#define MAX_NAME 3 // 顶点字符串的最大长度+1

#define MAX_INFO 20 // 相关信息字符串的最大长度+1

#define INFINITY INT_MAX // 用整型最大值代替∞

typedef int VRType;

typedef char InfoType;

typedef char VertexType[MAX_NAME];

// 邻接矩阵的数据结构

typedef struct

{

VRType adj; // 顶点关系类型。对无权图，用1(是) 或0(否) 表示相邻否； // 对带权图，则为权值类型

InfoType *info; // 该弧相关信息的指针(可无)

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 图的数据结构

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量

AdjMatrix arcs; // 邻接矩阵

int vexnum, // 图的当前顶点数

arcnum; // 图的当前弧数

} MGraph;

// 记录从顶点集U 到V-U 的代价最小的边的辅助数组定义

typedef struct

{

VertexType adjvex;

VRType lowcost;

}minside[MAX_VERTEX_NUM];

// 若G 中存在顶点u, 则返回该顶点在图中位置; 否则返回-1。

int LocateVex(MGraph G,VertexType u)

{

for(i = 0; i < g.vexnum;="">

if( strcmp(u, G.vexs[i]) == 0)

return i;

return -1;

}

// 算法7.2 P162

// 采用数组(邻接矩阵) 表示法, 构造无向网G 。

int CreateAN(MGraph *G)

{

int i,j,k,w,IncInfo;

char s[MAX_INFO],*info;

VertexType va,vb;

printf("请输入无向网G 的顶点数, 边数, 边是否含其它信息(是:1,否:0):(空格区分) "); scanf("%d%d%d%*c",&(*G).vexnum,&(*G).arcnum,&IncInfo);

printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME); for(i=0;i<(*g).vexnum;++i)>

scanf("%s",(*G).vexs[i]);

for(i=0;i<(*g).vexnum;++i)>

for(j=0;j<>

{

(*G).arcs[i][j].adj=INFINITY; // 网初始化为无穷大

(*G).arcs[i][j].info=NULL;

}

printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum); for(k=0;k<>

{

scanf("%s%s%d%*c",va,vb,&w); // %*c吃掉回车符

i=LocateVex(*G,va);

j=LocateVex(*G,vb);

(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; // 无向

if(IncInfo)

{

printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);

gets(s);

w=strlen(s);

if(w)

{

info=(char*)malloc((w+1)*sizeof(char));

strcpy(info,s);

(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; // 无向

}

return 1;

}

// 求closedge.lowcost 的最小正值

int minimum(minside SZ,MGraph G)

{

int i=0,j,k,min;

while(!SZ[i].lowcost)

i++;

min=SZ[i].lowcost; // 第一个不为0的值

k=i;

for(j=i+1;j<>

if(SZ[j].lowcost>0)

if(min>SZ[j].lowcost)

{

min=SZ[j].lowcost;

k=j;

}

return k;

}

// 算法7.9 P175

// 用普里姆算法从第u 个顶点出发构造网G 的最小生成树T, 输出T 的各条边 void MiniSpanTree_PRIM(MGraph G,VertexType u)

{

int i,j,k;

minside closedge;

k=LocateVex(G,u);

for(j=0;j

{

if(j!=k)

{

strcpy(closedge[j].adjvex,u);

closedge[j].lowcost=G.arcs[k][j].adj;

}

closedge[k].lowcost=0; // 初始,U={u}

printf("最小代价生成树的各条边为:\n");

for(i=1;i<>

{ // 选择其余G .vexnum-1个顶点

k=minimum(closedge,G); // 求出T 的下一个结点：第K 顶点

printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); // 输出生成树的边 closedge[k].lowcost=0; // 第K 顶点并入U 集

for(j=0;j<>

if(G.arcs[k][j].adj<>

{

// 新顶点并入U 集后重新选择最小边

strcpy(closedge[j].adjvex,G.vexs[k]);

closedge[j].lowcost=G.arcs[k][j].adj;

}

int main()

{

MGraph G;

CreateAN(&G);

MiniSpanTree_PRIM(G,G .vexs[0]);

system("pause");

return 0;

}

输出效果：

请输入无向网G 的顶点数, 边数, 边是否含其它信息(是:1,否:0):(空格区分) 4 4 0 请输入4个顶点的值(<>

请输入4条边的顶点1 顶点2 权值(以空格作为间隔):

a b 1

a c 2

b d 3

a d 1

最小代价生成树的各条边为:

(a-b)

(a-d)

(a-c)

请按任意键继续. . .

范文五：最小生成树prim算法

《数据结构》

课程设计报告

(最小生成树问题)

1 课程设计的目的和意义 . ................................................................................................................

2 需求分析 .........................................................................................................................................

3 系统(项目)设计 . ........................................................................................................................

4 系统实现 .........................................................................................................................................

5 系统调试 ......................................................................................................................................... 附录源程序 . ......................................................................................................................................

1 课程设计的目的和意义

据《数据结构》课堂讲授及书本内容,学生做相应的自主练习,消化课堂所

讲解的内容;通过调试典型例题或习题积累调试 C 及 C++程序的经验;通过完成课程设计中的编程题, 逐渐培养学生的编程能力、用计算机解决实际问题的能力。 “ 数据结构 ” 作为计算机专业基础课,该课程的目标就是使学生学会如何从问题出发, 分析数据, 构造求解问题的数据结构和算法, 培养学生有一定进行较复杂程序设计的能力。

本次课程设计的内容是用最小生成树的构造来表示城市间的最小代价即最小距离, 最小生成树可以用连接矩阵和连接表表示, 而它们的区别就是连接矩阵一般用来表示密集型的网络, 连接表一般用来表示稀疏型的网络, 连接矩阵是用数组来存储, 连接了是用链表来存储的, 比较复杂密集型的网络就网连接矩阵较适用了, 设计中运用了 Prim 算法, “构造可以使 n 个城市连接的最小生成树” 问题就是用连接矩阵和 Prim 算法处理的一个实际应用。通过这个题目的设计实例, 了解了最小生成树的实际运用意义,也了解连接矩阵和连接表的相同与不同之处,进一步加深了对最小生成树结构和 Prim 算法的理解。

通过这次课程设计,一方面使学生加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解,另一方面,使学生在程序设计方法(如抽象数据类型、结构化分析、模块化设计和结构化设计) 、 C 和 C++语言编程环境以及程序的调试和测试方面受到比较系统的严格的训练。

2 需求分析

1. 题目:最小生成树的 Prime 算法实现(难度 **) 要求:

1) 先任意创建一个图;

2) 用 Prime 算法,求出该图的最小生成树。

3 系统(项目)设计

(包括总体设计和详细设计 )

一 . 设计思想及方案:

n 个顶点的连通图应该至少有 n-1条边,而生成树正好有 n-1条边,所以生成树是对应的连通图的极小连通子图。带权的无向图,经过遍历得到的生成树也是带权的,最小生成树即权值最小的生成树。所以要求图的最小生成树,即只要求权值最小的极小连通子图。这实际上是求图的一个生成树。同时还要考虑造价最低这个条件。一棵树的权定义为它所含各边的权之和。一个连通网络的最小生成树是该图所有生成树中权最小的生成树普里姆算法(Prim )算法:设 N=(V,{E})是连通图, TE 是 N 上最小生成树中边的集合, U 为 V 中具有最小生成树的顶点集合,初始时, TN 为空, U={uo}( uo∈ V), 重复下叙操作:在所有 u ∈ U 、 v ∈ V-U 的边(u,v )∈ E 中找一条代价最小的边(u0 , v0 )并入集合 TE ,同时 v0 并入集合 TE, 同时 , 直到 U=V为止,此时 TE 必有 n-1条边,且 T=(V,{TE})为 N 的最小生成树。

二. 模块的设计及介绍

(1). 主程序模块

void main(){

{

接受命令;

处理命令;

Cout<><”” 命令="" ”="”" 是否继续?="" y/n””="">

}

(2). 创建链接矩阵模块

int creatMGraph_L(参数 ){

for {

接受命令;

处理命令;

}

cout

}

4 系统实现

各模块关键代码及算法的解释:

(1) . 主函数模块代码

{

algraph gra;

MGraph_L G;

int i,d,g[20][20];

char a='a';

d=creatMGraph_L(G);

vnode v;

cout<>

cout

char y='y';

while(y='y')

{

cout

cin>>s;

switch(s)

{

case 0:

cout

ljjzprint(G);

break;

case 1:

for(i=0;i!=G.vexnum;++i)

for(int j=0;j!=G.vexnum;++j)

g[i+1][j+1]=G.arcs[i][j].adj;

cout

prim(g,d);

break;

}

cout<>

cin>>y;

if(y=='n')

break;

}

程序解释:该主函数用一个循环语句,来执行其它的函数的功能。从键盘输入顶点数和边数上限,再调用定义连接矩阵的函数,后输出创建连接矩阵的信息,再调用 creatMGraph ()函数,接着进入菜单,然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价,最后选择输入确定字母 y 或 N 确定是否继续。

(2). 邻接矩阵定义模块代码

typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct

{

char vexs[20];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

int localvex(MGraph_L G,char v) {

int i=0;

while(G.vexs[i]!=v)

{

++i;

}

return i;

}

程序解释:用 typedef struct定义连接矩阵, 通过二维数组来存储连接矩阵,并设定参数的最大值为 20。

(3) . 创建链接矩阵模块代码

int creatMGraph_L(MGraph_L &G) {

char v1,v2;

int i,j,w;

cout

cin>>G.vexnum>>G.arcnum;

for(i=0;i!=G.vexnum;++i)

{

cout

cin>>G.vexs[i];

}

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for(int k=0;k!=G.arcnum;++k)

{

cout

i=localvex(G,v1); j=localvex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

cout

return G.vexnum;

}

程序解释:该语句是从键盘输入顶点数和边数, 输入顶点和权值, 通过循环语句的调用,最后调用 creatMGraph_L()创建连接矩阵

(4). 最小生成树 Prim 算法及代价模块代码

int prim(int g[][max],int n)

{

int lowcost[max],prevex[max];

int i,j,k,min;

int sum=o;

for(i=2;i<>

{

lowcost[i]=g[1][i]; //初始化

prevex[i]=1;

}

lowcost[1]=0;

for(i=2;i<=n;i++) 形成="">

{

min=inf;

k=0;

for(j=2;j<>

if((lowcost[j]<>

{

min=lowcost[j];

k=j;

}

printf(

sum+=min;

lowcost[k]=0;

for(j=2;j<>

if(g[k][j]<>

{

lowcost[j]=g[k][j];

prevex[j]=k;

}

printf(

}

cout

cout<>

return 0;

}

程序解释:该语句运用一系列的循环语句来实现的, 利用前面的创建好的链接矩阵,通过各边权值的比较,最后调用 prim()函数,实现最小生成树的生成,同时运用 sum 把最小生成树各边权值相加得到最小生成树的代价。

5 系统调试 1、运行程序后,初界面:

2、输入顶点和弧的个数后的界面:

3、输入顶点后的界面:

4、输入一条边依附的顶点和权值后的界面:

5、输入确定数字 0及确定字母 y 后的界面:

6、输入确定数字 1及确定字母 n 后的界面:

小结

回顾起此次课程设计,至今我仍感慨颇多,从理论到实践,在整整一周的日子里,我学到很多很多的东西,不仅巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的内容。培养了独立思考,深入研究,分析问题、解决问题的能力,提高综合运用本课程所学知识的能力,还对课程设计的基的设计方法、步骤、思路、有了深刻的了解与认识,并对存储结构和函数的调用,比如连接矩阵、链接表、树、图等存储结构, for 引导的循环语句,特别是 Prim 算法理解的更深。我本次课程设计的题目是构造可以使 n 个城市连接的最小生成树, 开始看到题目觉得自己题目对自己比较有利,因为自己对最小生成树这节的内容比较熟悉 ,但是刚一开始编程觉得自己无从下手,这就看出自己的问题了,在书本上学的只是一些很肤浅的东西, 在实际运用中显得很无力, 但是通过自己慢慢查阅相关书籍和相关网站后, 编程的进度慢慢加快了, 一些相关的难点逐步得到解决, 最终还是完成了此次课程设计中最主要的几个步骤。

通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才是真正的知识,才能提高自己的实际动手能力和独立思考的能力。在设计的过程遇到了各种各样的问题,同时在设计的过程中发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固,通过这次课程设计,把以前所学过的知识重新温故,巩固了所学的知识。

源程序

#include

using namespace std;

#define int_max 10000 //最大的顶点数

#define inf 9999 //将无法到达的权值无限大设为 9999

#define max 20

//????????????????邻接矩阵定义???????? typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct

{

char vexs[20];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ int localvex(MGraph_L G,char v)//返回 V 的位置

{

int i=0;

while(G.vexs[i]!=v)

{

++i;

}

return i;

}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示

{

char v1,v2;

int i,j,w;

printf(

cin>>G.vexnum>>G.arcnum;

for(i=0;i!=G.vexnum;++i)

{

cout

cin>>G.vexs[i];

}

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for(int k=0;k!=G.arcnum;++k)

{

printf(

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

cout

return G.vexnum;

}

void ljjzprint(MGraph_L G)

{

int i,j;

for(i=0;i!=G.vexnum;++i)

{

for(j=0;j!=G.vexnum;++j)

cout<>

}

int visited[max];//访问标记

int we;

typedef struct arcnode//边结点

{

int adjvex;//该边指向的顶点的位置

struct arcnode *nextarc;//边尾相同的下一条弧

char *info;//该边信息

}arcnode;

typedef struct vnode//邻接链表顶点头接点

{

char data;//结点信息

arcnode *firstarc;//指向第一条依附该结点的边的指针 }vnode,adjlist;

typedef struct//图的定义

{

adjlist vertices[max];

int vexnum,arcnum;

int kind;

}algraph;

int prim(int g[][max],int n) //最小生成树 PRIM 算法

{

int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合 U 分别到剩余结点的最短路径 //prevex[]存储最短路径在 U 中的结点

int i,j,k,min;

int sum=0;

for(i=2;i<=n;i++) n个顶点,="">

{

lowcost[i]=g[1][i]; //初始化

prevex[i]=1; //顶点未加入到最小生成树中

}

lowcost[1]=0; //标志顶点 1加入 U 集合

for(i=2;i<=n;i++) 形成="">

{

min=inf;

k=0;

for(j=2;j<=n;j++) 寻找满足边的一个顶点在="" u,="" 另一个顶点在="" v="">

if((lowcost[j]<>

{

min=lowcost[j];

k=j;

}

printf(

sum+=min;

lowcost[k]=0; //顶点 k 加入 U

for(j=2;j<=n;j++) 修改由顶点="" k="">

if(g[k][j]<>

{

lowcost[j]=g[k][j];

prevex[j]=k;

}

printf(

}

cout

cout<>

return 0;

}

void main()

{

algraph gra;

MGraph_L G;

int i,d,g[20][20];

char a='a';

d=creatMGraph_L(G);

vnode v;

cout<>

cout

int s;

char y='y';

while(y='y')

{

cout

cin>>s;

switch(s)

{

case 0:

cout

ljjzprint(G);

break;

case 1:

for(i=0;i!=G.vexnum;++i)

for(int j=0;j!=G.vexnum;++j)

g[i+1][j+1]=G.arcs[i][j].adj;

cout

prim(g,d);

break;

}

cout<>

cin>>y;

if(y=='n')

break;

}

转载请注明出处范文大全网 » prim算法