prim算法代码
❶ prim算法matlab
%Prims Algorithm
%coded by Vikramaditya V. Kunr
clc
fid = fopen('testfile1.txt', 'r'); % Input file
%Input file should be in the form of a text file.
%5 %order of matrix
%0 2 3 4 0
%2 0 1 2 5
%3 1 0 1 2
%4 2 1 0 2
%0 5 2 2 0
l = fscanf(fid, '%g %g', [1 1]) % Input matrix size from line 1
h = fscanf(fid, '%g %g', [l l]) % Input the matrix
a=h'
fclose(fid);
fid = fopen('Result.txt','wt'); % Output file
fprintf(fid,'Original matrix\n\n'); % Printing the original matrix in the output file
for i=1:l
for k=1:l
fprintf(fid,'%6d',a(i,k));
end
fprintf(fid,' \n');
end
for i=1:l
for j=1:l
if a(i,j)==0
a(i,j)=inf;
end
end
end
k=1:l
listV(k)=0;
listV(1)=1;
e=1;
while (e<l)
min=inf;
for i=1:l
if listV(i)==1
for j=1:l
if listV(j)==0
if min>a(i,j)
min=a(i,j);
b=a(i,j);
s=i;
d=j;
end
end
end
end
end
listV(d)=1;
distance(e)=b;
source(e)=s;
destination(e)=d;
e=e+1;
end
fprintf(fid,'\n\nDistance modified matrix\n\n');
for i=1:l
for k=1:l
if i==k
fprintf(fid,'%6d',0);
else
fprintf(fid,'%6d',a(i,k));
end
end
fprintf(fid,' \n');
end
fprintf(fid,'\n The nodes and shortest distances are \n');
fprintf(fid,'\nFORMAT: Distance(Source, destination) \n');
for g=1:e-1
fprintf(fid,'%d(%d,%d)\n',distance(g),source(g),destination(g));
end
status = fclose(fid);
clear
❷ Prim算法c语言表示，求源程序。。。。。。。。。
我原来自己写的模板
//朴素prim算法
//复杂度 O(n^2)
//flag[SIZE] 顶点标记
//mindis[SIZE] 当前最短距离
//dis[SIZE][SIZE] 任意两点间距离 邻接矩阵表示
int prim()
{
memset(flag,false,sizeof(bool)*(n+1));
flag[0] = true;
for(int i=1;i<n;i++)
mindis[i] = dis[0][i];
int ans = 0;
for(int i=1;i<n;i++)
{
int min = 10000;
int pos;
for(int j=1;j<n;j++)
{
if(!flag[j] && min > mindis[j])
{
min = mindis[j];
pos = j;
}
}
ans+=min;
flag[pos] = true;
for(int j=1;j<n;j++)
{
if(!flag[j] && mindis[j] > dis[pos][j])
mindis[j] = dis[pos][j];
}
}
return ans;
}
❸ prime算法建立最小生成树的代码
这个我也不会,
❹ Prim算法的实现过程
贪心过程.
首先,把图中的点分成两种,已连通和未连通的,我把它们分别称为"黑"和"白"点.
一开始时,图中全是白点,没有黑点.算法的第一步,随机选出一个白点,染成黑色.
然后开始一个重复的过程:
从当前图的边中寻找这样的一些边:它的其中一个端点是黑点,而另一个端点是一个白点. 我们可以把这类边称为"可扩展边". 然后算法需要从所有的可扩展边之中选出权值最小的一条.把这条可扩展边加入生成树之中,且把这条边的白色端点染成黑色.
重复这个过程,直到全部的节点都为黑色.
算法可以优化的地方是,在选择权值最小的可行边时可以使用堆.
❺ Python中prim算法或kruscal算法的实现
kruskal:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXE 100 //MAXE为最大的边数
struct edges
{
int bv,tv,w; //边集类型,存储一条边的起始顶点bv、终止顶点tv和权w
}edges;
typedef struct edges edgeset[MAXE];
//寻找v所在的连通集
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0)
i=set[i];
return i;
}
void kruskal(edgeset ge,int n,int e)
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0;
i=1; //i表示待获取的生成树中的边数,初值为1
j=1; //j表示ge中的下标,初值为1
while(j<n&&i<=e)//按边权递增顺序,逐边检查该边是否应加入到生成树中
{
v1=seeks(set,ge[i].bv); //确定顶点v所在的连通集
v2=seeks(set,ge[i].tv);
cout<<ge[i].bv<<":"<<v1<<", "<<ge[i].tv<<":"<<v2<<endl;
if(v1!=v2) //当v1,v2不在同一顶点集合,确定该边应当选入生成树
{
cout<<"("<<ge[i].bv<<", "<<ge[i].tv<<") "<<ge[i].w<<endl;
set[v1]=v2;
j++;
}
i++;
}
}
int main()
{
edgeset ee;
int n,e; //n是图的结点数,e是图的边数
n=6;
e=3;
for(int i=1;i<=e;i++)
{
scanf_s("%d",&ee[i].bv);
scanf_s("%d",&ee[i].tv);
scanf_s("%d",&ee[i].w);
}
//ee表示的边集图是按权值从小到大排列的
printf("最小生成树边集及它的权值: \n");
kruskal(ee,n,e);
system("pause");
return 0;
}
prim:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define N 3
void prim(int c[N][N])
{
//lowcost 为顶点间的最小距离，closest为最小距离上的邻接顶点
//lowcost[i]:与顶点i连通的最小边的权值
//closest[i]:与顶点i连通的邻接顶点
int lowcost[N],closest[N];
int i,j,k,min;
//lowcost,closest初始化
for(i=0;i<N;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
closest[0]=-1;
//寻找U 和 V 之间连接的最短距离的邻接点
for(i=0;i<N;i++)
{
min=32767;
k=0;
//寻找U 和 V 之间连接的最短距离的邻接点
for(j=0;j<N;j++)
{
if((lowcost[j]<min)&&(closest[j]!=-1))
{
min=lowcost[j];
k=j;
}
}
//输出新的邻接顶点，并修改lowcost值
if(k)
{
cout<<"("<<closest[k]<<", "<<k<<") "<<lowcost[k]<<endl;
closest[k]=-1;
for(j=1;j<N;j++)
{
if(closest[j]!=-1)// huo if(!(closest[j]==-1))
{
//修改lowcost值
lowcost[j]=c[k][j];
//修改邻接顶点
closest[j]=k;
}
}
}
}
}
int main()
{
int i,j,a[3][3];
cout<<"请输入二维数组："<<endl;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
cin>>a[i][j];
cout<<"最小树的结构为："<<endl;
prim(a);
int q;
cin>>q;
return 0;
}
❻ 急！数据结构最小生成树prim算法C语言实现
Kruskal算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成边数增1
for (i=0;i<n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
Prim算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
❼ 数据结构（prim算法）
开始时将v1加入U后，更新ee中的值应该是0 6 1 2 无穷 无穷；
将v3加入U后，更新ee中的值应该是0 5 0 2 6 4；
怎么会出现你说的0 6 0 5 无穷无穷的情况呢？
for(j = 0;j < G.vexnum;j++)中不是有条件判断么，要在k到j的距离小于ee[j]的value值时才会更新ee[j]啊。
❽ 请问谁有Prim算法代码 ,Kruskal算法代码 ,Dijkstra算法代码
我不是计算机系的
但是刚才帮你在CSDN上搜索了下,看到一个BLOG点击很高,内容很全
给你贴上,祝你成功:
用Prim算法求无向图的最小生成树
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445156.aspx
Kruskal算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445147.aspx
Dijkstra算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/11/17/1393130.aspx
银行家算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/09/09/1198551.aspx
❾ 求dijkstra、prim算法的C语言可执行代码！
http://ke..com/view/7839.html?fromTaglist
❿ 用prim算法的思想，用C语言编写出最小生成树的方法的代码
PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}