primc语言
我原来自己写的模板
//朴素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;
}
㈡ 下面是我写的c语言判断一个数是不是素数的程序，我不知道到底什么地方错了，输入4为什么会输出prim
for循环写的有问题。这个判断条件会把所有素数的平方也当做素数
改为
for (i=2;i<=n;i++)//得包含等于的情况
谢谢采纳
㈢ 急！数据结构最小生成树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;
}
}
}
㈣ C语言prim最小生成树问题 调试无提示错误，但运行到 PRIM中输出那一步就运行不了了，求大神解答~
运行不下去了？你看一下这一行代码的变量值，是不是k的值超过了数组范围，又或close[k-1]超范围了？
㈤ 用prim算法求最小生成树:c语言
把main函数改成：
main(){
GraphMatrix graph = {
"abcd",
{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},
};
Edge mst[Max];
int i,j;
prim(graph,mst);
for(j=0;j<Max;j++)
{
printf("%c\t",mst[j].stop_vex);
printf("%c\t",mst[j].start_vex);
printf("%d\n",mst[j].weight);
}
}
还有GraphMatrix结构体里的vexs数组最好定义为vexs[VN+1]给字符串末尾的‘\0'留地方。
㈥ 用c语言描述prim算法求最小生成树.... 求高人指点啊，给出完整的代码，那个邻接矩阵是要要一次全部输入的
#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=102;
const int inf=1<<30;
int map[maxn][maxn];
int dis[maxn];
bool flag[maxn];
int a,b,c,n,m,ans;
void init()
{
memset(map,-1,sizeof(map));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]==-1 || c< map[a][b])
{
map[a][b]=map[b][a]=c;
}
}
}
void prim()
{
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
ans=0;
for(int j=1;j<=n;j++)
{
int now,value=inf;
for(int i=1;i<=n;i++)
{
if(flag[i]==false && dis[i]<value)
{
value=dis[i];
now=i;
}
}
if(value==inf)
{
cout << "-1" <<endl;
return;
}
flag[now]=true;
ans+=dis[now];
for(int i=1;i<=n;i++)
{
if(!flag[i] && map[now][i]!=-1 && dis[i]>map[now][i])
dis[i]=map[now][i];
}
}
cout << ans <<endl;
}
int main()
{
//'freopen("in.txt","r",stdin);
while(cin >> n >> m)
{
init();
prim();
}
return 0;
}
测试数据：
Sample Input
3 3
1 2 1
1 3 1
2 3 3
Sample Output
2
既然问到了prim算法相信你能看懂测试数据是什么意思~
㈦ 用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调整候选轻边集
}
}
㈧ 哪位高手帮我写一个C语言的Prim和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++; //扫描下一条边
}
}
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;
}
}
}