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;
}
}
}